Consider the following algorithm to find the minimum spanning tree of an undirected, weighted graph G(V,E)....

  

Transcribed Image Text:

Consider the following algorithm to find the minimum spanning tree of an undirected, weighted graph G(V,E). For simplicity, you may assume that no two edges in G have the same weight. procedure FINDMST (G(V,E)) E' E for Each edge e in E in decreasing weight order do if G(V, E' - e) is connected then E' E' - e return E' Show that this algorithm outputs a minimum spanning tree of G. Consider the following algorithm to find the minimum spanning tree of an undirected, weighted graph G(V,E). For simplicity, you may assume that no two edges in G have the same weight. procedure FINDMST (G(V,E)) E' E for Each edge e in E in decreasing weight order do if G(V, E' - e) is connected then E' E' - e return E' Show that this algorithm outputs a minimum spanning tree of G.