如何实现最小生成树算法？Prim算法实现

最小生成树算法是指在一个无向加权图中，找出一棵权值最小的生成树。常见的解决方案有两种：Prim算法和Kruskal算法。

Prim算法

Prim算法是一种贪心算法，它从一个任意的起点开始，逐渐扩展生成树中的节点。在每次扩展时，选择与生成树相连的边中，权值最小的那条边，并将其加入生成树中。

下面是Prim算法的Java实现：

import java.util.*;

public class Prim {
    public static List<int[]> minimumSpanningTree(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e[1]));
        queue.offer(new int[] {0, 0});
        List<int[]> edges = new ArrayList<>();
        while (!queue.isEmpty() && edges.size() < n - 1) {
            int[] edge = queue.poll();
            int u = edge[0], w = edge[1];
            if (!visited[u]) {
                visited[u] = true;
                edges.add(edge);
                for (int v = 0; v < n; v++) {
                    if (graph[u][v] != 0 && !visited[v]) {
                        queue.offer(new int[] {v, graph[u][v]});
                    }
                }
            }
        }
        return edges;
    }
}