Prims算法

Prims算法（普里姆算法）是一种用于解决最小生成树问题的贪心算法，与Kruskal算法类似，但是更加适合于稠密图。

算法步骤如下：

选取一个起始节点，并将其加入到最小生成树中。

找到连接已选择节点和未选择节点的权值最小的边，将其连接的未选择节点加入到最小生成树中。

重复步骤2，直到所有的节点都被加入到最小生成树中。

Prims算法和Dijkstras算法非常相似，都是通过维护一个优先队列来选择下一个节点，只是Dijkstras算法是基于路径长度来进行选择，而Prims算法是基于边的权值来进行选择。

以下是Prims算法的Java代码实现，其中使用了优先队列来维护边的权值：

import java.util.*;

class PrimsAlgorithm {
    private static final int INF = Integer.MAX_VALUE;

    public int getMinimumSpanningTree(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[0] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(-1, 0, 0)); // dummy edge

        int weight = 0;

        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            if (visited[e.to]) {
                continue;
            }
            visited[e.to] = true;
            weight += e.weight;
            for (int i = 0; i < n; i++) {
                if (i == e.to || visited[i]) {
                    continue;
                }
                if (graph[e.to][i] < dist[i]) {
                    dist[i] = graph[e.to][i];
                    pq.offer(new Edge(e.to, i, dist[i]));
                }
            }
        }

        return weight;
    }

    private static class Edge implements Comparable<Edge> {
        int from, to, weight;

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

        public int compareTo(Edge other) {
            return Integer.compare(weight, other.weight);
        }
    }
}

在上述代码中，getMinimumSpanningTree方法接受一个二维数组表示的图，返回最小生成树的权值和。其中，visited数组记录了已经加入最小生成树的节点，dist数组记录了每个节点到最小生成树的距离，pq是优先队列，按照边的权值进行排序。算法从起始节点开始遍历，每次选择权值最小的边并将其连接的未选择节点加入到最小生成树中，直到所有的节点都被加入到最小生成树中。