一、拓扑排序：
1、拓扑排序本身是基于有向无环图的一个算法。
2、拓扑排序的实现算法：
- Kahn算法
- DFS算法
二、Kahn算法：
1、思路：
- 定义数据结构的时候，如果s需要先于t执行，那就添加一条s指向t的边。所以如果某个顶点入度为0， 也就表示没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行了。
- 可以先从图中，找出一个入度为0的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减1）。
- 循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。
2、源码：
public void topoSortByKahn() {
int[] inDegree = new int[v]; // 统计每个顶点的入度
for (int i = 0; i < v; ++i) {
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inDegree[w]++;
}
}
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < v; ++i) {
if (inDegree[i] == 0) queue.add(i);
}
while (!queue.isEmpty()) {
int i = queue.remove();
System.out.print("->" + i);
for (int j = 0; j < adj[i].size(); ++j) {
int k = adj[i].get(j);
inDegree[k]--;
if (inDegree[k] == 0) queue.add(k);
}
}
}
3、时间复杂度：
从代码中可以看出来，每个顶点被访问了一次，每个边也都被访问了一次，所以， Kahn算法的时间复杂度就是（V表示顶点个数， E表示边的个数）。
三、DFS算法：
1、思路：
这个算法包含两个关键部分：
- 第一部分是通过邻接表构造逆邻接表。邻接表中，边s->t表示s先于t执行，也就是t要依赖s。在逆邻接表中，边s->t表示s依赖于t， s后于t执行
- 第二部分是这个算法的核心，也就是递归处理每个顶点。对于顶点vertex来说，先输出它可达的所有顶点，也就是说，先把它依赖的所有的顶点输出了，然后再输出自己。
2、源码：
public void topoSortByDFS() {
// 先构建逆邻接表，边s->t表示， s依赖于t， t先于s
LinkedList<Integer> inverseAdj[] = new LinkedList[v];
for (int i = 0; i < v; ++i) { // 申请空间
inverseAdj[i] = new LinkedList<>();
}
for (int i = 0; i < v; ++i) { // 通过邻接表生成逆邻接表
for (int j = 0; j < adj[i].size(); ++j) {
int w = adj[i].get(j); // i->w
inverseAdj[w].add(i); // w->i
}
}
boolean[] visited = new boolean[v];
for (int i = 0; i < v; ++i) { // 深度优先遍历图
if (visited[i] == false) {
visited[i] = true;
dfs(i, inverseAdj, visited);
}
}
}
private void dfs(int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
int w = inverseAdj[vertex].get(i);
if (visited[w] == true) continue;
visited[w] = true;
dfs(w, inverseAdj, visited);
} // 先把vertex这个顶点可达的所有顶点都打印出来之后，再打印它自己
System.out.print("->" + vertex);
}
3、时间复杂度：
每个顶点被访问两次，每条边都被访问一次，所以时间复杂度是。
