graph algorithms figure graph and its minimum spanning tree prim' algorithm one way to compute minimum spanning tree is to grow the tree in successive stages in each stageone node is picked as the rootand we add an edgeand thus an associated vertexto the tree at any point in the algorithmwe can see that we have set of vertices that have already been included in the treethe rest of the vertices have not the algorithm then findsat each stagea new vertex to add to the tree by choosing the edge (uvsuch that the cost of (uvis the smallest among all edges where is in the tree and is not figure shows how this algorithm would build the minimum spanning treestarting from initiallyv is in the tree as root with no edges each step adds one edge and one vertex to the tree we can see that prim' algorithm is essentially identical to dijkstra' algorithm for shortest paths as beforefor each vertex we keep values dv and pv and an indication of whether it is known or unknown dv is the weight of the shortest edge connecting to known vertexand pv as beforeis the last vertex to cause change in dv the rest of the algorithm is exactly the samewith the exception that since the definition of dv is differentso is the update rule for this problemthe update rule is even simpler than beforeafter vertexvis selectedfor each unknown adjacent to vdw min(dw cw, the initial configuration of the table is shown in figure is selectedand and are updated the table resulting from this is shown in figure the next vertex