There are 10 vertices and each vertex has at least one edge connecting to it. We’ll look through the edges until we find the least costly edge. We can quickly see that edge F-I has the least costly edge, so we’ll include it first.

Next, there are two edges with a weight of 2: C-D and G-H. Neither of them forms a cycle, so we’ll select one of them: C-D.

The next least costly edge is edge G-H. Since it doesn’t form a cycle, we’ll include it into the MST.

The next least costly weight is 3; there are 2 edges with a cost of 3: edges A-C and I-J. We’ll choose edge A-C and include it into the formation of the MST since it comes next lexically.

Edge I-J is also included since it’s not involved in the construction of any cycles in the graph.

The next least costly edge weight is 4. There are two edges with a weight of 4: edges B-D and F-J. Edge B-D is added to the MST formation.

Although edge F-J does have the next least costly edge, it cannot be added to the list since it creates a cycle. This is what the cycle would look like if we added that edge.

 

We’ll remove that edge and continue with the creation of the MST.

 

There are two possibilities next. We can either add edge C-G or F-H. We’ll add the edge C-G since it comes next alphabetically and does not form a cycle.

Edge H-F can also be added since it’s not part of a cycle.

Only one more vertex needs to be added to the MST: vertex E. The next lowest edge weight is 6. Edge E-F contains a weight of 6. Once added, it does not form a cycle.

Kruskal’s algorithm ends since all vertices have been added to the MST.

 

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Algorithm and many more.