Kruskal’s algorithm is a popular algorithm used to find the Minimum Spanning Tree of a connected weighted graph. It is a greedy algorithm that works by selecting the edges of the graph in ascending order of their weights and adding them to the minimum spanning tree if they do not create a cycle. In this article, we will discuss Kruskal’s algorithm in detail and provide code snippets and examples to help you understand it better.

Understanding Kruskal’s Algorithm

Before we dive into the algorithm, let’s first define some terms:

• Minimum Spanning Tree (MST): A tree that spans all the vertices of a connected weighted graph with the minimum possible total edge weight.
• Weighted Graph: A graph in which each edge is assigned a weight or cost.
• Edge: A connection between two vertices in a graph.
• Vertex: A node in a graph.

Now let’s see how Kruskal’s algorithm works:

1. Sort all the edges of the graph in ascending order of their weights.
2. Initialize an empty set to store the minimum spanning tree.
3. Iterate through all the edges in the sorted order.
4. If adding the current edge to the minimum spanning tree does not create a cycle, add it to the minimum spanning tree.
5. Repeat steps 3 and 4 until all the vertices are included in the minimum spanning tree.

The algorithm works by selecting the edges with the smallest weights first and adding them to the minimum spanning tree. If adding an edge creates a cycle, it is discarded. The algorithm continues until all the vertices are included in the minimum spanning tree.

Implementing Kruskal’s Algorithm in Java

Let’s now see how we can implement Kruskal’s algorithm in Java. We will use the following classes:

• Edge: A class to represent an edge in the graph.
• Graph: A class to represent the graph.
• Kruskal: A class to implement Kruskal’s algorithm.

Here is the code for the Edge class:

class Edge implements Comparable {
    int src, dest, weight;
 
    public int compareTo(Edge edge) {
        return this.weight - edge.weight;
    }
}

The Edge class has three fields: src (source vertex), dest (destination vertex), and weight (edge weight). It also implements the Comparable interface to enable sorting of edges based on their weights.

Here is the code for the Graph class:

class Graph {
    int V, E;
    Edge[] edges;
 
    Graph(int v, int e) {
        V = v;
        E = e;
        edges = new Edge[E];
        for (int i = 0; i 

The Graph class has two fields: V (number of vertices) and E (number of edges). It also has an array of edges to store the edges of the graph.

Here is the code for the Kruskal class:

class Kruskal {
    int V, E;
    Edge[] edges;
 
    Kruskal(Graph graph) {
        V = graph.V;
        E = graph.E;
        edges = graph.edges;
    }
 
    int find(int[] parent, int i) {
        if (parent[i] == i) {
            return i;
        }
        return find(parent, parent[i]);
    }
 
    void union(int[] parent, int[] rank, int x, int y) {
        int xroot = find(parent, x);
        int yroot = find(parent, y);
 
        if (rank[xroot]  rank[yroot]) {
            parent[yroot] = xroot;
        } else {
            parent[yroot] = xroot;
            rank[xroot]++;
        }
    }
 
    void kruskalMST() {
        Edge[] result = new Edge[V];
        int[] parent = new int[V];
        int[] rank = new int[V];
 
        for (int i = 0; i 

The Kruskal class has three fields: V (number of vertices), E (number of edges), and edges (array of edges). It also has three methods:

• find: A method to find the parent of a vertex in the union-find data structure.
• union: A method to perform union operation on two vertices in the union-find data structure.
• kruskalMST: A method to implement Kruskal’s algorithm and print the minimum spanning tree.

The find method uses the path compression technique to find the parent of a vertex in the union-find data structure. The union method performs the union operation on two vertices in the union-find data structure using the rank heuristic to maintain the balance of the tree. The kruskalMST method implements Kruskal’s algorithm by iterating through all the edges in the sorted order and adding them to the minimum spanning tree if they do not create a cycle.

Example

Let’s now see an example of how Kruskal’s algorithm works. Consider the following graph:

We will use Kruskal’s algorithm to find the minimum spanning tree of this graph. First, we sort all the edges in ascending order of their weights:

(0, 1, 4)
(0, 7, 8)
(1, 2, 8)
(1, 7, 11)
(2, 3, 7)
(2, 8, 2)
(2, 5, 4)
(3, 4, 9)
(3, 5, 14)
(4, 5, 10)
(5, 6, 2)
(6, 7, 1)
(6, 8, 6)
(7, 8, 7)

We then initialize an empty set to store the minimum spanning tree:

Minimum Spanning Tree:

We then iterate through all the edges in the sorted order:

(0, 1, 4)
(0, 7, 8)
(1, 2, 8)
(1, 7, 11)
(2, 3, 7)
(2, 8, 2)
(2, 5, 4)
(3, 4, 9)
(3, 5, 14)
(4, 5, 10)
(5, 6, 2)
(6, 7, 1)
(6, 8, 6)
(7, 8, 7)

We add the first edge (0, 1, 4) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4

We then add the next edge (0, 7, 8) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1

We then add the next edge (1, 2, 8) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1
1 - 2: 8

We then add the next edge (2, 3, 7) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1
1 - 2: 8
2 - 3: 7

We then add the next edge (2, 8, 2) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1
1 - 2: 8
2 - 3: 7
2 - 8: 2

We then add the next edge (2, 5, 4) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1
1 - 2: 8
2 - 3: 7
2 - 8: 2
2 - 5: 4

We then add the next edge (5, 6, 2) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1
1 - 2: 8
2 - 3: 7
2 - 8: 2
2 - 5: 4
5 - 6: 2

We then add the next edge (6, 8, 6) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1
1 - 2: 8
2 - 3: 7
2 - 8: 2
2 - 5: 4
5 - 6: 2
6 - 8: 6

We then add the last edge (7, 8, 7) to the minimum spanning tree:

Minimum Spanning Tree:
0 - 1: 4
6 - 7: 1
1 - 2: 8
2 - 3: 7
2 - 8: 2
2 - 5: 4
5 - 6: 2
6 - 8: 6
7 - 8: 7

Thus, the minimum spanning tree of the graph is:

Conclusion

Kruskal’s algorithm is a popular algorithm used to find the minimum spanning tree of a connected weighted graph. It is a greedy algorithm that works by selecting the edges of the graph in ascending order of their weights and adding them to the minimum spanning tree if they do not create a cycle. In this article, we discussed Kruskal’s algorithm in detail and provided code snippets and examples to help you understand it better.

Thank you for reading!

Related Articles:

• No related articles found.

The post Kruskal’s Algorithm: Finding the Minimum Spanning Tree appeared first on Java Master.