fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
拓扑排序详解及运用 :: labuladong的算法小抄
一开始我也在想visited是否重复，但是正如前者说的那样，这么做会减少计算量，如果碰到visited被标记为true，则说明前面已经对这个节点之后的样子做出判断了，无须再进行延伸，所以减少计算量
@Inn0vati0n @hui60 @0xlightyear 对的，visited 记录哪些节点被遍历过，而 onPath 记录当前递归堆栈中有哪些节点，它们的作用不同，所以并不重复。
类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身。onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景。
我认为还是有些重复的，可以使用染色法，将visited数组定义为int型，visited[0]表示未遍历，visited[1]表示遍历栈中，visited[2]表示已遍历完成，这样就能丢弃onPath数组
@labuladong 东哥好，这道题，不用翻转数据，才能通过。 因为后续遍历，本身就是先遍历被依赖的任务，这样的顺序本身就是正确的。
[不需要翻转]
// 逆后序遍历结果即为拓扑排序结果
Collections.reverse(postorder);
需要反转，看图就能明白。不过面试碰上还是BFS比较清楚 https://zhuanlan.zhihu.com/p/135094687 。。。递归的话确实只有后序遍历，先处理两个子节点再处理父节点这种能表达出依赖关系，前序（根左右）和中序(左根右）都不行。
@z-ak-z @553269487 按照我的解法代码逻辑是需要反转的，不过你确实可能看到有的解法代码没有对后序遍历结果进行翻转，是因为那种解法建图的时候对边的定义和我不同，我解法建的图中箭头方向是「被依赖」关系，如果你定义为「依赖」关系，整幅图中边全部反转，那就可以不对后序遍历结果反转。
具体来说，你把我的代码中 graph[from].add(to); 改成 graph[to].add(from); 就可以不反转了。
@labuladong 嗯。是的。你代码中from，to的关系是这样的。是我没看仔细。 以下的from、to的关系，确实是需要翻转的。改成 graph[to].add(from); 就可以不反转了。
int from = edge[1];
int to = edge[0];
visit数组和onpath是不冲突的，一开始也想不明白。“明明visit【s】=true就说明已经来过了呀，那肯定成环了”，后来想了个菱形有向图如下，原来1-2-4 这次遍历中visit【2】=true，但在1-3-2-4这轮遍历的时候，visit【2】不表示有环。也就是说只有在本轮遍历中出现visit【s】=true才存在环，而本轮遍历要靠onpath来判断。 也就是@Inn0vati0n 说的 visit 数组是以图为维度来考虑的，onPath 数组考虑的是路径维度。
1——>2——>4
\ /
3
- visit数组确实不好理解, 我之前疑惑的原因是, 207. 课程表 确实需要visit, 避免重复的迭代, 已经走过一遍, 就不需要再走了. 而在课程表2, 因为postorder是全局变量(这点很重要),所以node_i走过, 就已经将其依赖的课程都存进去了, 再遍历其他node时候就不需要再走了.
- 如果graph定位为被依赖,就不需要reverse了.
感觉思路上首先想到的应该是前序遍历，这里采用后序再反转的原因是，主函数开始时要把所有点作为根节点弄一遍，前序会出问题。 不怕背模板，就怕小技巧，只能多做题呜呜呜
环包含哪些结点，我能想到的有2个办法：
- bfs, 剩下来的就是
- dfs，onPath[] 记录父节点的id，当最后检测到环时，假设重复的id是cur, 父节点id是prev，就覆盖onPath[cur] = prev，然后dfs结束时，从cur往前找就可以
@Dereshi BFS 没看懂你说的啥意思，DFS 的话，可以用一个栈来存储 onPath 中标记的节点，发现环时通过栈和 onPath 数组找出环节点。
@labuladong 关于图遍历路径，我有个问题，这个 onPath 的赋值是不是应该放到 visited 检查之前啊？否则会不会丢失中间其它路径覆盖过的相同节点？
比如说有两条路，一条是 1 -> 2 -> 3，另一条是 4 -> 2 -> 5，这两条路径都会走过 2，如果放在 visited 检查之后，那第二条路径就不会包含 2 了吧？
const visited = [];
const onPath = [];
function traverse(v) {
// 感觉应该放在这里
onPath.push(v);
if (visited[v]) {
return;
}
visited[v] = true;
// 如果放在这里，之前其他路径访问过的相同节点就不会包含进来了。
onPath.push(v);
for (const n of graph[v]) {
traverse(n);
}
onPath.pop();
}
@jswxwxf 首先，你这个代码肯定是不对的，设想 if (visited[v]) 这个条件没触发，那么会执行两次 push，却只执行了一次 pop，显然没有正确维护 onPath 栈。
你对这里有疑问是因为还不太理解递归的执行顺序，可以多动手画一画代码执行的过程，就明白了。
两条路径，一条是 1 -> 2 -> 3，另一条是 4 -> 2 -> 5，成一个八叉形，那么遍历顺序是：
先从 1 开始遍历：1，2，3，回退，5，回退，回退，回退，结束
再从 4 开始遍历：4，回退，结束。
@Dereshi 我又认真思考了下，不对，BFS 算法用入度数组的方式可以判断图中是否有环，但无法找出具体哪些节点成环，indegree 数组最后不为 0 的节点并不一定都是成环的节点。
比如这幅很简单的图 1 <=> 2 -> 3，应该是节点 1 和 2 成环，但是按照 BFS 的逻辑，一开始就没有入度为 0 的节点，所以 BFS 循环根本不会执行，最终 indegree 数组中 1, 2, 3 都是 1，这显然是不正确的。
想用 BFS 找出环，就得模拟 DFS 的递归堆栈去记录遍历路径上的所有节点，同时也得用 visited 数组防止重复遍历节点。但就算这样似乎也不行，具体你可以试一下。
所以，我的结论是，BFS 算法可以判断有向图中是否存在环，但无法找出环具体是哪些节点。大家有什么看法，欢迎讨论。
个人看法： 当onPath[s]为true时，代表出现了环 当onVisited[s]为true时，表示，以s为从出发点的所有路径已经查找过了，所以不用再查一遍了，return回去即可。
这道题目给的inputs是integer，请问如果graph的edge是string该怎么做啊？ 比如 edges "A--B", "B--C"。当integer的时候我们很容易用array index来表示node，但是string就不可以用index来表示node了，是否应该Map<String, List<String>> graph 呢？感谢大家指点迷津！
