Kruskul's Algorithm

 

kruskul's algorithm

Definition:

Kruskal's algorithm for finding the shortest forest of non-directional edge-weighted graphs If the graph is connected, it finds the minimum spanning tree. . consists of a minimum spanning tree for each connected component.) Greedy algorithms in graph theory add the lowest weight edge that will not form a loop in the spanning forest at least at each step.

Algorithm:

  • create a forest (a set of trees), where each vertex in the graph is a separate tree
  • create a sorted set containing all the edges in the graph
  • while sorted set is nonempty and set of tree is not yet spanning
  • Remove an edge with minimum weight from sorted set

If the edge is removed to join two different trees, combine the two trees into one tree and add it to the  forest

After the algorithm is finished, the forest forms the least sparse forest of the graph. If the graph is connected, then the forest has a subset and forms a minimum spanning tree.

YouTube Video 

Click here to see video how to solve kruskul's algorithm in Hindi/Urdu language.

Comments