Monday, 18 September 2017

Graph | Kruskal’s algorithm

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

Steps for finding MST using Kruskal’s algorithm
1. Sort all the edges in non-decreasing order of their weight.

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far.
    2.a. if the cycle is not formed, include this edge.
    2.b. else, discard it.

3. Repeat step#2 until there are (V-1) edges in the spanning tree.

 Pseudo Code for Kruskal’s Algorithm

Example:














No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...