Minimum Spanning Trees
- a spanning tree for an undirected graph G is an undirected graph that:
- contains all the vertices of G
- contains a subset of the edges of G
- has no cycles
- is connected (this implies that only connected graphs can have spanning trees)
Prim's Algorithm starts with a single vertex from the original graph and builds the MST by iteratively adding the least costly edges that stem from it (very similar to Dijkstra's Algorithm).
Kruskal's Algorithm starts with a forest of vertices without any edges and builds the MST by iteratively adding the least costly edges from the entire graph.
Prim's Algorithm achieves the steps described previously by using a priority queue of edges sorted by edge weights.
Kruskal's Algorithm is very similar to Prim's Algorithm. However, the major difference is that Kruskal's Algorithm starts with a "forest of nodes" (basically the original graph except with no edges) and interatively adds back the edges based on which edges have the lowest weight.
Kruskal's Algorithm and Prim's Algorithm, both of which solve this computational problem efficiently in O(|V| + |E|*log(|E|)) time