Saturday, 12 June 2021

Kruskal's Algorithm for finding minimum spanning tree

 The implementation of Kruskal’s Algorithm is explained in the following steps-

Step-01: Sort all the edges from low weight to high weight.

Step-02:

  • Take the edge with the lowest weight and use it to connect the vertices of graph.
  • If adding an edge creates a cycle, then reject that edge and go for the next least weight edge.

Step-03:
Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is obtained.

Example:

In the above example, we first listed all the edges in this ascending order.

Then, we started adding minimum weighted edge to the MST. If the addition of edge causes cycle in the graph we ignored it.

Repeat this process until all vertices are connected in the graph.

Time complexity:

In Kruskal's algorithm, most time consuming operation is sorting because the total complexity of the Disjoint-Set operations will be O ( E l o g V ) , which is the overall Time Complexity of the algorithm.

Source: classic data structure by samantha

0 comments:

Post a Comment

Note: only a member of this blog may post a comment.

Find Us On Facebook

python tutorial

More

C Programming

More

Java Tutorial

More

Data Structures

More

MS Office

More

Database Management

More
Top