Kruskal's algorithm for minimum-spanning-tree(mst)

Definition from Wikipedia

Basically, we use Kruskal's algorithm to find the minimum-spanning-tree(mst) from a weighted graph.

Here is an example from the book "Data structures and Algorithm Analysis in Java" by Mark Allen Weiss.

9.15
a. Find a minimum spanning tree for the graph in Figure 9.84 using both Prim’s and Kruskal’s algorithms.

We will use Kruskal's algorithm here.

Before we start, you should be familiar with the concept of Disjoint-set.


We first find a edge that has the minimum weight on the graph as a starting point. In this case, we've found (C,G) and (E,I). They both have a weight of 1.

We can choose either of them. Here, we choose (C,G) first. We union(C,G), which means we make them into one set. And then we find the next minimum weight edge, which is (E,I), and we do the same. Union(E,I). We have two sets so far, {C,G} and {E,I}

We repeat the above process.

(G,F), (B,E) and (E,H) all have weight of 2, so we can start from either one. 

We've examined all edges that have weight 2, so next we find the next minimum edge weight, which is three in this case

You can choose either of (B,A), (F,B),(F,I) because all of them have the weight of 3.

I'll choose (F,B) here.  Union the two sets. So we have one set now.{C,G,F,B,E,I,H}

The next edge you can choose from (F, I) and (B,A) because both of the edges weight are 3, but we cannot choose (F,I). Why? Because both F and I are in the same set. As a tree, they've already connected to each other.

We repeat the algorithm. and we find (A,D) weight(4)

(I,J) weight:7

Now, we've connected all vertices!

Our minimum-spanning-tree looks like this!

The minimum spanning tree is a list of edges:
(CG, GF, FB, BE, EI, IJ, EH, BA, AD)

I hope this is helpful!