43 | 拓扑排序：如何确定代码源文件的编译依赖关系？

老师，这门专栏快结束了，突然有点新的想法：如果老师在讲解算法的时候，多讲点算法的由来，也就是背景，那就更好了。 我想，如果能知道某个算法的创造者为什么会发明某个算法，怎么能够发明出某个算法，我想我们会掌握得更牢，学得应该也稍微轻松一点，关键是能跟随发明者回到原点，体会思考的过程

老师你好。我在做一道动态规划题的时候，不借助其他启发性线索时，在纸上演算一遍后，发现自己如果不能直觉地从演算中推演出解答的关键，就会产生强烈的自我怀疑。会有一层对自己智力水平的怀疑，如果没有一定的智商，是不适合做这事情的。请问老师你有什么方法，可以克服这种自我的质疑？

老师, 专栏一直跟进到现在了, 每堂课都是对知识的巩固和完善, 额...不过我一直有个小问题想请教一下老师, 那就是老师的图是使用什么工具绘制的, 我觉得非常富有生命力, 记录在笔记里非常 nice ...

1、反过来的话计算的就不是入度了，可以用出度来判断； 2、BFS的话，则需要记录上一个节点是哪个，可以实现，但是比DFS要麻烦些。 还请老师指点。 老师之后能不能给思考题一个答疑？

DFS 算法的时间复杂度计算中，为什么每个顶点访问两次？每个顶点进入dfs是一次呀？

请教个问题，思考题2是否可以基于Kahn算法，稍微改造一下，成为一个BFS的实现？即从入度为0的顶点开始，逐层遍历。。。

老师您好，还看到过另一个深度优先遍历的方法，是通过将节点涂不同的颜色判断是否在遍历的时候遇到了环，这种方法看着应该很明了，但是好像很少看到有人这么写程序，不知道是什么原因呢？

kahn算法中统计每个顶点的入度，有两层循环，时间复杂度为什么不是O(V*E)呢？

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); } // int w = adj[i].get(j); // i->w 这个W表示什么？ inverseAdj[w].add(i); // w->i 为啥是相反的邻接？这个不也是从0-i来存对应的值？

public void topoSortByKahn() { for (int i = 0; i < v; ++i) {// for (int j = 0; j < adj[i].size(); ++j) { int w = adj[i].get(j); // i->w } } 为什么要用两层循环遍历，不是直接遍历链表旧可以？