最小生成树之Prim算法

1public class Main {
2
3    private static final int INF = Integer.MAX_VALUE;
4
5    public static void main(String[] args) {
6        int[][] map = {
7                {0, 4, 5, INF, INF, INF},
8                {4, 0, 2, INF, INF, INF},
9                {5, 2, 0, 3, 5, 2},
10                {INF, INF, 3, 0, INF, 1},
11                {INF, INF, 5, INF, 0, 4},
12                {INF, INF, 2, 1, 4, 0}
13        };
14        System.out.println(prim(map));
15    }
16
17    /**
18     * prim算法求最小生成树
19     *
20     * @param map 图，邻接矩阵表示
21     */
22    public static int prim(int[][] map) {
23        int sum = 0;
24        /**
25         * 是否已经加入到树中
26         */
27        boolean[] visited = new boolean[map.length];
28        /**
29         * 从第一个顶点开始
30         */
31        visited[0] = true;
32        /**
33         * 当前已选择顶点的数量
34         */
35        int count = 1;
36        while (count < map.length) {
37            int cost = INF;
38            int vertex = 0;
39            /**
40             * 查找与已加入到树中的顶点最近且不在树中的顶点
41             */
42            for (int i = 0; i < map.length; i++) {
43                if (!visited[i]) {
44                    continue;
45                }
46                for (int j = 0; j < map.length; j++) {
47                    /**
48                     * 已经是树中的顶点或者和树中顶点不相邻，跳过
49                     */
50                    if (visited[j] || map[i][j] == INF) {
51                        continue;
52                    }
53                    if (cost > map[i][j]) {
54                        cost = map[i][j];
55                        vertex = j;
56                    }
57                }
58            }
59            sum += cost;
60            visited[vertex] = true;
61            count++;
62        }
63        return sum;
64    }
65}