Kruskal's Algorithm

Last updated Jan 24, 2022 Edit Source

• Cs algorithms

In order to create the minimum spanning tree of a graph, the kruskal’s algorithm takes the following approach:

• Save each of the edges into a priority queue
• Create $n$ clusters, each containing one of the vertices.
• Remove the minimum entry from the priority queue.
• If the nodes connected by the edge do not belong to the same cluster, we merge the two clusters. Add the removed edge to the tree.
• repeat

Kruskal’s algoritm runs in $O(mlogn)$ time. Where $m$ is the number of edges while $n$ is the number of vertices.