|
Data Structures and Algorithms
|
| Prim's Algorithm
|
Prim's Algorithm
Prim's algorithm is very similar to Kruskal's:
whereas Kruskal's "grows" a forest of trees,
Prim's algorithm grows a single tree until it
becomes the minimum spanning tree.
Both algorithms use the greedy approach -
they add the cheapest edge that will not cause a
cycle.
But rather than choosing the cheapest edge that
will connect any pair of trees together,
Prim's algorithm only adds edges that join nodes to
the existing tree.
(In this respect, Prim's algorithm is very similar
to Dijkstra's algorithm
for finding shortest paths.)
Prim's algorithm works efficiently if we keep a
list d[v] of the cheapest weights which connect
a vertex, v, which is not in the tree,
to any vertex already in the tree.
A second list pi[v] keeps the index of the
node already in the tree to which v
can be connected with cost, d[v].
int *MinimumSpanningTree( Graph g, int n, double **costs ) {
Queue q;
int u, v;
int d[n], *pi;
q = ConsEdgeQueue( g, costs );
pi = ConsPredList( n );
for(i=0;iadj[u] {
if ( (v in q) && costs[u][v] < d[v] ) {
pi[v] = u;
d[v] = costs[u][v];
}
}
}
return pi;
}
The steps are:
- The edge queue is constructed
- A predecessor list
of predecessors for each node is constructed.
- "Best" distances to each node are set to infinity.
- Choose node 0 as the "root" of the MST (any node will do
as the MST must contain all nodes),
- While the edge queue is not empty,
- Extract the cheapest edge, u, from the queue,
- Relax all its neighbours -
if the distance of this node from the closest node in
the MST formed so far is larger than d[u][v],
then update d[u][v] and set v's
predecessor to u.
- Return the predecessor list.
The time complexity is
O(VlogV + ElogV) = O(ElogV),
making it the same as Kruskal's algorithm.
However, Prim's algorithm can be improved using
Fibonacci Heaps
(cf Cormen) to
O(E + logV).
- Predecessor list
- A data structure for defining a graph by storing a
predecessor for each node with that node.
Thus it uses a single array of integers to define
a sub-graph of a graph.
- Fibonacci Heaps
- See Cormen, chapter 21.
The time complexity is
O(VlogV + ElogV) = O(ElogV),
making it the same as Kruskal's algorithm.
However, Prim's algorithm can be improved using
Fibonacci Heaps
(cf Cormen) to
O(E + logV).
© John Morris, 1998