Dado un gráfico no dirigido, conectado y ponderado, encuentre el árbol de expansión mínimo (MST) del gráfico utilizando el algoritmo de Prim.
Input : Adjacency List representation
of above graph
Output : Edges in MST
0 - 1
1 - 2
2 - 3
3 - 4
2 - 5
5 - 6
6 - 7
2 - 8
Note: There are two possible MSTs, the other
MST includes edge 0-7 in place of 1-2.
Hemos discutido a continuación las implementaciones de MST de Prim.
- Algoritmo de Prim para la representación de arrays de adyacencia (en C/C++ con complejidad temporal O(v 2 )
- Algoritmo de Prim para la representación de listas de adyacencia (en C con complejidad temporal O(ELogV))
La segunda implementación es mejor en cuanto a la complejidad del tiempo, pero es realmente compleja ya que hemos implementado nuestra propia cola de prioridad. STL proporciona la cola de prioridad , pero la cola de prioridad proporcionada no admite la operación de disminución de clave. Y en el algoritmo de Prim, necesitamos una cola de prioridad y las siguientes operaciones en la cola de prioridad:
- ExtractMin: de todos esos vértices que aún no se han incluido en MST, necesitamos obtener un vértice con un valor de clave mínimo.
- DecreaseKey: después de extraer el vértice, necesitamos actualizar las claves de sus vértices adyacentes, y si la nueva clave es más pequeña, actualícela en la estructura de datos.
El algoritmo discutido aquí se puede modificar para que nunca se requiera la tecla de disminución. La idea es no insertar todos los vértices en la cola de prioridad, sino solo aquellos que no son MST y han sido visitados a través de un vértice que se ha incluido en MST. Realizamos un seguimiento de los vértices incluidos en MST en una array booleana separada en MST[].
1) Initialize keys of all vertices as infinite and
parent of every vertex as -1.
2) Create an empty priority_queue pq. Every item
of pq is a pair (weight, vertex). Weight (or
key) is used as first item of pair
as first item is by default used to compare
two pairs.
3) Initialize all vertices as not part of MST yet.
We use boolean array inMST[] for this purpose.
This array is required to make sure that an already
considered vertex is not included in pq again. This
is where Prim's implementation differs from Dijkstra.
In Dijkstra's algorithm, we didn't need this array as
distances always increase. We require this array here
because key value of a processed vertex may decrease
if not checked.
4) Insert source vertex into pq and make its key as 0.
5) While either pq doesn't become empty
a) Extract minimum key vertex from pq.
Let the extracted vertex be u.
b) Include u in MST using inMST[u] = true.
c) Loop through all adjacent of u and do
following for every vertex v.
// If weight of edge (u,v) is smaller than
// key of v and v is not already in MST
If inMST[v] = false && key[v] > weight(u, v)
(i) Update key of v, i.e., do
key[v] = weight(u, v)
(ii) Insert v into the pq
(iv) parent[v] = u
6) Print MST edges using parent array.
A continuación se muestra la implementación en C++ de la idea anterior.
C++
// STL implementation of Prim's algorithm for MST
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// This class represents a directed graph using
// adjacency list representation
class Graph
{
int V; // No. of vertices
// In a weighted graph, we need to store vertex
// and weight pair for every edge
list< pair<int, int> > *adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v, int w);
// Print MST using Prim's algorithm
void primMST();
};
// Allocates memory for adjacency list
Graph::Graph(int V)
{
this->V = V;
adj = new list<iPair> [V];
}
void Graph::addEdge(int u, int v, int w)
{
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
// Prints shortest paths from src to all other vertices
void Graph::primMST()
{
// Create a priority queue to store vertices that
// are being primMST. This is weird syntax in C++.
// Refer below link for details of this syntax
// http://geeksquiz.com/implement-min-heap-using-stl/
priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
int src = 0; // Taking vertex 0 as source
// Create a vector for keys and initialize all
// keys as infinite (INF)
vector<int> key(V, INF);
// To store parent array which in turn store MST
vector<int> parent(V, -1);
// To keep track of vertices included in MST
vector<bool> inMST(V, false);
// Insert source itself in priority queue and initialize
// its key as 0.
pq.push(make_pair(0, src));
key[src] = 0;
/* Looping till priority queue becomes empty */
while (!pq.empty())
{
// The first vertex in pair is the minimum key
// vertex, extract it from priority queue.
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted key (key must be first item
// in pair)
int u = pq.top().second;
pq.pop();
//Different key values for same vertex may exist in the priority queue.
//The one with the least key value is always processed first.
//Therefore, ignore the rest.
if(inMST[u] == true){
continue;
}
inMST[u] = true; // Include vertex in MST
// 'i' is used to get all adjacent vertices of a vertex
list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
// Get vertex label and weight of current adjacent
// of u.
int v = (*i).first;
int weight = (*i).second;
// If v is not in MST and weight of (u,v) is smaller
// than current key of v
if (inMST[v] == false && key[v] > weight)
{
// Updating key of v
key[v] = weight;
pq.push(make_pair(key[v], v));
parent[v] = u;
}
}
}
// Print edges of MST using parent array
for (int i = 1; i < V; ++i)
printf("%d - %d\n", parent[i], i);
}
// Driver program to test methods of graph class
int main()
{
// create the graph given in above figure
int V = 9;
Graph g(V);
// making above shown graph
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.primMST();
return 0;
}
Producción
0 - 1 1 - 2 2 - 3 3 - 4 2 - 5 5 - 6 6 - 7 2 - 8
Complejidad del tiempo : O(E Log V))
Una implementación más rápida utilizando una array de representación de vectores de un gráfico ponderado :
C++
// STL implementation of Prim's algorithm for MST
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// To add an edge
void addEdge(vector <pair<int, int> > adj[], int u,
int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
adj[v].push_back(make_pair(u, wt));
}
// Prints shortest paths from src to all other vertices
void primMST(vector<pair<int,int> > adj[], int V)
{
// Create a priority queue to store vertices that
// are being primMST. This is weird syntax in C++.
// Refer below link for details of this syntax
// http://geeksquiz.com/implement-min-heap-using-stl/
priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
int src = 0; // Taking vertex 0 as source
// Create a vector for keys and initialize all
// keys as infinite (INF)
vector<int> key(V, INF);
// To store parent array which in turn store MST
vector<int> parent(V, -1);
// To keep track of vertices included in MST
vector<bool> inMST(V, false);
// Insert source itself in priority queue and initialize
// its key as 0.
pq.push(make_pair(0, src));
key[src] = 0;
/* Looping till priority queue becomes empty */
while (!pq.empty())
{
// The first vertex in pair is the minimum key
// vertex, extract it from priority queue.
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted key (key must be first item
// in pair)
int u = pq.top().second;
pq.pop();
//Different key values for same vertex may exist in the priority queue.
//The one with the least key value is always processed first.
//Therefore, ignore the rest.
if(inMST[u] == true){
continue;
}
inMST[u] = true; // Include vertex in MST
// Traverse all adjacent of u
for (auto x : adj[u])
{
// Get vertex label and weight of current adjacent
// of u.
int v = x.first;
int weight = x.second;
// If v is not in MST and weight of (u,v) is smaller
// than current key of v
if (inMST[v] == false && key[v] > weight)
{
// Updating key of v
key[v] = weight;
pq.push(make_pair(key[v], v));
parent[v] = u;
}
}
}
// Print edges of MST using parent array
for (int i = 1; i < V; ++i)
printf("%d - %d\n", parent[i], i);
}
// Driver program to test methods of graph class
int main()
{
int V = 9;
vector<iPair > adj[V];
// making above shown graph
addEdge(adj, 0, 1, 4);
addEdge(adj, 0, 7, 8);
addEdge(adj, 1, 2, 8);
addEdge(adj, 1, 7, 11);
addEdge(adj, 2, 3, 7);
addEdge(adj, 2, 8, 2);
addEdge(adj, 2, 5, 4);
addEdge(adj, 3, 4, 9);
addEdge(adj, 3, 5, 14);
addEdge(adj, 4, 5, 10);
addEdge(adj, 5, 6, 2);
addEdge(adj, 6, 7, 1);
addEdge(adj, 6, 8, 6);
addEdge(adj, 7, 8, 7);
primMST(adj, V);
return 0;
}
Producción
0 - 1 1 - 2 2 - 3 3 - 4 2 - 5 5 - 6 6 - 7 2 - 8
Nota: Al igual que la implementación de la cola de prioridad de Dijkstra , es posible que tengamos varias entradas para el mismo vértice, ya que no hacemos (y no podemos) hacer isMST[v] = verdadero en la condición if.
C++
// If v is not in MST and weight of (u,v) is smaller
// than current key of v
if (inMST[v] == false && key[v] > weight)
{
// Updating key of v
key[v] = weight;
pq.push(make_pair(key[v], v));
parent[v] = u;
}
Java
// If v is not in MST and weight of (u,v) is smaller
// than current key of v
if (inMST[v] == false && key[v] > weight)
{
// Updating key of v
key[v] = weight;
pq.add(new Pair<Integer, Integer>(key[v], v));
parent[v] = u;
}
// This code is contributed by avanitrachhadiya2155
Python3
# If v is not in MST and weight of (u,v) is smaller # than current key of v if (inMST[v] == False and key[v] > weight) : # Updating key of v key[v] = weight pq.append([key[v], v]) parent[v] = u # This code is contributed by divyeshrabadiya07.
C#
// If v is not in MST and weight of (u,v) is smaller
// than current key of v
if (inMST[v] == false && key[v] > weight)
{
// Updating key of v
key[v] = weight;
pq.Add(new Tuple<int,int>(key[v], v));
parent[v] = u;
}
// This code is contributed by divyesh072019.
Javascript
<script>
// If v is not in MST and weight of (u,v)
// is smaller than current key of v
if (inMST[v] == false && key[v] > weight)
{
// Updating key of v
key[v] = weight;
value = [key[v], v];
pq.push(value);
parent[v] = u;
}
// This code is contributed by suresh07
</script>
Pero como se explica en el algoritmo de Dijkstra, la complejidad del tiempo sigue siendo O(E Log V) ya que habrá como máximo vértices O(E) en la cola de prioridad y O(Log E) es igual a O(Log V).
A diferencia de la implementación de Dijkstra, una array booleana en MST[] es obligatoria aquí porque los valores clave de los elementos recién insertados pueden ser menores que los valores clave de los elementos extraídos. Por lo que no debemos considerar elementos extraídos.
Este artículo es una contribución de Shubham Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA