Minimum Spanning Tree (Prim's and Kruskal's algorithm)

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach (pick the smallest weight edg).

Below are the steps for finding MST using Kruskal's algorithm:

1) Arrange all of the edges in ascending order of weight.

2) Pick the smallest edge and check if it will form a cycle if it is added to the spanning tree formed so far. If a cycle is not formed, include this edge. Otherwise, throw it away.

3) Repeat step 2 until the spanning tree has (v-1) edges.

Note: The disjoint set data structure is used to make sure that the two nodes belong to different components (adding a new node will not create a cycle).

The time complexity of this solution is O(E LogE + E LogV) ~ O(E logE) or O(E logV) and space complexity is O(V + E).

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected, connected graph.

The algorithm can be described as follows:

1) Initialise a tree with a single vertex, chosen arbitrarily from the graph.

2) Grow the tree by one edge at a time, selected out of the minimum-weight adjacent edges that connect the tree to vertices not yet in the tree.

3) Repeat step 2 until the tree has all vertices.

We can implement the above-mentioned algorithm with the help of a priority-queue and an auxiliary array to track already added nodes.

We can start by adding any node to the priority-queue and keep on doing the below-mentioned steps until the queue is not empty.

If the polled node is already visited, mark it as visited, add its weight to the total weight, and add its adjacents to the queue.

Prim's algorithm works only on connected graphs.

The time complexity of this solution is O(E * log V) and space complexity is O(V).