Minimum Spanning Tree

Algorithm:

1. Select any node and shade the node.
2. Look at all the edges and pick one edge which connects to an unshaded node and smallest weight.
3. Repeat above steps till no unshaded nodes exist.
4. Sum of the shaded costs is the minimum cost of the minimum spanning tree.

Prim's algorithm:

• Keep track of one connected component
• Pick one connected edge which has smallest weight
• Look at nearest neighbors of a seen/shaded nodes
• Running time: O(E + logV) using fibonacci heap
• Most effective on a dense graph

Kruskal's algorithm:

• Don't need to keep track of if a connected component exists
• Pick one globally smallest weight edge - this could be connected/unconnected
• Can look at any node within the graph provided the above condition is satisfied
• Running time: O(ElogV)
• Most effective on a sparse graph