Dado el gráfico ponderado no dirigido G , la tarea es encontrar el árbol de expansión máximo del gráfico usando el algoritmo de Prim
El algoritmo Prims es un algoritmo codicioso que se puede utilizar para encontrar el árbol de expansión mínimo (MST) , así como el árbol de expansión máximo de un gráfico .
Ejemplos:
Entrada: gráfico[V][V] = {{0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0}}
Salida:
el peso total del árbol de expansión máxima es 30.
Peso de los bordes
3 – 1 8
4 – 2 7
0 – 3 6
3 – 4 9
Explicación:
Elegir otros bordes no dará como resultado un árbol de expansión máximo.
Árbol de expansión máximo:
Dado un gráfico ponderado no dirigido , un árbol de expansión máxima es un árbol de expansión que tiene un peso máximo. Se puede calcular fácilmente usando el algoritmo de Prim . El objetivo aquí es encontrar el árbol de expansión con el peso máximo de todos los árboles de expansión posibles.
Algoritmo de Prim:
El algoritmo de Prim es un algoritmo codicioso, que funciona con la idea de que un árbol de expansión debe tener todos sus vértices conectados. El algoritmo funciona construyendo el árbol un vértice a la vez, desde un vértice de inicio arbitrario, y agregando la conexión más costosa posible del árbol a otro vértice, lo que nos dará el árbol de expansión máximo (MST) .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array visitada de tipo de datos booleano para realizar un seguimiento de los vértices visitados hasta el momento. Inicialice todos los valores con false .
- Inicializa una array de pesos[] , que representa el peso máximo para conectar ese vértice. Inicialice todos los valores con algún valor mínimo.
- Inicialice una array parent[] para realizar un seguimiento del árbol de expansión máximo .
- Asigne un valor grande, como el peso del primer vértice y el padre como -1 , para que se elija primero y no tenga padre.
- De todos los vértices no visitados, elija un vértice v que tenga un peso máximo y márquelo como visitado.
- Actualice los pesos de todos los vértices adyacentes no visitados de v . Para actualizar los pesos, itere a través de todos los vecinos no visitados de v . Para cada vértice adyacente x , si el peso del borde entre v y x es mayor que el valor anterior de v , actualice el valor de v con ese peso.
A continuación se muestra la implementación del algoritmo anterior:
C++
// C++ program for the above algorithm
#include <bits/stdc++.h>
using namespace std;
#define V 5
// Function to find index of max-weight
// vertex from set of unvisited vertices
int findMaxVertex(bool visited[], int weights[])
{
// Stores the index of max-weight vertex
// from set of unvisited vertices
int index = -1;
// Stores the maximum weight from
// the set of unvisited vertices
int maxW = INT_MIN;
// Iterate over all possible
// nodes of a graph
for (int i = 0; i < V; i++) {
// If the current node is unvisited
// and weight of current vertex is
// greater than maxW
if (visited[i] == false
&& weights[i] > maxW) {
// Update maxW
maxW = weights[i];
// Update index
index = i;
}
}
return index;
}
// Utility function to find the maximum
// spanning tree of graph
void printMaximumSpanningTree(int graph[V][V],
int parent[])
{
// Stores total weight of
// maximum spanning tree
// of a graph
int MST = 0;
// Iterate over all possible nodes
// of a graph
for (int i = 1; i < V; i++) {
// Update MST
MST += graph[i][parent[i]];
}
cout << "Weight of the maximum Spanning-tree "
<< MST << '\n'
<< '\n';
cout << "Edges \tWeight\n";
// Print the Edges and weight of
// maximum spanning tree of a graph
for (int i = 1; i < V; i++) {
cout << parent[i] << " - " << i << " \t"
<< graph[i][parent[i]] << " \n";
}
}
// Function to find the maximum spanning tree
void maximumSpanningTree(int graph[V][V])
{
// visited[i]:Check if vertex i
// is visited or not
bool visited[V];
// weights[i]: Stores maximum weight of
// graph to connect an edge with i
int weights[V];
// parent[i]: Stores the parent node
// of vertex i
int parent[V];
// Initialize weights as -INFINITE,
// and visited of a node as false
for (int i = 0; i < V; i++) {
visited[i] = false;
weights[i] = INT_MIN;
}
// Include 1st vertex in
// maximum spanning tree
weights[0] = INT_MAX;
parent[0] = -1;
// Search for other (V-1) vertices
// and build a tree
for (int i = 0; i < V - 1; i++) {
// Stores index of max-weight vertex
// from a set of unvisited vertex
int maxVertexIndex
= findMaxVertex(visited, weights);
// Mark that vertex as visited
visited[maxVertexIndex] = true;
// Update adjacent vertices of
// the current visited vertex
for (int j = 0; j < V; j++) {
// If there is an edge between j
// and current visited vertex and
// also j is unvisited vertex
if (graph[j][maxVertexIndex] != 0
&& visited[j] == false) {
// If graph[v][x] is
// greater than weight[v]
if (graph[j][maxVertexIndex] > weights[j]) {
// Update weights[j]
weights[j] = graph[j][maxVertexIndex];
// Update parent[j]
parent[j] = maxVertexIndex;
}
}
}
}
// Print maximum spanning tree
printMaximumSpanningTree(graph, parent);
}
// Driver Code
int main()
{
// Given graph
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
// Function call
maximumSpanningTree(graph);
return 0;
}
Java
// Java program for the above algorithm
import java.io.*;
class GFG
{
public static int V = 5;
// Function to find index of max-weight
// vertex from set of unvisited vertices
static int findMaxVertex(boolean visited[],
int weights[])
{
// Stores the index of max-weight vertex
// from set of unvisited vertices
int index = -1;
// Stores the maximum weight from
// the set of unvisited vertices
int maxW = Integer.MIN_VALUE;
// Iterate over all possible
// nodes of a graph
for (int i = 0; i < V; i++)
{
// If the current node is unvisited
// and weight of current vertex is
// greater than maxW
if (visited[i] == false && weights[i] > maxW)
{
// Update maxW
maxW = weights[i];
// Update index
index = i;
}
}
return index;
}
// Utility function to find the maximum
// spanning tree of graph
static void printMaximumSpanningTree(int graph[][],
int parent[])
{
// Stores total weight of
// maximum spanning tree
// of a graph
int MST = 0;
// Iterate over all possible nodes
// of a graph
for (int i = 1; i < V; i++)
{
// Update MST
MST += graph[i][parent[i]];
}
System.out.println("Weight of the maximum Spanning-tree "
+ MST);
System.out.println();
System.out.println("Edges \tWeight");
// Print the Edges and weight of
// maximum spanning tree of a graph
for (int i = 1; i < V; i++)
{
System.out.println(parent[i] + " - " + i + " \t"
+ graph[i][parent[i]]);
}
}
// Function to find the maximum spanning tree
static void maximumSpanningTree(int[][] graph)
{
// visited[i]:Check if vertex i
// is visited or not
boolean[] visited = new boolean[V];
// weights[i]: Stores maximum weight of
// graph to connect an edge with i
int[] weights = new int[V];
// parent[i]: Stores the parent node
// of vertex i
int[] parent = new int[V];
// Initialize weights as -INFINITE,
// and visited of a node as false
for (int i = 0; i < V; i++) {
visited[i] = false;
weights[i] = Integer.MIN_VALUE;
}
// Include 1st vertex in
// maximum spanning tree
weights[0] = Integer.MAX_VALUE;
parent[0] = -1;
// Search for other (V-1) vertices
// and build a tree
for (int i = 0; i < V - 1; i++) {
// Stores index of max-weight vertex
// from a set of unvisited vertex
int maxVertexIndex
= findMaxVertex(visited, weights);
// Mark that vertex as visited
visited[maxVertexIndex] = true;
// Update adjacent vertices of
// the current visited vertex
for (int j = 0; j < V; j++) {
// If there is an edge between j
// and current visited vertex and
// also j is unvisited vertex
if (graph[j][maxVertexIndex] != 0
&& visited[j] == false) {
// If graph[v][x] is
// greater than weight[v]
if (graph[j][maxVertexIndex]
> weights[j]) {
// Update weights[j]
weights[j]
= graph[j][maxVertexIndex];
// Update parent[j]
parent[j] = maxVertexIndex;
}
}
}
}
// Print maximum spanning tree
printMaximumSpanningTree(graph, parent);
}
// Driver Code
public static void main(String[] args)
{
// Given graph
int[][] graph = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
// Function call
maximumSpanningTree(graph);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python program for the above algorithm
import sys
V = 5;
# Function to find index of max-weight
# vertex from set of unvisited vertices
def findMaxVertex(visited, weights):
# Stores the index of max-weight vertex
# from set of unvisited vertices
index = -1;
# Stores the maximum weight from
# the set of unvisited vertices
maxW = -sys.maxsize;
# Iterate over all possible
# Nodes of a graph
for i in range(V):
# If the current Node is unvisited
# and weight of current vertex is
# greater than maxW
if (visited[i] == False and weights[i] > maxW):
# Update maxW
maxW = weights[i];
# Update index
index = i;
return index;
# Utility function to find the maximum
# spanning tree of graph
def printMaximumSpanningTree(graph, parent):
# Stores total weight of
# maximum spanning tree
# of a graph
MST = 0;
# Iterate over all possible Nodes
# of a graph
for i in range(1, V):
# Update MST
MST += graph[i][parent[i]];
print("Weight of the maximum Spanning-tree ", MST);
print();
print("Edges \tWeight");
# Print Edges and weight of
# maximum spanning tree of a graph
for i in range(1, V):
print(parent[i] , " - " , i , " \t" , graph[i][parent[i]]);
# Function to find the maximum spanning tree
def maximumSpanningTree(graph):
# visited[i]:Check if vertex i
# is visited or not
visited = [True]*V;
# weights[i]: Stores maximum weight of
# graph to connect an edge with i
weights = [0]*V;
# parent[i]: Stores the parent Node
# of vertex i
parent = [0]*V;
# Initialize weights as -INFINITE,
# and visited of a Node as False
for i in range(V):
visited[i] = False;
weights[i] = -sys.maxsize;
# Include 1st vertex in
# maximum spanning tree
weights[0] = sys.maxsize;
parent[0] = -1;
# Search for other (V-1) vertices
# and build a tree
for i in range(V - 1):
# Stores index of max-weight vertex
# from a set of unvisited vertex
maxVertexIndex = findMaxVertex(visited, weights);
# Mark that vertex as visited
visited[maxVertexIndex] = True;
# Update adjacent vertices of
# the current visited vertex
for j in range(V):
# If there is an edge between j
# and current visited vertex and
# also j is unvisited vertex
if (graph[j][maxVertexIndex] != 0 and visited[j] == False):
# If graph[v][x] is
# greater than weight[v]
if (graph[j][maxVertexIndex] > weights[j]):
# Update weights[j]
weights[j] = graph[j][maxVertexIndex];
# Update parent[j]
parent[j] = maxVertexIndex;
# Print maximum spanning tree
printMaximumSpanningTree(graph, parent);
# Driver Code
if __name__ == '__main__':
# Given graph
graph = [[0, 2, 0, 6, 0], [2, 0, 3, 8, 5], [0, 3, 0, 0, 7], [6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]];
# Function call
maximumSpanningTree(graph);
# This code is contributed by 29AjayKumar
C#
// C# program for the above algorithm
using System;
class GFG
{
public static int V = 5;
// Function to find index of max-weight
// vertex from set of unvisited vertices
static int findMaxVertex(bool[] visited,
int[] weights)
{
// Stores the index of max-weight vertex
// from set of unvisited vertices
int index = -1;
// Stores the maximum weight from
// the set of unvisited vertices
int maxW = int.MinValue;
// Iterate over all possible
// nodes of a graph
for (int i = 0; i < V; i++)
{
// If the current node is unvisited
// and weight of current vertex is
// greater than maxW
if (visited[i] == false && weights[i] > maxW)
{
// Update maxW
maxW = weights[i];
// Update index
index = i;
}
}
return index;
}
// Utility function to find the maximum
// spanning tree of graph
static void printMaximumSpanningTree(int[, ] graph,
int[] parent)
{
// Stores total weight of
// maximum spanning tree
// of a graph
int MST = 0;
// Iterate over all possible nodes
// of a graph
for (int i = 1; i < V; i++)
{
// Update MST
MST += graph[i, parent[i]];
}
Console.WriteLine(
"Weight of the maximum Spanning-tree " + MST);
Console.WriteLine();
Console.WriteLine("Edges \tWeight");
// Print the Edges and weight of
// maximum spanning tree of a graph
for (int i = 1; i < V; i++) {
Console.WriteLine(parent[i] + " - " + i + " \t"
+ graph[i, parent[i]]);
}
}
// Function to find the maximum spanning tree
static void maximumSpanningTree(int[, ] graph)
{
// visited[i]:Check if vertex i
// is visited or not
bool[] visited = new bool[V];
// weights[i]: Stores maximum weight of
// graph to connect an edge with i
int[] weights = new int[V];
// parent[i]: Stores the parent node
// of vertex i
int[] parent = new int[V];
// Initialize weights as -INFINITE,
// and visited of a node as false
for (int i = 0; i < V; i++) {
visited[i] = false;
weights[i] = int.MinValue;
}
// Include 1st vertex in
// maximum spanning tree
weights[0] = int.MaxValue;
parent[0] = -1;
// Search for other (V-1) vertices
// and build a tree
for (int i = 0; i < V - 1; i++) {
// Stores index of max-weight vertex
// from a set of unvisited vertex
int maxVertexIndex
= findMaxVertex(visited, weights);
// Mark that vertex as visited
visited[maxVertexIndex] = true;
// Update adjacent vertices of
// the current visited vertex
for (int j = 0; j < V; j++) {
// If there is an edge between j
// and current visited vertex and
// also j is unvisited vertex
if (graph[j, maxVertexIndex] != 0
&& visited[j] == false) {
// If graph[v][x] is
// greater than weight[v]
if (graph[j, maxVertexIndex]
> weights[j]) {
// Update weights[j]
weights[j]
= graph[j, maxVertexIndex];
// Update parent[j]
parent[j] = maxVertexIndex;
}
}
}
}
// Print maximum spanning tree
printMaximumSpanningTree(graph, parent);
}
// Driver Code
static public void Main()
{
// Given graph
int[, ] graph = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
// Function call
maximumSpanningTree(graph);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program for the above algorithm
var V = 5;
// Function to find index of max-weight
// vertex from set of unvisited vertices
function findMaxVertex(visited, weights)
{
// Stores the index of max-weight vertex
// from set of unvisited vertices
var index = -1;
// Stores the maximum weight from
// the set of unvisited vertices
var maxW = -1000000000;
// Iterate over all possible
// nodes of a graph
for (var i = 0; i < V; i++) {
// If the current node is unvisited
// and weight of current vertex is
// greater than maxW
if (visited[i] == false
&& weights[i] > maxW) {
// Update maxW
maxW = weights[i];
// Update index
index = i;
}
}
return index;
}
// Utility function to find the maximum
// spanning tree of graph
function printMaximumSpanningTree(graph, parent)
{
// Stores total weight of
// maximum spanning tree
// of a graph
var MST = 0;
// Iterate over all possible nodes
// of a graph
for (var i = 1; i < V; i++) {
// Update MST
MST += graph[i][parent[i]];
}
document.write( "Weight of the maximum Spanning-tree "
+ MST + '<br>'
+ '<br>');
document.write( "Edges \tWeight<br>");
// Print the Edges and weight of
// maximum spanning tree of a graph
for (var i = 1; i < V; i++) {
document.write( parent[i] + " - " + i + " "
+ graph[i][parent[i]] + " <br>");
}
}
// Function to find the maximum spanning tree
function maximumSpanningTree(graph)
{
// visited[i]:Check if vertex i
// is visited or not
var visited = Array(V).fill(false);
// weights[i]: Stores maximum weight of
// graph to connect an edge with i
var weights = Array(V).fill(-1000000000);
// parent[i]: Stores the parent node
// of vertex i
var parent = Array(V).fill(0);
// Include 1st vertex in
// maximum spanning tree
weights[0] = 1000000000;
parent[0] = -1;
// Search for other (V-1) vertices
// and build a tree
for (var i = 0; i < V - 1; i++) {
// Stores index of max-weight vertex
// from a set of unvisited vertex
var maxVertexIndex
= findMaxVertex(visited, weights);
// Mark that vertex as visited
visited[maxVertexIndex] = true;
// Update adjacent vertices of
// the current visited vertex
for (var j = 0; j < V; j++) {
// If there is an edge between j
// and current visited vertex and
// also j is unvisited vertex
if (graph[j][maxVertexIndex] != 0
&& visited[j] == false) {
// If graph[v][x] is
// greater than weight[v]
if (graph[j][maxVertexIndex] > weights[j]) {
// Update weights[j]
weights[j] = graph[j][maxVertexIndex];
// Update parent[j]
parent[j] = maxVertexIndex;
}
}
}
}
// Print maximum spanning tree
printMaximumSpanningTree(graph, parent);
}
// Driver Code
// Given graph
var graph = [ [ 0, 2, 0, 6, 0 ],
[ 2, 0, 3, 8, 5 ],
[ 0, 3, 0, 0, 7 ],
[ 6, 8, 0, 0, 9 ],
[ 0, 5, 7, 9, 0 ] ];
// Function call
maximumSpanningTree(graph);
// This code is contributed by rutvik_56.
</script>
Producción:
Weight of the maximum Spanning-tree 30 Edges Weight 3 - 1 8 4 - 2 7 0 - 3 6 3 - 4 9
Complejidad temporal: O(V 2 ) donde V es el número de Nodes en el gráfico.
Espacio Auxiliar: O(V 2 )
Publicación traducida automáticamente
Artículo escrito por mishrapriyanshu557 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA