Table of Contents Definition Finding the Minimum Spanning Tree Kruskal’s Algorithm Prim’s Algorithm Minimum spanning trees are undirected graphs that connect all of the vertices such that there are no redundant edges and the total weight is minimized. They are useful for finding the shortest path between two points in a graph. Useful application of MSTs include
network design: it is useful to know the least expensive path with respect to either latency or resource cost for telecommunications networks, transportation networks, or electrical grids. approximation algorithms: MSTs can be used to approximate the solution to the traveling salesman problem. clustering: MSTs can be used to cluster data points in a graph. image segmentation: MSTs can be used to segment images into smaller regions. Definition Let \(G\) be a connected, undirected graph with edges \(E\), vertices \(V\), and edge weights \(w\). A minimum spanning tree is a subset \(T \subseteq E\) that connects all of the vertices such that the total weight is minimized. The original graph \(G\) is shown below.