minimum spanning tree

Minimum Spanning Tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Kruskal’s algorithm to find the minimum cost spanning tree uses the greedy approach....