最小生成树(Prim算法、Kruskal算法)：国防部长PIPI、信使PIPI

最小生成树(Prim算法、Kruskal算法)

  给定一个无向图，如果它的某个子图包含图中所有顶点且是为一棵树，那么这棵树就叫做生成树。如果边上有权值，那么使得边权之和最小的生成树叫做最小生成树。
  求解最小生成树主要有两个算法，Kruskal算法和Prim算法。

Prim算法

  Prim算法和dijkstra算法十分相似，都是从某个顶点出发不断添加边的算法，同样也利用了贪心的思想。首先我们假设有一棵只包含一个顶点v的树T，然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加入到T中。不断进行这个操作就可以得到最小生成树了。
  举个例子，若一个图的初始状态如下所示，我们从v1开始，利用Prim算法获取该图的最小生成树

  首先，树中只有v1一个结点，选取与树相连的最短边，为v1和v3相连的边，将v3加入树中：

  接下来，v6和v3相连的边为与树相连的最短边，将v6加入树中：

  同理，我们可以按上述规则得到最终状态为：

  上述过程即为prim算法的流程，prim算法的模板如下：
  我们使用cost[]数组表示节点离生成树的距离，cost[i] = j即表示i号节点以权值为j的边连入生成树。使用visit[]数组标记节点是否已经加入生成树中。使用邻接矩阵int[][] distance来表示图，distance[i][j]表示i号节点和j号节点间的直接路径距离，若它们不相连，则为INF，distance[i][i] = 0。我们从1号节点开始进行Prim算法流程，初始时1号节点已经加入生成树，visit[1] = true，cost[i] = distance[1][i]
  我们每次需要贪心地选取生成树T和其他顶点之间相连的最小权值的边，并把它加入到T中，即找到离生成树距离最近的结点，也就是找到cost[]数组中的最小值对应的下标。我们一共需要找到除1号节点外的所有点，设总结点数为n，则我们需要进行n – 1次循环，这就是算法的最外层循环。
  找到离生成树距离最近的结点k后，我们将其加入生成树T中，生成树中有了新节点，那么其他结点距生成树的距离将发生变化，我们需要更新cost[]数组。若结点k到其他未加入生成树的结点的距离小于cost[]数组中记录的距离，我们更新cost[]数组
  prim算法的时间复杂度为O(n ^ 2)，n为图中的结点数

    static final int INF = 100000000;
    // cost[i]表示 i 号结点离生成树的距离
    static int[] cost = new int[105];
    // visit数组标记节点是否已经加入生成树T中
    static boolean[] visit = new boolean[105];
    // 邻接矩阵，用于表示两节点间的直接路径距离，若不相连，则为INF
    static int[][] distance = new int[105][105];
    static void prim(int n) {
        int i, k, p, min;
        for (i = 2;i <= n;i++) {
            cost[i] = distance[1][i];
        }
        visit[1] = true;
        for (i = 2;i <= n;i++) {
            min = INF;
            k = 1;
            // 找未纳入生成树T的，离生成树距离最近的节点
            for (p = 2;p <= n;p++) {
                if (!visit[p] && cost[p] < min) {
                    min = cost[p];
                    k = p;
                }
            }
            // 将该节点加入最小生成树中
            visit[k] = true;
            // 更新结点离生成树的距离
            for (p = 2;p <= n;p++) {
                if (!visit[p] && distance[k][p] < cost[p]) {
                    cost[p] = distance[k][p];
                }
            }
        }
    }

Kruskal算法

  Kruskal算法同样利用了贪心的思想，它会贪心地选择权值最小的边。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于生成树，那么就选择这条边加入生成树，直到所有的点都在生成树中为止。将生成树看成一个集合，上面这句话的意思就是若当前遍历边的两个端点不属于同一集合，那么就将它们所属的两个子集合并，直到所有的点都属于同一个集合为止。维护点与点之间的连通性和点集合并的操作我们可以借助并查集很方便地完成。
  Kruskal算法通过两点保证了正确性:
  （1）按边权从小到大加入边，保证了最小。
  （2）每次加边都不会产生环，保证了最后生成的是一棵树。
  Kruskal适合点多边少的图，复杂度为|E|log|E|，只和边有关。

  使用Prim算法介绍中相同的例子，Kruskal算法的执行过程为：
  首先，选择最短边，两端结点为1,3，将该边加入生成树

  然后，继续选择最短边，两端结点为4,6，不在生成树中，将该边加入生成树

  同理，我们可以按上述规则得到最终状态为：

  Kruskal算法模板如下：

    // 并查集数组
    static int[] father = new int[102];
    // 存储边的list
    static ArrayList<Edge> array = new ArrayList<>();
    // 对边按权值从小到大排序
    static {
        Collections.sort(array, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if (o1.distance > o2.distance) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });
    }
    // nodeNum表示图中节点的个数,在这里用kruskal算法返回最小生成树边权值之和ans
    static int kruskal(int nodeNum) {
        // 用count表示已选取加入生成树的边的数目
        int i, count = 0, from, to, ans = 0;
        // 初始时，每个结点对应一个集合
        for (i = 0;i < nodeNum;i++) {
            father[i] = i;
        }
        // 遍历所有边
        for (i = 0;i < array.size();i++) {
            from = array.get(i).from;
            to = array.get(i).to;
            // 使用并查集判断该边的两端点是否属于同一集合，若不属于同一集合，则进行合并,即将该边加入生成树，count++
            if (find(from) != find(to)) {
                union(from, to);
                count++;
                ans += array.get(i).distance;
                // 若已加入节点数 - 1条边，最小生成树便已经构建完成，返回权值之和
                if (count == nodeNum - 1) {
                    return ans;
                }
            }
        }
        return ans;
    }

    // 并查集的合并操作
    static void union(int from, int to) {
        father[find(from)] = father[find(to)];
    }

    // 并查集的查找操作
    static int find(int node) {
        if (node == father[node]) {
            return node;
        }
        return father[node] = find(father[node]);
    }

    // 表示边的类
    class Edge {
        public int from;
        public int to;
        public int distance;

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

问题1：

思路：

  将哨所看成图中的结点，通讯半径看成结点之间的边权值。我们需要使所有哨所互相之间可达，也就是说我们要构造一颗生成树，树中包含所有结点，为了使通讯半径最小，我们需要使生成树中权值最大的边的权最小。而根据最小生成树的性质，所有权值最小的边一定会出现在任何一个最小生成树中，因此该题被转化为了求最小生成树中的最大边权
  首先先使用邻接矩阵建图，我们求出每个哨所到其他哨所间的距离，distance[i][j]表示i号哨所与j号哨所之间的距离，然后跑一遍最小生成树算法，用一个变量ans记录最小生成树的最大边即可。可以使用Prim算法来解决。

需注意的地方：

• 注意最后输出答案时，使用System.out.printf("%.2f\n", prim(n, ans));，换行符\n一定要加

代码：

import java.util.*;

public class Main {
    static final double INF = 100000000.0;
    static double[] cost = new double[105];
    static boolean[] visit = new boolean[105];
    static double[][] distance = new double[105][105];
    static double[] xArray = new double[105];
    static double[] yArray = new double[105];
    public static void main(String[] args) {
        int n, i, j;
        double ans;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            n = scanner.nextInt();
            ans = 0;
            for (i = 1;i <= n;i++) {
                xArray[i] = scanner.nextDouble();
                yArray[i] = scanner.nextDouble();
            }
            for (i = 1;i <= n;i++) {
                Arrays.fill(distance[i], INF);
            }
            for (i = 1;i <= n;i++) {
                for (j = 1;j <= n;j++) {
                    distance[i][j] = Math.sqrt((xArray[i] - xArray[j]) * (xArray[i] - xArray[j]) + (yArray[i] - yArray[j]) * (yArray[i] - yArray[j]));
                    distance[j][i] = distance[i][j];
                }
            }
            Arrays.fill(visit, false);
            System.out.printf("%.2f\n", prim(n, ans));
        }

    }

    static double prim(int n, double ans) {
        int i, k, p;
        double min;
        for (i = 2;i <= n;i++) {
            cost[i] = distance[1][i];
        }
        visit[1] = true;
        for (i = 2;i <= n;i++) {
            min = INF;
            k = 1;
            for (p = 2;p <= n;p++) {
                if (!visit[p] && cost[p] < min) {
                    min = cost[p];
                    k = p;
                }
            }
            visit[k] = true;
            ans = Math.max(ans, min);
            for (p = 2;p <= n;p++) {
                if (!visit[p] && distance[k][p] < cost[p]) {
                    cost[p] = distance[k][p];
                }
            }
        }
        return ans;
    }

}

问题2

思路：

  该题是一个明显的要用bfs的题，但我们如果只用bfs，能否求出答案呢？我们若从升华楼（C）作为起点进行bfs，能得到它到其他教学楼的最短距离，但我们也可以从某个教学楼到另一个教学楼，有可能这种路线最短，因此我们要进行多次bfs，求出每个教学楼到其他教学楼的最短距离。但有了这些距离值后，我们还是不好求解问题。这时我们需要转换思维，题目给出的问题是体现在矩阵上的，我们把它转换成图上的问题。将教学楼当成图上的结点，经过上述多次bfs的过程，我们相当于构建了一个图，那么原问题便转换成了在我们构建的图中求一个子图，该子图包含图中所有结点（即教学楼），且边权值之和最小，这很明显就是要求出最小生成树了。
  因此我们需使用多次bfs + 最小生成树来求解该问题，这里我们使用Kruskal算法

需注意的地方：

• 本题思路较易理解，但代码量较多，我们首先需要从输入中提取出所有教学楼结点将其保存到数组中，之后遍历数组进行多次bfs，为了避免重复对visit标记数组进行重置，我们可以使用当前遍历结点的编号k来做标记，若visit[i][j] == k，即表示(i,j)已被访问。
• 在bfs过程中，我们每找到一条教学楼到教学楼的边，就将该边加入到一个list中，以便之后对该list进行排序并使用Kruskal算法
• 注意在并查集的合并集合操作中，一定是将一个集合的根节点挂到另一个集合的根节点上，而不是用子节点去挂，这样会出现问题，可能会丢失父节点的信息

代码：

import java.util.*;

public class Main {
    static int[] father = new int[102];
    static int[][] map = new int[102][102];
    static int[][] visit = new int[102][102];
    static Node[] building = new Node[102];
    static ArrayList<Edge> array = new ArrayList<>();
    static int[][] face = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static LinkedList<Node> q = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n, i, j, ans = 0, number = 1;
        StringBuilder stringBuilder = new StringBuilder();
        char ch;
        n = scanner.nextInt();
        // 节点编号表示C或c,-1表示不能走#,0表示能走'.'
        for (i = 0;i < n;i++) {
            stringBuilder.delete(0, stringBuilder.length());
            stringBuilder.append(scanner.next());
            for (j = 0;j < n;j++) {
                ch = stringBuilder.charAt(j);
                if (ch == 'C' || ch == 'c') {
                    map[i][j] = number;
                    building[number] = new Node(i, j, 0);
                    number++;
                } else if (ch == '#') {
                    map[i][j] = -1;
                } else {
                    map[i][j] = 0;
                }
            }
        }
        for (i = 1;i < number;i++) {
            q.add(building[i]);
            visit[building[i].x][building[i].y] = i;
            bfs(i, n);
        }
        Collections.sort(array, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if (o1.distance > o2.distance) {
                    return 1;
                } else {
                    return -1;
                }
            }
        });
        System.out.println(kruskal(ans, number));
    }

    static void bfs(int number, int n) {
        Node top;
        int x, y, i, step;
        while (!q.isEmpty()) {
            top = q.pop();
            step = top.step;
            for (i = 0;i < 4;i++) {
                x = top.x + face[i][0];
                y = top.y + face[i][1];
                if (x < 0 || x >= n || y < 0 || y >= n || visit[x][y] == number || map[x][y] == -1) {
                    continue;
                }
                visit[x][y] = number;
                q.add(new Node(x, y, step + 1));
                if (map[x][y] > 0) {
                    array.add(new Edge(number, map[x][y], step + 1));
                }
            }
        }
    }

    static int kruskal(int ans, int number) {
        int i, count = 0, from, to;
        for (i = 1;i < number;i++) {
            father[i] = i;
        }
        for (i = 0;i < array.size();i++) {
            from = array.get(i).from;
            to = array.get(i).to;
            if (find(from) != find(to)) {
                union(from, to);
                count++;
                ans += array.get(i).distance;
                if (count == number - 2) {
                    return ans;
                }
            }
        }
        return ans;
    }

    static void union(int from, int to) {
        father[find(from)] = father[find(to)];
    }

    static int find(int node) {
        if (node == father[node]) {
            return node;
        }
        return father[node] = find(father[node]);
    }
}

class Node {
    public int x;
    public int y;
    public int step;

    public Node(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}

class Edge {
    public int from;
    public int to;
    public int distance;

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