# 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions