普利姆(prim)算法 java

普利姆(Prim)算法是一种用于求解最小生成树的算法，它的基本思想是从一个点开始，每次选择一个与当前生成树距离最近的点加入生成树中，直到生成树包含了所有的点。下面是Java实现的代码示例：

import java.util.*;

public class PrimAlgorithm {
    public static void prim(int[][] graph, int n) {
        int[] dist = new int[n]; // 存储当前生成树到每个点的最短距离
        boolean[] visited = new boolean[n]; // 标记每个点是否已经加入生成树
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化距离为无穷大
        dist[0] = 0; // 从第一个点开始构建生成树
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
                    dist[v] = graph[u][v];
                }
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += dist[i];
        }
        System.out.println("最小生成树的权值为：" + sum);
    }

    public static void main(String[] args) {
        int[][] graph = {{0, 1, 3, 0, 0},
                         {1, 0, 3, 6, 0},
                         {3, 3, 0, 4, 2},
                         {0, 6, 4, 0, 5},
                         {0, 0, 2, 5, 0}};
        prim(graph, 5);
    }
}