Java code to implement Kruskal's algorithm

Kruskal algorithm

Kruskal algorithm is a greedy algorithm used to solve the minimum spanning tree problem. A minimum spanning tree is a spanning tree with the smallest sum of edge weights in a connected undirected graph. Kruskal's algorithm selects edges in order from small to large edge weights. When the selected edges do not form a cycle, they are added to the spanning tree. The specific implementation process is as follows:

• Sort all edges according to their edge weights from small to large.

• Select edges in turn. If the two endpoints of the selected edge are not in the same connected component, add this edge to the minimum spanning tree and merge the two endpoints into the same connected component.

• Until the minimum spanning tree contains all the vertices in the graph.

The advantage of the algorithm is that it only needs to pay attention to the weight of the edge and has nothing to do with the degree of the vertex, so it can also show better performance in dense graphs. At the same time, Kruskal's algorithm also has good scalability and can easily handle the minimum spanning forest problem in weighted graphs.

Execution process

• Sort all the edges according to their weights from small to large;

• Traverse each edge in turn, If the two nodes connected by this edge are not in the same connected component, add this edge to the spanning tree and merge the two nodes into one connected component;

• Repeat Step 2 Until all nodes are in the same connected component, the tree generated at this time is the minimum spanning tree.

During the implementation process, union-find sets are usually used to maintain connectivity to improve efficiency.

Code implementation

import java.util.*;

public class KruskalAlgorithm {
    
    // 定义边的数据结构
    class Edge implements Comparable {
        int src, dest, weight;
 
        public int compareTo(Edge edge) {
            return this.weight - edge.weight;
        }
    }
    
    // 并查集数据结构
    class Subset {
        int parent, rank;
    }
 
    int V, E; // V是顶点数，E是边数
    Edge edge[]; // 存储边的数组
 
    // 构造函数，初始化边和顶点数
    KruskalAlgorithm(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }
 
    // 查找父节点
    int find(Subset subsets[], int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }
 
    // 合并两个子集
    void union(Subset subsets[], int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
 
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }
 
    // 执行克鲁斯卡尔算法
    void kruskal() {
        Edge result[] = new Edge[V]; // 存储结果的数组
        int e = 0; // 表示result数组中的下标
 
        // 将边按照权重从小到大排序
        Arrays.sort(edge);
 
        // 创建V个子集
        Subset subsets[] = new Subset[V];
        for (int i = 0; i < V; ++i)
            subsets[i] = new Subset();
 
        // 初始化每个子集的父节点和秩
        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
 
        // 取E-1条边
        int i = 0;
        while (e < V - 1) {
            Edge next_edge = new Edge();
            next_edge = edge[i++];
 
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);
 
            // 如果两个节点不在同一个集合中，合并它们
            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
        }
 
        // 打印结果
        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i){
            System.out.println(result[i].src + " - " + result[i" - " + result[i].weight);
            return;
        }
        
        // 定义一个辅助函数，用于查找结点所在的集合 
        private int find(int parent[], int i) { 
            if (parent[i] == -1) 
                return i; 
            return find(parent, parent[i]); 
        }

        // 定义一个辅助函数，用于合并两个集合 
        private void union(int parent[], int x, int y) { 
            int xset = find(parent, x); 
            int yset = find(parent, y); 
            parent[xset] = yset; 
        } 
    }
}

The function uses the sort method of the Arrays class to sort the edges according to their weight from small to large. Then, the function traverses the sorted edges in sequence, and for each edge, uses the find function to find the root node of the set where its src and dest are located. If the root nodes are different, it means that the two sets are not connected and can be merged, and the edges are added to the result array of the minimum spanning tree. Finally, the function traverses the result array of the minimum spanning tree and outputs the starting point, end point and weight of each edge.

In this implementation, a method of quickly searching for sets is used, that is, using union search to achieve it. Each node has a parent array, where parent[i] represents the parent node of node i. If parent[i] == -1, node i is the root node. When searching for the set where the node is located, if the parent node of the current node is -1, it means that the node is the root node and is returned directly; otherwise, the set where the parent node is located is searched recursively. When merging two collections, find the root nodes of the two collections to be merged, and set the parent node of one root node to the index of the other root node, that is, merge the root node of one collection under the root node of the other collection. .

The time complexity of Kruskal's algorithm implemented in this way is O(ElogE), where E represents the number of edges in the graph. The main time cost lies in the process of sorting the edges. The space complexity is O(V E), where V represents the number of vertices in the graph. The main space overhead is to store the edges and parent arrays.

The above is the detailed content of Java code to implement Kruskal's algorithm. For more information, please follow other related articles on the PHP Chinese website!