# 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

- Spanning tree has wide applications in many areas like network design.
- Spanning tree is important in designing routing algorithms.
- 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:**

- Firstly arrange all the edges in increasing order of their weight.
- Then the edges should be added if it does not form a circuit.
- Continue these steps till all the edges are visited and MST is formed.
- 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:**

- Start with a vertex, say
**u**. - 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**. - Now among the set of all vertices find other vertex
**v**that is not included in_{i}**A**such that**(v**is minimum labeled and is the nearest neighbor of all vertices in set_{i}, v_{j})**A**and it does not form a cycle, add it to**A**. - Continue this process till we get an
**MST**, then the**MST**formed will be of minimum cost.

**Reference:** Kruskal's algorithm

**Quick links:**

C FAQ(s)
C Advance programs
C/C++ Tips & Tricks
Puzzles
JavaScript
CSS
Python
Linux Commands
PHP
Android
Articles
More...

**Featured post:**

Introduction to Linux (Its modes, Safety, Most popular Applications)

Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions