拓扑排序

图的存储

矩阵存储 graph = new int[n][n]
链表存储 List> grapth = new ArrayList<>()

辅助存储数据结构：

入度数组 inDeg = new int[n]
遍历队列 queue = new LinkedList<>()

207-课程表 I

题意分析：
课程表的先后修关系构造图，本题的目的就是判断图中是否存在环。

解题思路：

拓扑排序。根据课程关系构造图，并记录每个节点的入度值，然后根据拓扑排序遍历节点，最后判断是否每个节点都被访问过（如果有节点没有被访问说明图中存在环）。

注意点：
扩展：
代码：

public class CoursesCanFinish_207 {
    /**
     * 题解分析：问题的本质就是检查有向图中是否存在环
     *
     * 解题思路：
     *  1、根据 int[][] 构建有向图。初始化入度。
     *  2、对图进行拓扑排序。访问的节点入度 -1。
     *  3、结束判断条件：队列为空，是否所有节点都被访问。
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建图的矩阵存储
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        // 记录节点入度
        int[] inDeg = new int[numCourses];
        // 记录节点是否访问
        boolean[] visited = new boolean[numCourses];
        Arrays.fill(visited, false);
        // 初始化矩阵数据
        for (int[] arr: prerequisites) {
            int v = arr[1], w = arr[0];
            graph.get(v).add(w);
            ++inDeg[w];
        }
//        System.out.println("graph = " + graph);
        // 从入度为0的顶点开始遍历
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDeg[i] == 0) {
                queue.offer(i);
            }
        }
//        System.out.println("indeg = " + Arrays.toString(inDeg));
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            visited[curr] = true;
            // 获取当前节点的直连节点
            for (int ele : graph.get(curr)) {
                if (--inDeg[ele] == 0) {
                    queue.offer(ele);
                }
            }
        }
//        System.out.println("visited = " + Arrays.toString(visited));
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == false) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        CoursesCanFinish_207 obj = new CoursesCanFinish_207();
        int numCourses = 3;
        int[][] prerequisites = {{1,0}, {2,0}, {2,1}};
        System.out.println("ret = " + obj.canFinish(numCourses, prerequisites));
    }
}

210-课程表 II

题意分析：

遍历图，并按课程先后顺序输出课程顺序。

解题思路：

拓扑排序。遍历图并记录遍历节点最后输出。

注意点：
扩展：
代码：

public class CoursesFindOrder_210 {
    /**
     * 本题的关键就是对图进行拓扑排序。
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 构建图的矩阵存储
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        // 记录节点入度
        int[] inDeg = new int[numCourses];
        // 记录节点是否访问
        boolean[] visited = new boolean[numCourses];
        Arrays.fill(visited, false);
        // 记录访问节点路径
        int[] ans = new int[numCourses];
        int idx = 0;
        // 初始化矩阵数据
        for (int[] arr: prerequisites) {
            int v = arr[1], w = arr[0];
            graph.get(v).add(w);
            ++inDeg[w];
        }
//        System.out.println("graph = " + graph);
        // 从入度为0的顶点开始遍历
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDeg[i] == 0) {
                queue.offer(i);
            }
        }
//        System.out.println("indeg = " + Arrays.toString(inDeg));
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            visited[curr] = true;
            ans[idx++] = curr;
            // 获取当前节点的直连节点
            for (int ele : graph.get(curr)) {
                if (--inDeg[ele] == 0) {
                    queue.offer(ele);
                }
            }
        }
//        System.out.println("visited = " + Arrays.toString(visited));
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == false) {
                return new int[0];
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        CoursesFindOrder_210 obj = new CoursesFindOrder_210();
        int numCourses = 4;
        int[][] prerequisites = {{1,0}, {2,0}, {3,1}, {1,2}};
        System.out.println("ret = " + Arrays.toString(obj.findOrder(numCourses, prerequisites)));
    }
}

802-找到最终的安全状态

题意分析：

图中没有构成环的节点。（判断有环的问题如何解决呢？拓扑排序）

解题思路：

图反向后拓扑排序。入度为 0 的节点为安全节点，删除入度为 0 到直连节点指向，剩余入度为 0 的节点也是安全节点。

注意点：

图的反向构造，并记录节点的入度。

扩展：
代码：

/**
* 解题思路：
 * 1、初始出度为 0 节点都是安全节点；
 * 2、删除初始出度为 0 的节点，剩余出度为 0 的节点也为安全节点，递归该步骤。
 *
 * 因此，将有向图反向，入度为 0 的节点为安全节点，这就成了 拓扑排序（BFS + 贪心算法，解决有向图是否有环问题）
 */
public class EventualSafeNodes_802 {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        // 将图反向，用链表存储
        List<List<Integer>> rg = new ArrayList<>();
        // 记录每个节点的入度
        int[] inDeg = new int[n];
        // 初始化反向图
        for (int i = 0; i < n; i++) {
            rg.add(new ArrayList<>());
        }
        // 填充反向图
        for (int i = 0 ; i < n; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                rg.get(graph[i][j]).add(i);
            }
            // 原数组记录的节点出度，在反图中就是入度
            inDeg[i] = graph[i].length;
        }
//        System.out.println("rg = " + rg.toString());
//        System.out.println("inDeg = " + Arrays.toString(inDeg));
        Queue<Integer> queue = new LinkedList<>();
        // 初始化入度为 0 的节点
        for (int i = 0; i < n; i++) {
            if (inDeg[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            // 分别将 x 节点的直连边节点入度 -1
            for (int x : rg.get(cur)) {
                if (--inDeg[x] == 0) {
                    queue.offer(x);
                }
            }
        }
//        System.out.println("new inDeg = " + Arrays.toString(inDeg));
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        EventualSafeNodes_802 obj = new EventualSafeNodes_802();
//        int[][] graph = {{1,2},{2,3},{5},{0},{5},{},{}};
        int[][] graph = {{1,2,3,4},{1,2},{3,4},{0,4},{}};
        System.out.println("ans = " + obj.eventualSafeNodes(graph));
    }
}

图的遍历（BFS/DFS，可达性分析）

1462-课程表 IV

题意分析：

给定图中两个节点，判断两个节点是否可达，可达则说明 a 是 b 的先修课程。

解题思路：

图中从给定节点开始的 bfs 遍历。

注意点：
扩展：

dfs 遍历如何实现？

代码：

/**
 * 有向无环图的遍历
 */
public class CoursesCheckIfPrerequisite_1462 {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        // 构建临接表存储图节点
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] arr : prerequisites) {
            int v = arr[0], w = arr[1];
            graph.get(v).add(w);
        }
        // 存储结果数据
        List<Boolean> ans = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) {
            // 判断顶点 start 到 end 是否可达
            int start = queries[i][0], end = queries[i][1];
//            System.out.println("start = " + start + ", end = " + end);
            ans.add(bfs(graph, start, end));
        }
//        System.out.println("ret = " + ans.toString());
        return ans;
    }
    /**
     * bfs 算法判断两个节点是否可达
     * @param graph
     * @param start
     * @param end
     * @return
     */
    public boolean bfs(List<List<Integer>> graph, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.size()];
        Arrays.fill(visited, false);
        queue.offer(start);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            visited[curr] = true;
            for (int ele : graph.get(curr)) {
                if (ele == end) {
//                    System.out.println(start + " to " + end + " is connected");
                    return true;
                }
                if (visited[ele] == false) {
                    queue.offer(ele);
                }
            }
        }
        return false;
    }
    /**
    * 输入：n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
     * 输出：[true,false,true,false]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/course-schedule-iv
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public static void main(String[] args) {
        CoursesCheckIfPrerequisite_1462 obj = new CoursesCheckIfPrerequisite_1462();
//        int numCourses, int[][] prerequisites, int[][] queries
        int numCourses = 5;
        int[][] prerequisites = {{0,1}, {1,2}, {2,3}, {3,4}};
        int[][] queries = {{0,4}, {4,0},{1,3},{2,4}};
        System.out.println(obj.checkIfPrerequisite(numCourses, prerequisites, queries));
    }
}

路径问题（路径和/最短路径）

743-网络延迟时间（节点k到其他节点最短距离中的最大值）

题意分析：

节点 k 到其他节点的最短距离，然后从所有最短距离中取出最大值即为最长信号发送时间。

解题思路：

Dijkstra 最短路径算法。采用贪心策略求节点 k 到其他节点的最短距离。

注意点：

矩阵存储（数组存储 graph[n][n]，课程表问题是用链表存储 List> graph = new ArrayList<>()）

扩展：
代码：

public class NetworkDelayTime_743 {
    public int networkDelayTime(int[][] times, int n, int k) {
        int INF = Integer.MAX_VALUE / 2;
        // 矩阵存储图节点
        int[][] graph = new int[n][n];
        // 初始化矩阵，距离都为最大值
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
        }
        // 根据图两个节点直达关系，更新 graph 数据
        for (int[] arr : times) {
            // 数据下标和节点值不完全对应，特殊处理一下。比如节点 1-5，数组下标 0-4
            int v = arr[0] - 1, w = arr[1] - 1, val = arr[2];
            graph[v][w] = val;
        }
        System.out.println("-----初始化矩阵数据后-----------");
        printArray(graph);
        // 顶点 k 到其他节点的最短距离
        int[] dist = new int[n];
        // 顶点 k 到其他节点的最短距离是否已经找到
        boolean[] flag = new boolean[n];
        // 初始化数据
        for (int i = 0; i < n; i++) {
            dist[i] = graph[k-1][i];
            flag[i] = false;
        }
        // 对顶点 k 自身进行初始化
        dist[k-1] = 0;
        flag[k-1] = true;
        System.out.println("-------初始化访问信息---------");
        System.out.println("dist=" + Arrays.toString(dist));
        System.out.println("flag=" + Arrays.toString(flag));
        int vs = - 1;
        // 保证 k 到每个顶点都被访问到
        for (int i = 0; i < n; i++) {
            // 寻找当前最小的路径，即，从未获取最短路径的顶点中，找到距离 k 最近的顶点 vs
            int min = INF;
            for (int j = 0; j < n; j++) {
                if (flag[j] == false && dist[j] < min) {
                    min = dist[j];
                    vs = j;
                }
            }
            System.out.println("当前访问节点：" + vs);
            if (vs == -1) {
                return -1;
            }
            // 标记顶点 vs 为已经获取到的最短路径
            flag[vs] = true;
            // 更新顶点 k 到其他未访问节点的最短距离
            for (int j = 0; j < n; j++) {
                dist[j] = Math.min(dist[j], dist[vs] + graph[vs][j]);  // 加法数组越界
            }
        }
        System.out.println();
        System.out.println("-------更新后节点访问信息---------");
        System.out.println("dist=" + Arrays.toString(dist));
        System.out.println("flag=" + Arrays.toString(flag));
        int ans = Arrays.stream(dist).max().getAsInt();
        System.out.println("ans=" + ans);
        return ans == INF ? -1 : ans;
    }
    public void printArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + "  ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        NetworkDelayTime_743 obj = new NetworkDelayTime_743();
        int[][] times = {{2,1,1}, {2,3,1}, {3,4,1}};
//        int[][] times = {{1,2,1}};
        int n = 4;
        int k = 2;
        System.out.println("return = " +obj.networkDelayTime(times,n,k));
    }
}

代码库

图问题

拓扑排序

207-课程表 I

210-课程表 II

802-找到最终的安全状态

图的遍历（BFS/DFS，可达性分析）

1462-课程表 IV

路径问题（路径和/最短路径）

743-网络延迟时间（节点k到其他节点最短距离中的最大值）