最小生成树问题java贪心prim算法输出树边权重

Prim算法是一种贪心算法，用于求解最小生成树问题。在Java中实现Prim算法，可以通过以下步骤输出树边权重：

1. 定义一个二维数组graph表示图的邻接矩阵，其中graph[i][j]表示节点i和节点j之间的边权重。

2. 定义一个一维数组dist表示每个节点到最小生成树的距离，初始值为正无穷大。

3. 定义一个一维数组parent表示每个节点在最小生成树中的父节点，初始值为-1。

4. 选择一个起始节点start，将dist[start]设置为。

5. 重复以下步骤，直到所有节点都被加入最小生成树：

a. 找到当前距离最小的节点min，将其加入最小生成树。

b. 更新min的邻居节点的距离和父节点，如果新的距离小于原来的距离，则更新dist和parent数组。

6. 输出最小生成树的边权重，可以通过遍历parent数组来得到每个节点在最小生成树中的父节点，从而得到每条边的权重。

下面是一个简单的Java代码实现：

public class PrimAlgorithm {
    public static void prim(int[][] graph) {
        int n = graph.length;
        int[] dist = new int[n];
        int[] parent = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
        dist[] = ;
        for (int i = ; i < n; i++) {
            int min = findMin(dist, visited);
            visited[min] = true;
            for (int j = ; j < n; j++) {
                if (!visited[j] && graph[min][j] < dist[j]) {
                    dist[j] = graph[min][j];
                    parent[j] = min;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            System.out.println(parent[i] + " - " + i + ": " + graph[i][parent[i]]);
        }
    }

    private static int findMin(int[] dist, boolean[] visited) {
        int min = -1;
        for (int i = ; i < dist.length; i++) {
            if (!visited[i] && (min == -1 || dist[i] < dist[min])) {
                min = i;
            }
        }
        return min;
    }
}

在上面的代码中，findMin方法用于找到当前距离最小的节点，prim方法用于实现Prim算法，输出最小生成树的边权重。