使用Prim算法建立G的最小生成树 java

Prim算法是一种求解加权无向连通图的最小生成树的经典算法，可以用来找到一棵包含所有顶点的树，且树的总权值最小。下面是使用Java实现Prim算法建立G的最小生成树的示例代码：

import java.util.*;

public class PrimMST {

    private int V; // 图的顶点数
    private int[] parent; // 最小生成树的父节点
    private boolean[] visited; // 用于表示节点是否被访问过
    private int[][] graph; // 存储图的邻接矩阵

    public PrimMST(int[][] graph) {
        this.graph = graph;
        V = graph.length;
        parent = new int[V];
        visited = new boolean[V];
        Arrays.fill(parent, -1);
        Arrays.fill(visited, false);
    }

    // 使用Prim算法生成最小生成树
    public void prim() {
        PriorityQueue<Node> pq = new PriorityQueue<Node>(Comparator.comparing(Node::getWeight)); // 使用优先队列存储节点
        pq.add(new Node(0, 0)); // 将起始节点加入队列
        while (!pq.isEmpty()) {
            Node node = pq.poll(); // 取出队列中权值最小的节点
            int u = node.getIndex();
            if (visited[u])
                continue;
            visited[u] = true;
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !visited[v]) {
                    pq.add(new Node(v, graph[u][v])); // 将未访问的节点加入队列
                    if (parent[v] == -1) {
                        parent[v] = u; // 更新最小生成树的父节点
                    }
                }
            }
        }
        printMST();
    }

    // 打印最小生成树
    private void printMST() {
        System.out.println("Edge   Weight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "    " + graph[i][parent[i]]);
        }
    }

    // 节点对象，用于存储节点的索引和权值
    private class Node {
        private int index;
        private int weight;

        public Node(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }

        public int getIndex() {
            return index;
        }

        public int getWeight() {
            return weight;
        }
    }
}

这里使用了一个优先队列来存储节点，并按照节点的权值进行排序。在算法的实现中，首先将起始节点加入队列中，然后不断从队列中取出权值最小的节点，并将其标记为已访问过。接着遍历该节点的所有邻居，将未访问的邻居加入队列中，并更新最小生成树的父节点。最后打印出最小生成树的边和权值即可。