用java语言Prim 和 Kruskal 算法及其测试实现

Prim算法实现：

public class PrimAlgorithm {
    private static final int INF = Integer.MAX_VALUE;
    private int[] lowCost;
    private int[] closest;
    private boolean[] visited;
    private int[][] graph;
    private int numVertices;

    public PrimAlgorithm(int[][] graph) {
        this.graph = graph;
        this.numVertices = graph.length;
        this.lowCost = new int[numVertices];
        this.closest = new int[numVertices];
        this.visited = new boolean[numVertices];
        Arrays.fill(lowCost, INF);
        Arrays.fill(closest, -1);
        Arrays.fill(visited, false);
    }

    public void run() {
        // 初始化起点
        int start = 0;
        lowCost[start] = 0;
        closest[start] = -1;

        // 执行 n-1 次，每次选取一个最近的节点加入生成树
        for (int i = 0; i < numVertices - 1; i++) {
            int minCost = INF;
            int next = -1;
            for (int j = 0; j < numVertices; j++) {
                if (!visited[j] && lowCost[j] < minCost) {
                    minCost = lowCost[j];
                    next = j;
                }
            }

            visited[next] = true;

            // 更新最近的节点
            for (int j = 0; j < numVertices; j++) {
                int cost = graph[next][j];
                if (!visited[j] && cost < lowCost[j]) {
                    lowCost[j] = cost;
                    closest[j] = next;
                }
            }
        }
    }

    public void printMST() {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < numVertices; i++) {
            System.out.println(closest[i] + " - " + i + "\t" + graph[i][closest[i]]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, 3, INF, INF},
                {2, 0, INF, 4, INF},
                {3, INF, 0, 1, 5},
                {INF, 4, 1, 0, 6},
                {INF, INF, 5, 6, 0}
        };

        PrimAlgorithm prim = new PrimAlgorithm(graph);
        prim.run();
        prim.printMST();
    }
}

Kruskal算法实现：

public class KruskalAlgorithm {
    private static final Comparator<int[]> edgeComparator = Comparator.comparingInt(a -> a[2]);
    private int[][] graph;
    private int numVertices;
    private int numEdges;
    private int[] parent;
    private int[] rank;

    public KruskalAlgorithm(int[][] graph) {
        this.graph = graph;
        this.numVertices = graph.length;
        this.numEdges = 0;
        for (int i = 0; i < numVertices; i++) {
            for (int j = i + 1; j < numVertices; j++) {
                if (graph[i][j] != 0) {
                    numEdges++;
                }
            }
        }
        this.parent = new int[numVertices];
        this.rank = new int[numVertices];
        Arrays.fill(parent, -1);
    }

    private int find(int v) {
        if (parent[v] == -1) {
            return v;
        }
        return parent[v] = find(parent[v]);
    }

    private void union(int v1, int v2) {
        int root1 = find(v1);
        int root2 = find(v2);
        if (root1 != root2) {
            if (rank[root1] < rank[root2]) {
                parent[root1] = root2;
            } else if (rank[root1] > rank[root2]) {
                parent[root2] = root1;
            } else {
                parent[root2] = root1;
                rank[root1]++;
            }
        }
    }

    public void run() {
        int[][] edges = new int[numEdges][3];
        int index = 0;
        for (int i = 0; i < numVertices; i++) {
            for (int j = i + 1; j < numVertices; j++) {
                if (graph[i][j] != 0) {
                    edges[index++] = new int[]{i, j, graph[i][j]};
                }
            }
        }
        Arrays.sort(edges, edgeComparator);

        int numEdgesSelected = 0;
        int[][] mst = new int[numVertices - 1][2];
        for (int i = 0; i < numEdges; i++) {
            int[] edge = edges[i];
            int v1 = edge[0];
            int v2 = edge[1];
            int weight = edge[2];
            if (find(v1) != find(v2)) {
                union(v1, v2);
                mst[numEdgesSelected][0] = v1;
                mst[numEdgesSelected][1] = v2;
                numEdgesSelected++;
                if (numEdgesSelected == numVertices - 1) {
                    break;
                }
            }
        }
        printMST(mst);
    }

    private void printMST(int[][] mst) {
        System.out.println("Edge \tWeight");
        for (int i = 0; i < numVertices - 1; i++) {
            System.out.println(mst[i][0] + " - " + mst[i][1] + "\t" + graph[mst[i][0]][mst[i][1]]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 2, 3, 0, 0},
                {2, 0, 0, 4, 0},
                {3, 0, 0, 1, 5},
                {0, 4, 1, 0, 6},
                {0, 0, 5, 6, 0}
        };

        KruskalAlgorithm kruskal = new KruskalAlgorithm(graph);
        kruskal.run();
    }
}