拓扑排序详解及运用 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：拓扑排序详解及运用

评论礼仪 见这里，违者直接拉黑。

[0xlightyear]

visited 和 onPath 这两个变量是否有些重复？

[dwdw666]

就像是回溯里面的track一样

[0xlightyear]

不重复，这两个变量很有必要，目的不一样。visited可以减少很大一部分计算量

[hui60]

一开始我也在想visited是否重复，但是正如前者说的那样，这么做会减少计算量，如果碰到visited被标记为true，则说明前面已经对这个节点之后的样子做出判断了，无须再进行延伸，所以减少计算量

[hui60]

课程表那道题，traverse中的两个if不能调换，哈哈，错这了

[Inn0vati0n]

visited是以整个图为维度判断是否重复遍历，onPath是以路径为维度判断是否有环，区别在于后续遍历的处理。两者不能互相替代。

[hlxs-c]

这个回答很妙啊 ！
(1)visited 在整个图的维度上判断一个节点是否已经被遍历过了，visited[i]==true表示该节点已经访问过了，而如果一个节点已经被访问过了，由于遍历一个点时一定会遍历完其所有的相邻节点（也即一定会遍历完以该节点开头的所有递归路径），所以当visited[i]==true时，则没有必要重复遍历该节点了，故可以减少很多的重复遍历。
(2)而 onPath数组代表的是当前递归遍历路径中已经被访问过的节点，如果 onPath[i]==true，则说明在当前路径中已经有该节点，说明成环。

[labuladong]

@Inn0vati0n @hui60 @0xlightyear 对的，visited 记录哪些节点被遍历过，而 onPath 记录当前递归堆栈中有哪些节点，它们的作用不同，所以并不重复。

类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身。onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景。

[xxl10000]

下面使用染色法，将visited数组定义为int型，visited[0]表示未遍历，visited[1]表示遍历栈中，visited[2]表示已遍历完成，这样就能丢弃onPath数组，这种属于修改了变量定义，他的visit 变量表示含义相当于把 作者的visit 和onpath变量含义合并了

[fuhailin]

我认为还是有些重复的，可以使用染色法，将visited数组定义为int型，visited[0]表示未遍历，visited[1]表示遍历栈中，visited[2]表示已遍历完成，这样就能丢弃onPath数组

[chaonanzhang1206]

讲道理，BFS版的拓扑还是更容易点更适合面试。。。

[xxl10000]

对的

[z-ak-z]

@labuladong
东哥好，这道题，不用翻转数据，才能通过。
因为后续遍历，本身就是先遍历被依赖的任务，这样的顺序本身就是正确的。

[不需要翻转]
// 逆后序遍历结果即为拓扑排序结果
Collections.reverse(postorder);

[qihang-dai]

需要反转，看图就能明白。不过面试碰上还是BFS比较清楚 https://zhuanlan.zhihu.com/p/135094687 。。。递归的话确实只有后序遍历，先处理两个子节点再处理父节点这种能表达出依赖关系，前序（根左右）和中序(左根右）都不行。

[Hanmu-Zuo]

前序遍历会产生的问题是，当一个节点有两个依赖时，前序遍历会在第一个依赖完成后就加入有两个或多个依赖的节点。后续可以保证&&的关系，前序只能保证 ||的关系。

[labuladong]

@z-ak-z @553269487 按照我的解法代码逻辑是需要反转的，不过你确实可能看到有的解法代码没有对后序遍历结果进行翻转，是因为那种解法建图的时候对边的定义和我不同，我解法建的图中箭头方向是「被依赖」关系，如果你定义为「依赖」关系，整幅图中边全部反转，那就可以不对后序遍历结果反转。

具体来说，你把我的代码中 graph[from].add(to); 改成 graph[to].add(from); 就可以不反转了。

[z-ak-z]

@labuladong
嗯。是的。你代码中from，to的关系是这样的。是我没看仔细。
以下的from、to的关系，确实是需要翻转的。改成 graph[to].add(from); 就可以不反转了。

int from = edge[1];
int to = edge[0];

[Jeremy0309]

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

[tommy-qichang]

1. visit数组确实不好理解, 我之前疑惑的原因是, 207. 课程表 确实需要visit, 避免重复的迭代, 已经走过一遍, 就不需要再走了. 而在课程表2, 因为postorder是全局变量(这点很重要),所以node_i走过, 就已经将其依赖的课程都存进去了, 再遍历其他node时候就不需要再走了.
2. 如果graph定位为被依赖,就不需要reverse了.

[fornobugworld]

感觉思路上首先想到的应该是前序遍历，这里采用后序再反转的原因是，主函数开始时要把所有点作为根节点弄一遍，前序会出问题。
不怕背模板，就怕小技巧，只能多做题呜呜呜

[Chen-yongcheng]

@labuladong，我的个人理解是visit[]只是起到一个剪枝的作用，只是为了避免重复计算，onPath只是是记录路径+环检测的作用；
若无环，则理论上不需要visit[],顶多重复计算。
若有环，我觉得理论上也不需要visit[]，只使用onPath也可以避免死循环，使用visit[]只是为了减少重复计算(当然如果是需要统计环个数，肯定得需要visit[]来避免重复)
不知道个人想的对不对，希望解惑😊

[Chen-yongcheng]

希望一起讨论😊

[labuladong]

你的理解是对的，但就判断环这道题来说，onPath 就可以发现环了，发现环就结束遍历的话，就不会有死循环的问题，确实不去要 visited 数组了👍🏼

[gaosh96]

还是 BFS 好理解一点

[tingtingwang217]

好厉害 把这两道题好好研究了一下 收获很大 谢谢作者

[DonkeyBoy001]

东哥，今天看完你的拓扑排序之后有一些不太一样的感悟，我想分享一下，之前 有一篇文章里面讲关于 DFS和backtracking回溯的区分，dfs更侧重在 节点上进行处理， 而backtrack则是在 树枝上进行处理，这篇文章上 拓扑排序使用 dfs的部分，虽然说是回溯，但感觉更偏向 dfs那种。因为对数据的处理主要还是在节点上完成的。如果是在树枝上完成，处理的部分应该是在for循环内部。分享完毕，欢迎大家指正！

[labuladong]

DFS 和回溯的边界其实不是特别明显，很多时候都是混用的，你的理解是对的，感谢分享！

[miiiiiko]

感觉还是不要反过来更好懂，边的指向是前提，所以用后续遍历就可以学完前提再学根节点的课程，不然要绕一下

[B1gO]

LinkedList的addFirst方法可以避免reverse postorder.

[wuzeyu2015]

看了后序遍历的拓扑排序，当时想到能不能用前序遍历来做，是不是前序遍历然后不用倒序然后组合下就可以了，结论是行不通的，但是leetcode的用例居然只有一个失败。。

[Mr-Righter]

for(int i=0;i<numCourses && !hasCycle;i++){   //如果一旦检测已经有环就停止循环
            traverse(i,graph);
        }
        return hasCycle;

leetcode上用DFS如果超时可以尝试在for循环那里加一个判定

[shiboys]

寻找带有环的图中的环的所有节点：

public class Solution {
boolean hasCycle = false;
    boolean[] visited;
    boolean[] onPath;
    Integer cycleNode = null;

int[] findCycleNodes(int numCourses, int[][] prerequisites) {
        boolean canFinish = canFinishWithCycleNodes(numCourses, prerequisites);
        if (canFinish || cycleNode == null) { // 没有环或者没有找到环的入口点
            return new int[] {};
        }
        // 路径中的所有节点并非环中的所有节点，取环中的所有节点
        int cycleStartIndex = -1;
        for (int i=0;i < cyclePathNodeList.size();i++) {
            // 都是在路径上的，且当前节点 i 为环的入口
            if (cycleNode == cyclePathNodeList.get(i)) {
                cycleStartIndex = i; // 首次找到入口
                break;
            }
        }
        if (cycleStartIndex == -1) {
            return new int[] {};
        }
        // 最后一个节点就是最后的那个重复的入口点
        return cyclePathNodeList.subList(cycleStartIndex, cyclePathNodeList.size() - 1).stream()
                .mapToInt(x -> x.intValue()).toArray();
    }

    List<Integer> cyclePathNodeList = new ArrayList<>();

    boolean canFinishWithCycleNodes(int numCourses, int[][] prerequisites) {
        onPath = new boolean[numCourses];
        visited = new boolean[numCourses];
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        for (int i = 0; i < numCourses; i++) {
            traverseWithCycle(graph, i);
        }
        return !hasCycle;
    }

    void traverseWithCycle(List<Integer>[] graph, int s) {
        if (onPath[s]) {
            hasCycle = true;
            // 也可以在这个地方收集所有的 onPath 为 true 的节点
            cycleNode = s;
            cyclePathNodeList.add(s);
        }
        if (visited[s] || hasCycle) {
            return;
        }
        visited[s] = true;
        onPath[s] = true;
        cyclePathNodeList.add(s);
        for (int to : graph[s]) {
            traverseWithCycle(graph, to);
        }
        // 后序位置
        onPath[s] = false;
    }
}

[Yuzongni]

vector< vector> find(unordered_map<int, vector>& graph, int m) {
if (path[m]) {
res.push_back(path);
return;
}
path.push_back(m);
for (auto& num : graph[m]) {
if (onpath[num]) {
find(graph, num);
}
}
path.pop_back();
}
c++找具体路径，不知道是否可行？
void traverse(unordered_map<int, vector>& graph, int m) {
if (onpath[m]){
on = true;
find(graph, m);
}
if (on || visited[m]) {
return;
}
visited[m] = true;
onpath[m] = true;
for (auto& m : graph[m]) {
traverse(graph, m);
}
onpath[m] = false;
}

[Yuzongni]

vector< vector> find(unordered_map<int, vector>& graph, int m) {
if (path[m]) {
res.push_back(path);
return;
}
for (auto& num : graph[m]) {
if (onpath[num]) {
path.push_back(num);
find(graph, num);
path.pop_back();
}
}
}
void traverse(unordered_map<int, vector>& graph, int m) {
if (onpath[m]){
on = true;
path.push_back(m);
find(graph, m);
}
if (on || visited[m]) {
return;
}
visited[m] = true;
onpath[m] = true;
for (auto& m : graph[m]) {
traverse(graph, m);
}
onpath[m] = false;
}

[luckyzc]

请问东哥和各位大佬，我把逻辑改成C语言这么写当输入位prerequisites =[[1,4],[2,4],[3,1],[3,2]] numCourses =5时
在clion可以跑通，为什么在LeetCode不行呢，能麻烦帮忙看看哪块出了问题么，注释我都写好了

int *graph_list; //记录先修课程后面需要修的课程
bool *visit; //访问过的节点
bool *onpath; //记录正在访问的节点，用于判定是否成环
bool hascycle = false; //设置标志位

//用矩阵方式建立邻接表
int** buildgraph(int numCourses, int** prerequisites, int prerequisitesSize){
//if(prerequisites == NULL) return NULL;
int** graph = malloc(sizeof(int*) * numCourses);
graph_list = malloc(sizeof(int) * numCourses);
//初始化
for(int i = 0; i < numCourses; i++){
graph_list[i] = 0;
graph[i] = NULL;
}
//为每个先修课程节点添加后续课程
for(int i = 0; i < prerequisitesSize; i++){
int index = prerequisites[i][1];
int value = prerequisites[i][0];
if(graph[index] == NULL){
graph[index] = (int*)malloc(sizeof(int) * numCourses);
}
graph[index][graph_list[index]] = value;
graph_list[index]++;
}
return graph;
}

//遍历邻接表
void transver(int** graph, int node){
if(graph[node] == NULL)
return;
if(onpath[node] == true)
hascycle = true;
if(visit[node] || hascycle)
return;
visit[node] = true;
onpath[node] = true;
for(int i = 0; i < graph_list[node]; i++){

    int next_node = graph[node][i];
    transver(graph, next_node);
}
onpath[node] = false;

}

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize){
//if(prerequisites == NULL) return true;
if(prerequisitesSize == 0 || prerequisitesSize == 1) return true;
visit = malloc(sizeof(bool) * numCourses);
onpath = malloc(sizeof(bool) * numCourses);
for(int i = 0; i < numCourses; i++){
onpath[i] = false;
visit[i] = false;
}
int** graph = buildgraph(numCourses, prerequisites, prerequisitesSize);
for(int i = 0; i < numCourses; i++){
if(graph[i] != NULL){
transver(graph, graph[i][0]);
}
}
return !hascycle;
}

[luckyzc]

解决了，打扰了

[ERICCYS]

class Solution {
private:
    vector<bool> visited;
    vector<bool> onPath;
    bool hasCycle = false;
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // construct a grpah
        vector<vector<int>> graph = makeGraph(numCourses, prerequisites);

        for (int i = 0; i < numCourses; i++) {
            visited.push_back(false);
            onPath.push_back(false);
        }

        for (int i = 0; i < numCourses; i++) {
            traverse(graph, i);
            if (hasCycle == true) {
                return false;
            }
        }

        return true;
    }

    // return a graph represented as a adj list
    vector<vector<int>> makeGraph(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph;
        for (int i = 0; i < numCourses; i++) {
            vector<int> adj;
            graph.push_back(adj);
        }
        for (vector<int> p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        return graph;
    }

    // DFS traverse
    void traverse(vector<vector<int>> graph, int node) {
        if (onPath[node]) {
            hasCycle = true;
            return;
        }
        if (visited[node] || hasCycle) {
            return;
        }
        visited[node] = true;
        onPath[node] = true;
        vector<int> neighbours = graph[node];
        for (int i = 0; i < neighbours.size(); i++) {
            traverse(graph, neighbours[i]);
        }
        onPath[node] = false;
    }
};

力扣207题这个DFS解法一直TLE，感觉和东哥解法差不多，不知道为啥超时了，哪位大佬可以帮忙看一下多谢啦！

[catchfree1225]

DAG的邊，可以當做課程節點間的單向關係（思路不知道正不正確）
(a, b) = (cur, pre)，兩種定義方式：
1.需要的前置課程數量：
定義關係為cur->pre，找到有最多pre的課程
後序遍歷結果為pre的多到少，因此不需reverse
2.另一種定義方式為學習方向：
pre->cur代表學習cur之前要學pre
後序遍歷最後一個點為首先學習課程，要reverse結果

[shayeyey]

这里判断是否有环的时候，如果有环，代码是不是还会继续执行遍历图的部分啊

[VincentWang1024]

leetcode显示BFS解法慢了2ms，对OA通过有影响么，还是遇到类似的题目直接DFS来解？