Java Reference
In-Depth Information
A
B
7
5
C
6
9
1
2
D
2
F
E
1
Figure11.20 A graph and its MST. All edges appear in the original graph.
Those edges drawn with heavy lines indicate the subset making up the MST. Note
that edge (C, F) could be replaced with edge (D, F) to form a different MST with
equal cost.
edge connects N to another vertex; call this M. Add Vertex M and Edge (N, M) to
the MST. Next, pick the least-cost edge coming from either N or M to any other
vertex in the graph. Add this edge and the new vertex it reaches to the MST. This
process continues, at each step expanding the MST by selecting the least-cost edge
from a vertex currently in the MST to a vertex not currently in the MST.
Prim's algorithm is quite similar to Dijkstra's algorithm for finding the single-
source shortest paths. The primary difference is that we are seeking not the next
closest vertex to the start vertex, but rather the next closest vertex to any vertex
currently in the MST. Thus we replace the lines
if(D[w]>(D[v]+G->weight(v,w)))
D[w]=D[v]+G->weight(v,w);
in Djikstra's algorithm with the lines
if(D[w]>G->weight(v,w))
D[w]=G->weight(v,w);
in Prim's algorithm.
Figure 11.21 shows an implementation for Prim's algorithm that searches the
distance matrix for the next closest vertex. For each vertex I, when I is processed
by Prim's algorithm, an edge going to I is added to the MST that we are building.
Array V[I] stores the previously visited vertex that is closest to Vertex I. This
information lets us know which edge goes into the MST when Vertex I is processed.
The implementation of Figure 11.21 also contains calls to AddEdgetoMST to
indicate which edges are actually added to the MST.
Alternatively, we can implement Prim's algorithm using a priority queue to find
the next closest vertex, as shown in Figure 11.22. As with the priority queue version
of Dijkstra's algorithm, the heap's Elem type stores a DijkElem object.
Search WWH ::




Custom Search