Categories
Coding Byte

Graphs: Understanding Kruskal’s Algorithm

What is Kruskal’s algorithm?

Kruskal’s algorithm is used to find a minimum spanning forest or tree in an undirected graphs and connected graphs respectively. For graphs, minimum spanning trees are a subset of edges that form a tree which include all vertices, where the sum of all edges is kept to the smallest number possible.

How does Kruskal’s algorithm work? Example:

To wholly explain how Kruskal’s algorithm works, we will need to use an example, as in the image below:

Graph

The first step is implementing Kruskal’s algorithm, which I feel many people do not take into account, is removing any loops and parallel edges from the MST (minimum spanning tree). Thankfully, the graph above does not contain any of these. If, say, the graph had two edged moving from A to B, then that would be a parallel edge. We would eliminate the edge that has the higher cost from the MST. If the graph had an edge that originated from A and ended at A, that would be a loop which would need to be eliminated.

Next, we would sort all our edges from the lowest weight to the highest. Then we would take the edge with the lowest weight and add it as our first entrant to our MST. In the example above, this edge is AC, which has the lowest weight, 1.

Then we would continue adding the next smallest edges to our MST. If we find that that edge creates a cycle, we would eliminate it and move to the next one. From above, the next edge we would add is DF, with a weight of 2. Since this edge doesn’t create a loop, we’ll allow it.

Next, we’ll add edge BE, with an weight of 3. Next will be FC, with a weight of 4. Then we’ll move to consider either CD or CB, which both have a weight of 5. We’ll eliminate CD, however, because it creates a cycle.

The next set of edges are CE, EF and AB, which all have a weight of 6. These edges, however, won’t be considered. Why? First, because our edges above have already covered all the vertices and second, considering any of these will create a cycle, which we do not want.

We are left with following diagram as our MST:

Minimum Spanning Tree

Why is Kruskal considered “Greedy”?

Kruskal’s algorithm is considered to be greedy because in each step, the algorithm compares several weights and choose the lowest-weight available to it for the moment, as long as it does not form a cycle. This is a greedy step, as you have to choose only what is optimal at the moment.

By Wafula Lukorito

I am an engineer with a strong Computer Science foundation with practical experience in full-stack web design, building and maintaining REST APIs, creating Django and PHP backends, and designing educational JavaScript games. You can check out my work at https://lukorito.dev

Leave a Reply

Your email address will not be published. Required fields are marked *