# Minimum Spanning Tree — Prim’s and Kruskal’s algorithm

## What is a spanning tree?

1. has n vertices
2. has n - 1 edge
3. is connected

## What is a minimum spanning tree?

`|E|C|V|- 1 - cycles`

# Prims’s Algorithm

## Algorithm

1. Initialize the minimum spanning tree with a vertex chosen at random.
2. Find all the edges that connect the tree to new adjacent vertices, find the minimum among them and add it to the tree.
3. Repeat step 2 until we get a minimum spanning tree.

# Kruskal’s Algorithm

## Algorithm

1. Sort all the edges in the ascending order of weight.
2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created a cycle, then remove the edge.
3. Keep adding edges until we reach all vertices i.e., get a minimum spanning tree.

# Differences between Prim’s and Kruskal’s algorithm

1. As we discussed early on, Prim’s algorithm can only generate a connected graph component thus it works only on a connected graph. Whereas Kruskal’s algorithm can generate forest ( disconnected components), it can work on disconnected graphs.
2. When to use Prim’s and when to use Kruskal’s? Due to each algorithm's nature, we can say that Prim’s algorithm runs faster in dense graphs whereas Kruskal’s algorithm runs faster in a sparse graph. Why is it so? Prim’s algorithm runs better in a dense graph as it only compares a limited number of edges per loop, whereas Kruskal’s algorithm starts by sorting all edges in the list when going through them again to check if the edge is part of MST or not. While both algorithms have similar running times, the number of edges in the graph should be the main component when you are deciding between the algorithms. More edges compared to vertices, use Prim’s otherwise go with Kruskal’s.

# So, where to go from here?

## My Github Repository

1. https://github.com/Sethuram52001/DSA

--

--

--

## More from Sethuram.S.V

Love podcasts or audiobooks? Learn on the go with our new app.