JAVA:实现Kruskal克鲁斯卡尔求连通网的最小生成树算法(附完整源码)

package com.thealgorithms.datastructures.graphs;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Kruskal {

    // Complexity: O(E log V) time, where E is the number of edges in the graph and V is the number of
    // vertices
    private static class Edge {

        private int from;
        private int to;
        private int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    private static void addEdge(HashSet<Edge>[] graph, int from, int to, int weight) {
        graph[from].add(new Edge(from, to, weight));
    }

    public static void main(String[] args) {
        HashSet<Edge>[] graph = new HashSet[7];
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new HashSet<>();
        }
        addEdge(graph, 0, 1, 2);
        addEdge(graph, 0, 2, 3);
        addEdge(graph, 0, 3, 3);
        addEdge(graph, 1, 2, 4);
        addEdge(graph, 2, 3, 5);
        addEdge(graph, 1, 4, 3);
        addEdge(graph, 2, 4, 1);
        addEdge(graph, 3, 5, 7);
        addEdge(graph, 4, 5, 8);
        addEdge(graph, 5, 6, 9);

        System.out.println("Initial Graph: ");
        for (int i = 0; i < graph.length; i++) {
            for (Edge edge : graph[i]) {
                System.out.println(i + " <-- weight " + edge.weight + " --> " + edge.to);
            }
        }

        Kruskal k = new Kruskal();
        HashSet<Edge>[] solGraph = k.kruskal(graph);

        System.out.println("\nMinimal Graph: ");
        for (int i = 0; i < solGraph.length; i++) {
            for (Edge edge : solGraph[i]) {
                System.out.println(i + " <-- weight " + edge.weight + " --> " + edge.to);
            }
        }
    }

    public HashSet<Edge>[] kruskal(HashSet<Edge>[] graph) {
        int nodes = graph.length;
        int[] captain = new int[nodes];
        // captain of i, stores the set with all the connected nodes to i
        HashSet<Integer>[] connectedGroups = new HashSet[nodes];
        HashSet<Edge>[] minGraph = new HashSet[nodes];
        PriorityQueue<Edge> edges = new PriorityQueue<>((Comparator.comparingInt(edge -> edge.weight)));
        for (int i = 0; i < nodes; i++) {
            minGraph[i] = new HashSet<>();
            connectedGroups[i] = new HashSet<>();
            connectedGroups[i].add(i);
            captain[i] = i;
            edges.addAll(graph[i]);
        }
        int connectedElements = 0;
        // as soon as two sets merge all the elements, the algorithm must stop
        while (connectedElements != nodes && !edges.isEmpty()) {
            Edge edge = edges.poll();
            // This if avoids cycles
            if (!connectedGroups[captain[edge.from]].contains(edge.to)
                    && !connectedGroups[captain[edge.to]].contains(edge.from)) {
                // merge sets of the captains of each point connected by the edge
                connectedGroups[captain[edge.from]].addAll(connectedGroups[captain[edge.to]]);
                // update captains of the elements merged
                connectedGroups[captain[edge.from]].forEach(i -> captain[i] = captain[edge.from]);
                // add Edge to minimal graph
                addEdge(minGraph, edge.from, edge.to, edge.weight);
                // count how many elements have been merged
                connectedElements = connectedGroups[captain[edge.from]].size();
            }
        }
        return minGraph;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95