算法之拓扑关系( 二 ) _顶点

< adj[i].size(); ++j) {int k = adj[i].get(j);inDegree[k]--;if (inDegree[k] == 0) queue.add(k);}}}
DFS算法
图上的深度优先搜索我们前面已经讲过了，实际上，拓扑排序也可以用深度优先搜索来实现。不过这里的名字要稍微改下，更加确切的说法应该是深度优先遍历，遍历图中的所有顶点，而非只是搜索一个顶点到另一个顶点的路径。
具体的代码如下：
public void topoSortByDFS() {// 先构建逆邻接表，边s->t表示，s依赖于t，t先于sLinkedList 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->winverseAdj[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 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);}
第一部分是通过邻接表构造逆邻接表。邻接表中，边 s->t 表示 s 先于 t 执行，也就是 t 要依赖 s 。在逆邻接表中，边 s->t 表示 s 依赖于 t，s 后于 t 执行。为什么这么转化呢？这个跟我们这个算法的实现思想有关。
第二部分是这个算法的核心，也就是递归处理每个顶点。对于顶点来说，我们先输出它可达的所有顶点，也就是说，先把它依赖的所有的顶点输出了，然后再输出自己。
总结：
拓扑排序应用非常广泛，解决的问题的模型也非常一致。凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。除此之外，拓扑排序还能检测图中环的存在。对于 Kahn 算法来说，如果最后输出出来的顶点个数，少于图中顶点个数，图中还有入度不是 0 的顶点，那就说明，图中存在环。
【算法之拓扑关系】参考资料