Kruskal's Algorithm

Kruskal's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds a subset of its edges that forms a tree including every vertex, with the minimum possible total edge weight.

How Kruskal's Algorithm Works

Kruskal's algorithm begins with the edges of lowest weight and continues adding edges until the target is reached. The following steps are applied in sequence:

1. All edges are sorted in ascending order of weight.

2. The edge with the lowest weight is selected and added to the spanning tree. If adding this edge creates a cycle, it is rejected.

3. Edges are added continuously until all vertices are included.

Example of Kruskal's Algorithm

1- A weighted graph is constructed.

2- The edge with the minimum weight is selected; if there are multiple such edges, any one is chosen.

3- The next lowest-weight edge is selected and added.

4- The next shortest edge that does not form a cycle is selected and added.

5- The next shortest edge that does not form a cycle is selected and added.

6- All steps are repeated until a spanning tree is formed.

Kruskal's Algorithm Pseudocode

Kruskal's Algorithm Explained in Java