# Kruskal's MST vs Prim's MST

There are two ways to get an MST from a connected graph.

There are two major algorithms to get an MST (Minimum Spanning Tree) given from a connected graph. The reason why I write "an" MST here is that there can be multiple MSTs for a connected graph.

The main idea of Kruskal's algorithm is that we repeatedly take the lightest edge in the given graph for the MST. Through the process of Kruskal's algorithm, we maintain a disjoint forest. The important idea is to use the disjoint set algorithms to make sure that we connect two different trees with an edge in each iteration, and finally reach the state of one big connected tree. Sample implementation.

On the other hand, we do not need to care about the connectedness in Prim's algorithm. In Prim's algorithm, a starting node is given. We grow our MST from the starting node one by one in each iteration. This is the main idea of Prim's algorithm. Sample implementation.