图论里面的基础问题。
有一堆课程，每个课程都有先后，比如：要上B，就必须先学完A，要上C，又必须先学完B。
图中的例子：
0是1,3,4的先驱，4是1,5的先驱，1和3是2的先驱
这样的话，一个学生要上完所有的课，可能的顺序就是：
[0,4,1,3,5,2]。这只是一种可能，只要能够上完，就算是正确。给定了两个类：
public class Course {
String course = "";
public Course(String str) {
course = str;
}
}
public class Dependency {
Course cur;
Course pre;
public Dependency(Course cur, Course pre) {
this.cur = cur;
this.pre = pre;
}
}
输入是Dependency的数组，输出要求是Course的数组。
函数的signature长这样： public List<Course> find(List<Dependency> list)
这种题，不会做真就不会做。要是我不知道什么叫拓扑排序（Topological Sort），根本就是递归懵逼。
这道题就是典型的拓扑排序。
拓扑排序就是拿来干这种事的，只要有先后顺序的，想想它准没错。
停！STOP！
怎么就直接说拓扑排序了呢？大家都没有发现，万一这个图中有环该怎么办？
在leetcode里面也有，就合着一块写了，不想看的就往下拉，题目的分析在下面~
问题就来了，如何检测有向图中是否有环。
BFS？DFS？反正图，总跑不了这两个。想想我们人是怎么看有没有环的，不就是沿着每条路看有没有回头的？DFS就是它了！
这个算法叫什么着色来着，算法导论里面也写得很详细易懂。
上面图就有环
这里用的算法叫做三色法。
当遍历到某一个节点时，节点可能会出现三种状态，这三种可能的状态用颜色来标记，便于理解。
首先定义一下三色（也就是三个状态）：
- 白色：代表此节点从来没有被访问过
- 灰色：代表此节点在当前DFS遍历中被访问过
- 黑色：代表此节点在之前的DFS遍历中被访问过 且 从此节点出发的DFS也走完了的
算法的基本思想就是：
先在图中选出白色的节点，DFS遍历：
- 如果发现有白色的节点就继续往下走，并标记为灰色
- 如果发现遇到黑色的节点，就不在黑色当前节点处DFS了
- 如果发现遇到灰色的节点，说明在当前DFS遍历中，这个节点之前被访问过，现在又被访问了，那么就有环了。
举个例子
上图为例。
- 先选择2节点开始DFS，标记2为灰色。
- 走到4，发现4是白色（没有被访问过），标记为灰色
2.1： 发现4没有邻居了，返回后把4标记为黑色 - 回到2，再访问3，标记3为灰色
3.1 ：3节点可以继续往下走，走到1，发现1也是白色，标记为灰色
3.2 ：从1节点往下走，发现2是1的邻居，但是2是灰色的，说明有环，返回！
如果图里没有环，最终所有的节点都会被标记成黑色。（当然，island这种东西不考虑）
上代码
LeetCode: [207. Course Schedule]
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 1 || prerequisites == null || prerequisites.length == 0) {
return true;
}
ArrayList<Integer>[] graph = new ArrayList[numCourses];
// 把int[][]转换成adjacency list
// 在graph中，index是每一个课程
// 所连接的arraylist是这个课程所相连的其他所有课程
for (int i = 0; i < prerequisites.length; i++) {
if (graph[prerequisites[i][0]] == null) {
graph[prerequisites[i][0]] = new ArrayList<>();
}
graph[prerequisites[i][0]].add(prerequisites[i][1]);
}
// mark每个cell中具有3个值，0,1,2
// 0 代表 没有被访问过
// 1 代表 正在被访问
int[] mark = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
if (!dfs(mark, graph, i)) {
return false;
}
}
return true;
}
private boolean dfs(int[] mark, ArrayList[] graph, int course) {
if (mark[course] == 1) {
return false;
} else if (mark[course] == 2) {
return true;
} else {
mark[course] = 1; // 现在正在访问中
}
// 继续访问该课程相连的所有课程
if (graph[course] != null) {
for (int i = 0; i < graph[course].size(); i++) {
if (!dfs(mark, graph, (int)graph[course].get(i))) {
return false;
}
}
}
mark[course] = 2;
return true;
}
}
这方法是比较经典，也比较快的方法，leetcode里面击败了来自全球的96%的Java代码
好，下面进入正题
拓扑排序
数据结构：
- 图的表示：Adjacency List
- 一个入度记录表：HashMap
- BFS必备数据结构：Queue
算法思路：
入度代表的是这个节点被指向的次数。在例子那张图中，1节点的入度为2， 0节点的入度为0，以此类推。
找入度为0的节点，BFS找它的所有邻居，然后把找到的所有邻居在入度记录表里面的入度数减一，如果某个邻居节点的入度数变成了0，那么加入Queue里面，成为下一个BFS的起点。
其实说白了，就是先挑没有prerequisite的课上，上完之后看有没有解锁的课，如果有，那么接着上，如果没有，看看有没有其他的课没有prerequisite。就像游戏里面什么修仙练级之类的……
上代码
public class OrderDependency {
public static class Order {
String order = "";
public Order(String str) {
order = str;
}
}
public static class Dependency {
Order cur;
Order pre;
public Dependency(Order cur, Order pre) {
this.cur = cur;
this.pre = pre;
}
}
public static List<Order> find(List<Dependency> list) {
List<Order> result = new ArrayList<>();
if (list == null || list.size() == 0) {
return result;
}
int totalOrder = 0;
Map<Order, List<Order>> adjList = new HashMap<>();
Map<Order, Integer> indegree = new HashMap<>();
Queue<Order> queue = new LinkedList<>();
// fill indegree and adjList
for (Dependency dep : list) {
Order cur = dep.cur;
Order pre = dep.pre;
// add to adjList
if (adjList.containsKey(pre)) {
adjList.get(pre).add(cur);
} else {
adjList.put(pre, new ArrayList<>());
adjList.get(pre).add(cur);
}
// add to indegree
if (indegree.containsKey(cur)) {
indegree.put(cur, indegree.get(cur) + 1);
} else {
indegree.put(cur, 1);
}
if (!indegree.containsKey(pre)) {
indegree.put(pre, 0);
}
}
for (Order o : indegree.keySet()) {
if (indegree.get(o) == 0) {
queue.offer(o);
}
}
// BFS
while (!queue.isEmpty()) {
Order order = queue.poll();
indegree.remove(order);
result.add(order);
if (adjList.containsKey(order)) {
for (Order cur : adjList.get(order)) {
if (indegree.containsKey(cur)) {
indegree.put(cur, indegree.get(cur) - 1);
}
if (indegree.get(cur) == 0) {
queue.offer(cur);
}
}
}
}
if (indegree.size() != 0) {
return null;
}
return result;
}
}
