Minimum Spanning Trees
BACK: Graphs Basics
A minimum spanning tree is an tree (acyclic) in the graph that is able to connect every node with each other with the least amount of cost. For things like circuits or a set of friend’s houses, you might want to know the least amount of wire or which streets to take to minimize the amount of used or gas needed to get around.
The two strategies we use to find MSTs in a graph are both greedy algorithms. If the weights in a set of edges are unique, then the Prim’s algorithm and Kruskal’s algorithm will yield the same result; otherwise it is indeterministic.
Kruskal’s Algorithm
In Kruskal’s, we want to put all of the edges in some minimum priority queue and then pop off the smallest edges to add into our tree–while making sure that it doesn’t create a cycle in our tree.
You can see that in steps \(a\) through \(e\), we iteratively pick the edges with the smallest weights. However, in step \(f\), the edge with the smallest weight ends up creating a cycle in one of the trees. Therefore, we choose to skip it.
We iteratively continue this until all nodes have been connected into a single tree. The pseudocode is on page 631.
Prim’s Algorithm
In Prim’s we instead start with a node and then choose to expand all of its children. We keep all of the edges in a similar minimum priority queue and then pop out the edges that we find along the way–similar to BFS.
The pseudocode can be found on page 634.