Kruskal's algorithm is another popular greedy algorithm used to find a minimum spanning tree (MST) in a weighted undirected graph. Unlike Prim's algorithm, which grows the MST from a starting vertex, Kruskal's algorithm builds the MST by repeatedly adding the lightest edge that does not create a cycle.

Here is the step-by-step explanation of Kruskal's algorithm:

1. Initialize an empty MST and a set of disjoint sets (one for each vertex).

2. Sort all the edges in the graph in non-decreasing order of their weights.

3. Iterate over each edge in the sorted order:

a. If adding the current edge to the MST does not create a cycle, i.e., the endpoints of the edge belong to different disjoint sets, add the edge to the MST and merge the two disjoint sets.

4. Return the MST.

Here is a pseudocode representation of Kruskal's algorithm:

Kruskal's Algorithm (G):
Initialize an empty MST
Initialize disjoint sets for each vertex in the graph
Sort all the edges in non-decreasing order of their weights

Repeat for each edge (u, v) in the sorted order:
    If the endpoints 'u' and 'v' belong to different disjoint sets:
        Add edge (u, v) to the MST
        Merge the disjoint sets containing 'u' and 'v'
Return the MST

Kruskal's algorithm typically uses a disjoint-set data structure (e.g., Union-Find) to efficiently determine whether adding an edge creates a cycle. The time complexity of Kruskal's algorithm is dominated by the sorting step, which is O(E log E), where E is the number of edges in the graph. However, if the graph is sparse (E is much smaller than V^2), the complexity can be expressed as O(E log V) by using a more efficient sorting algorithm.

Note that Kruskal's algorithm assumes the input graph is connected. If the graph is disconnected, you may need to modify the algorithm to handle multiple connected components.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc