How Far Have You Gotten in Algorithm — Kruskal’s Algorithm
2 min readJan 4, 2021
** This story heavily depends on an astonishing explanation of Programiz
Kruskal’s Algorithm
Kruskal’s algorithm is a minimum spanning tree that takes a graph as input and finds the subset of the edges of that graph which forms a tree including every vertex and has the lowest sum of weights among all the trees that can be formed from the graph.
How it works
It works with three steps:
- Sort all the edges from the lowest weight to the highest.
- Select an edge with the lowest weight that doesn’t make a cycle, and add it to a spanning tree.
- Go on to the next edge and keep adding the others under the condition.
Union-Find
Checking if it makes a cycle, any minimum spanning tree algorithm revolves around. The Union-Find algorithm is the most commonly used, which divides the vertices into clusters and allows us to check if two vertices belong to the same cluster or not and hence decide whether adding an edge creates a cycle.
