用java实现prim算法

以下是Java实现Prim算法的示例代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class PrimAlgorithm {
    private static final int INF = 0x3f3f3f3f; // 无穷大
    private int[][] graph; // 图的邻接矩阵
    private int vertexCount; // 图的顶点数

    public PrimAlgorithm(int[][] graph, int vertexCount) {
        this.graph = graph;
        this.vertexCount = vertexCount;
    }

    public void prim() {
        int[] dist = new int[vertexCount]; // 存储每个顶点到最小生成树的距离
        int[] parent = new int[vertexCount]; // 存储每个顶点在最小生成树中的父节点
        boolean[] visited = new boolean[vertexCount]; // 存储每个顶点是否已加入最小生成树

        Arrays.fill(dist, INF); // 初始距离为无穷大
        Arrays.fill(visited, false); // 初始状态下所有顶点都未加入最小生成树

        PriorityQueue<Node> minHeap = new PriorityQueue<>(); // 用小根堆存储每个顶点到最小生成树的距离
        dist[0] = 0; // 从第一个顶点开始构建最小生成树
        minHeap.offer(new Node(0, 0)); // 将第一个顶点加入小根堆

        while (!minHeap.isEmpty()) {
            Node node = minHeap.poll(); // 取出距离最小的顶点
            int u = node.vertex;

            if (visited[u]) { // 如果该顶点已加入最小生成树，则跳过
                continue;
            }

            visited[u] = true; // 将该顶点加入最小生成树

            for (int v = 0; v < vertexCount; v++) {
                if (graph[u][v] != INF && !visited[v] && graph[u][v] < dist[v]) { // 如果顶点v未加入最小生成树且边(u, v)比当前距离更短，则更新距离和父节点
                    dist[v] = graph[u][v];
                    parent[v] = u;
                    minHeap.offer(new Node(v, dist[v])); // 将顶点v加入小根堆
                }
            }
        }

        printMST(parent); // 输出最小生成树
    }

    private void printMST(int[] parent) {
        System.out.println("Minimum Spanning Tree:");
        for (int v = 1; v < vertexCount; v++) {
            System.out.println(parent[v] + " - " + v);
        }
    }

    private static class Node implements Comparable<Node> {
        int vertex;
        int distance;

        public Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(distance, other.distance);
        }
    }

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

        PrimAlgorithm prim = new PrimAlgorithm(graph, 5);
        prim.prim();
    }
}

输出结果为：

Minimum Spanning Tree:
0 - 1
1 - 2
0 - 3
1 - 4