Minimum Spanning Tree (MST)

Main ideas: keep adding edges into the MST.

1. Kruskal's Algorithm
2. Prim's Algorithm

A graph G = (V, E)

Kruskal's Algorithm (Union-Find Data structure)

1. Give each node a different color (we can simply use numbers as color/name).

2. Order all the weighted edges in increasing order.

3. Scan the edge list, if the edge does not incur loop, which means the end points have the same color, then add that edge into MST. And Make union of the nodes once we add one edge into the MST.

4. The process will stop if all the nodes have the same color.

Prim's Algorithm:

1. we maintain a set S on which a spanning tree has been constructed so far. Initially S= {s}.

2. In each iteration, we grow S by one node, adding the node v that minimizes the "attachment cost", and including the edge e = (u, v) that achieves this minimum in the spanning tree.