图论基础知识、常用算法与LeetCode题解
目的：将有向图转化为线性排序；检测有向图是否有环
计算每个结点的入度删除任意一个入度为0的结点 u 及其所有出边 (u, vi) ，并将其加入拓扑排序更新每一个 vi 的入度重复执行 [2. ~ 3.] 直到再也找不到入度为 0 的点如果 循环[2. ~ 3.] 的执行次数等于结点个数，那么该图无环，反之该图有环BFS与DFS的复杂度都是 O(N + M)，N 和 M 分别为点的个数和边的个数
ArrayList<ArrayList<Integer>> graph; List<Integer> inDegree; List<Integer> topo; private void toGraph(int n, int[][] p) { // 初始化 graph = new ArrayList<ArrayList<Integer>>(); inDegree = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<Integer>()); inDegree.add(0); } // 将通过边列表 p 构建邻接表，并计算入度 for (int i = 0; i < p.length; i++) { graph.get(p[i][0]).add(p[i][1]); inDegree.set(p[i][1], inDegree.get(p[i][1]) + 1); } } private boolean noLoops() { topo = new ArrayList<Integer>(); // 已经处理过的入度为 0 的结点个数 // 待处理的 0 入度结点队列 Queue<Integer> todo = new LinkedList<Integer>(); for (int i = 0; i < inDegree.size(); i++) { if (inDegree.get(i) == 0) { todo.offer(i); } } while (!todo.isEmpty()) { int c = todo.poll(); for (int e : graph.get(c)) { inDegree.set(e, inDegree.get(e) - 1); if (inDegree.get(e) == 0) { todo.offer(e); } } // 结点被这个循环处理的顺序就是图的拓扑排序 topo.add(c); } return topo.size() == inDegree.size(); }Course Schedule i 思路：判断图中是否存在闭环 Course Schedule ii 思路：输出拓扑排序，注意理解题面，对于输入 (u, v)，在邻接表中加入边 v -> u，然后对点 u 的入度 + 1。 Course Schedule iii 这题和图没有关系，是贪心的思路，先放在这里。 思路：创建优先队列（课程时长降序）pq 存放决定要上的所有课程，记录课程总时长 totalTime 。以结束时间升序遍历输入的课程列表，记当前课程为 c，如果 c.getDuration() + totalTime <= c.getEnd()，则可以将 c 直接加入队列；否则，用 c 去替换 pq 中时长最大的课程 pq.peek()，如果替换后能满足 c.getDuration() + totalTime' <= c.getEnd()，则表示替换成功；其他情况则舍弃当前课程。 注意 Java 中的优先队列无法记录重复元素，所以其元素不应该是时长（容易重复），而应该是课程。
