图第二讲

本章继续介绍一些图相关的重要算法。

拓扑排序

课程表

共有 numCourses 门课可选，即为 0 到 numsCourses - 1。
给定数组 prerequisites，其中 prerequisites[i] = [a, b]，表示选修课程a之前必须选修b。
返回学完所有课程的学习顺序，如果有多种顺序，返回任意一种即可。如果不可能完成所有课程，返回空数组。

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]

本题是典型的拓扑排序问题，首先要解决有没有解的问题。
把每门课看做一个节点，必须先修的课伸出一条边指向后修的课，假如图中出现环，
比如选修a之前必须选修b,而选修b之前必须选修a，这样两门课都不可能修上，所以有环的图是一定没有拓扑排序的。
我们可以用深度搜索来查找有没有环，可以在代码中看到。有解的情况下，拓扑排序就是图的逆后序，即后序遍历反转。
以numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]为例。

上图的一个后序遍历为[3,1,2,0]，则逆后序为[0,2,1,3]。

// https://leetcode.cn/problems/course-schedule-ii/submissions/612543424
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        boolean[] visited = new boolean[numCourses];
        List<Integer> onStack = new ArrayList<>();
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                if (hasCycle(i, visited, onStack, graph)) {
                    return new int[]{};
                }
            }
        }

        Deque<Integer> topoOrder = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            visited[i] = false;
        }

        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                reversePost(i, visited, graph, topoOrder);
            }
        }

        int[] result = new int[topoOrder.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = topoOrder.pollFirst();
        }

        return result;
    }

    private boolean hasCycle(int i , boolean[] visited, List<Integer> onStack, List<List<Integer>> graph) {
        visited[i] = true;
        onStack.add(i);
        for (int desc : graph.get(i)) {
            if (!visited[desc]) {
                if (hasCycle(desc, visited, onStack, graph)) {
                    onStack.remove(onStack.size() - 1);
                    return true;
                }
            } else {
                if (onStack.contains(desc)) {
                    onStack.remove(onStack.size() - 1);
                    return true;
                }
            }
        }
        onStack.remove(onStack.size() - 1);
        return false;
    }

    private void reversePost(int i, boolean[] visited, List<List<Integer>> graph, Deque<Integer> topoOrder) {
        visited[i] = true;
        for (int desc : graph.get(i)) {
            if (!visited[desc]) {
                reversePost(desc, visited, graph, topoOrder);
            }
        }
        topoOrder.addFirst(i);
    }

最小生成树

连接所有点的最小费用

给定points数组，表示二维平面上的点，
点之间的距离为 曼哈顿距离：|x0 - x1| + |y0 - y1|。
返回构成一棵树的最小总费用，设点有n个，树的边有n - 1条，且没有环。

这里我们介绍Prime算法的即时版本，以数组[[0,0],[1,1],[1,0],[2,1]]为例。
首先我们将所有节点按是否在最小生成树中分为两个集合，数组distTo[i]记录点i到最小生成树中点的最小距离，初始为无穷大。

• 首先将点0放入生成树中，distTo[0]设为0，更新所有相邻节点的distTo值，选其中最小的边对应的点作为下一个加入生成树。
• 加入点2，更新distTo[1]为1，因为边(2,1)更短，同理更新distTo[3]为2，选取最小边(2,1)加入生成树。
• 加入点1，更新distTo[3]为1，将边(1,3)加入生成树。
• 加入点3，最小生成树形成，边长总和为1 + 1 + 1 = 3。

// https://leetcode.cn/problems/min-cost-to-connect-all-points/submissions/612678927
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        boolean[] marked = new boolean[n];
        Integer[] edgeTo = new Integer[n];
        int[] distTo = new int[n];
        int sum = 0;
        TreeSet<Integer> unmarkedNodes = new TreeSet<>((a, b) -> 
            distTo[a] != (distTo[b]) ? Integer.compare(distTo[a], distTo[b])
                : Integer.compare(a, b));
        distTo[0] = 0;
        edgeTo[0] = 0;
        unmarkedNodes.add(0);
        while (!unmarkedNodes.isEmpty()) {
            int minNode = unmarkedNodes.pollFirst();
            visit(minNode, marked, unmarkedNodes, points, edgeTo, distTo);
            sum += distTo[minNode];
        }

        return sum;
    }

    private void visit(int i, boolean[] marked, TreeSet<Integer> unmarkedNodes, int[][] points, Integer[] edgeTo, int[] distTo) {
        marked[i] = true;
        for (int j = 0; j < points.length; j++) {
            if (j != i && !marked[j]) {
                int dist = dist(points[i][0], points[i][1], points[j][0], points[j][1]);
                if (edgeTo[j] == null || dist < distTo[j]) {
                    edgeTo[j] = i;
                    if (unmarkedNodes.contains(j)) {
                        unmarkedNodes.remove(j);
                    }
                    distTo[j] = dist;
                    unmarkedNodes.add(j);
                }
            }
        }
    }


    private int dist(int x0, int y0, int x1, int y1) {
        return (int)(Math.abs(x1 - x0) + Math.abs(y1 - y0));
    }

注意TreeSet的比较器，TreeSet中存储的是节点序号，但是按distTo值排序，如果直接比较distTo的值，相等时会相互覆盖，
所以distTo相等时还需要比较节点序号，保证不同节点不会相互覆盖。
更新distTo值时，也要先删除TreeSet中对应的节点，更新完再插入，不然排序会混乱。

最短路径

这里限定为求解权值非负的有向图，因为如果存在负权重环（即权重和为负的环），就没有最短路径，因为每绕环走一圈都会减小总权重。
这里通过下图介绍dijkstra算法，求非负权重有向图(可包含环)的最短路径。

• 先将点0加入visited数组中，设置distTo[0]=0，对0的每条连接到未遍历点的边作松弛操作，即如果distTo[0]加上边的权重weight小于distTo[i]，i为另一个点，更新distTo[i]=distTo[0]+weight，这里distTo[1]和distTo[2]被更新，在数组中被标为黄色
• 选择distTo值最小的未遍历点加入visited数组，即点1，松弛点1的边，更新dist[2]和dist[3]
• 将点2加入visited数组，没有可松弛的边
• 将点3加入visited数组，distTo数组即点0到每个点的最短路径

// https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/submissions/612817157/
class Graph {
    private static class IndexPQ<V extends Comparable<V>> {
        V[] keys;
        int[] heap, rank;
        int size;
        public IndexPQ(int cap) {
            size = 0;
            keys = (V[])new Comparable[cap];
            heap = new int[cap];
            rank = new int[cap];
        }

        public void insert(int i, V v) {
            if (contains(i)) {
                return;
            }
            keys[i] = v;
            heap[size] = i;
            rank[i] = size;
            size++;
            swim(size - 1);
        }

        public boolean contains(int i) {
            return keys[i] != null;
        }

        public void change(int i, V v) {
            if (!contains(i)) {
                return;
            }
            keys[i] = v;
            sink(rank[i]);
            swim(rank[i]);
        }

        public int delMin() {
            int min = heap[0];
            swap(0, size - 1);
            size--;
            sink(0);

            keys[min] = null;
            return min;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        private void swim(int i) {
            while (i != 0 && keys[heap[i]].compareTo(keys[heap[(i - 1)/ 2]]) < 0) {
                swap(i, (i - 1) / 2);
                i = (i - 1) / 2;
            }
        }

        private void sink(int i) {
            while (i + i + 1 < size) {
                int next = i + i + 1;
                if (next + 1 < size && keys[heap[next + 1]].compareTo(keys[heap[next]]) < 0) {
                    next++;
                }
                if (keys[heap[i]].compareTo(keys[heap[next]]) <= 0) {
                    return;
                }
                swap(i, next);
                i = next;
            }
        }

        private void swap(int i, int j) {
            int tmp = heap[i];
            heap[i] = heap[j];
            heap[j] = tmp;
            rank[heap[i]] = i;
            rank[heap[j]] = j;
        }
    }

    private List<List<int[]>> adjList;

    public Graph(int n, int[][] edges) {
        adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            addEdge(edge);
        }
    }
    
    public void addEdge(int[] edge) {
        adjList.get(edge[0]).add(new int[]{edge[1], edge[2]});
    }
    
    public int shortestPath(int node1, int node2) {
        Integer[] distTo = new Integer[adjList.size()];
        distTo[node1] = 0;
        for (int i = 0; i < distTo.length; i++) {
            distTo[i] = i == node1 ? 0 : Integer.MAX_VALUE;
        }
        IndexPQ<Integer> indexPQ = new IndexPQ<>(adjList.size());
        indexPQ.insert(node1, 0);
        while (!indexPQ.isEmpty()) {
            int minNode = indexPQ.delMin();
            if (minNode == node2) {
                return distTo[node2];
            }
            relax(minNode, adjList, distTo, indexPQ);
        }

        return -1;
    }

    private void relax(int node, List<List<int[]>> adjList, Integer[] distTo,  IndexPQ<Integer> indexPQ) {
        for (int[] edge : adjList.get(node)) {
            if (distTo[edge[0]] > distTo[node] + edge[1]) {
                distTo[edge[0]] = distTo[node] + edge[1];
                if (indexPQ.contains(edge[0])) {
                    indexPQ.change(edge[0], distTo[edge[0]]);
                } else {
                    indexPQ.insert(edge[0], distTo[edge[0]]);
                }
            }
        }
    }
}

上方代码实现了一个可以求最短路径的图类，用IndexPQ代替TreeSet，IndexPQ的具体实现可以开专栏来讲。