Home » Algorithms

Kruskal's (P) and Prim's (K) Algorithms

In this article, we are going to learn about the minimum spanning tree with their application and there are some algorithms for finding the minimum spanning tree which are kruskal’s algorithms and prim’s algorithm, that are also prescribed in this article.
Submitted by Abhishek Kataria, on August 02, 2018

Minimum Spanning Tree

• An MST is a subset of the edges of the connected, undirected graph that connect all the vertices together, in which there is no forming of a cycle and there should be minimum possible total edge weight.
• In this weight of a tree is defined as the sum of the weight of all its edges which are connected but no formation of the cycle is there.
• A tree T is said to be a spanning tree of a connected graph X if T is a subgraph of X and T contains all vertices of X.

Application of Spanning Tree

1. Spanning tree has wide applications in many areas like network design.
2. Spanning tree is important in designing routing algorithms.
3. Practical application based on minimum spanning tree includes taxonomy and cluster analysis.

1) Kruskal’s Algorithm

• It is an application of a greedy algorithm.
• In this edges are selected with minimum weight and added to MST till no cycle is formed.
• It is used to find a minimum cost.
• It finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
• Kruskal algorithm does not form a tree at each step.

Steps for the kruskal’s algorithm are as follows:

1. Firstly arrange all the edges in increasing order of their weight.
2. Then the edges should be added if it does not form a circuit.
3. Continue these steps till all the edges are visited and MST is formed.
4. Add the cost of all edges in MST to get a minimum cost of a spanning tree.

2) Prim’s algorithm

• This algorithm generally focused on vertices.
• Prim's algorithm always forms a tree at every step.
• It applies the nearest neighbor method to select new edges.
• This algorithm is generally used when we have to find a minimum cost of a dense graph because this number of edges will be high.
• Basically, Prim's algorithm is faster than the Kruskal's algorithm in the case of the complex graph.

Steps for the Prim’s algorithms are as follows:

1. Start with a vertex, say u.
2. Select another vertex v such that edges are formed from u and v and are of minimum weight, connect uv and add it to set of MST for edges A.
3. Now among the set of all vertices find other vertex v_i that is not included in A such that (v_i, v_j) is minimum labeled and is the nearest neighbor of all vertices in set A and it does not form a cycle, add it to A.
4. Continue this process till we get an MST, then the MST formed will be of minimum cost.

Reference: Kruskal's algorithm