known dv pv figure the table after and are selected (prim' algorithm terminatesthe final table is shown in figure the edges in the spanning tree can be read from the table( )( )( )( )( )( the total cost is the entire implementation of this algorithm is virtually identical to that of dijkstra' algorithmand everything that was said about the analysis of dijkstra' algorithm applies here be aware that prim' algorithm runs on undirected graphsso when coding itremember to put every edge in two adjacency lists the running time is (| | without heapswhich is optimal for dense graphsand (|elog | |using binary heapswhich is good for sparse graphs kruskal' algorithm second greedy strategy is to continually select the edges in order of smallest weight and accept an edge if it does not cause cycle the action of the algorithm on the graph in the preceding example is shown in figure edge weight action ( ( ( ( ( ( ( ( ( accepted accepted accepted accepted rejected rejected accepted rejected accepted figure action of kruskal' algorithm on