环检测和拓扑排序算法（bfs/dfs）

艾伦野鸽ggg

362人浏览 · 2026-03-29 15:07:15

艾伦野鸽ggg · 2026-03-29 15:07:15 发布

环检测和拓扑排序算法（bfs/dfs）

环检测

用 DFS 的 onPath 数组或 BFS 的入度数组，可以判断有向图中是否存在环

dfs版本

力扣207

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

什么时候无法修完所有课程？当存在循环依赖的时候。

看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。

具体来说，我们首先可以把课程看成「有向图」中的节点，节点编号分别是 0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。

所以我们可以根据题目输入的 prerequisites 数组生成一幅图。

如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。

我们将所给的数据转化为邻接表（有向图）：

vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
    // 图中共有 numCourses 个节点
    vector<vector<int>> graph(numCourses);
    for (int i = 0; i < numCourses; i++) {
        graph[i] = vector<int>();
    }
    for (auto& edge : prerequisites) {
        int from = edge[1], to = edge[0];
        graph[from].push_back(to);
    }
    return graph;
}

然后套用遍历所有路径的 DFS 代码模板，用一个 hasCycle 变量记录是否存在环，当重复遍历到 onPath 中的节点时，就说明遇到了环，设置 hasCycle = true。

注意图中并不是所有节点都相连，所以要用一个 for 循环将所有节点都作为起点调用一次 DFS 搜索算法。

如果我们发现一个节点之前被遍历过，就可以直接跳过，不用再重复遍历了。

class Solution {
public:
    // 记录一次递归堆栈中的节点
    vector<bool> onPath;
    // 记录节点是否被遍历过
    vector<bool> visited;
    // 记录图中是否有环
    bool hasCycle = false;

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        auto graph = buildGraph(numCourses, prerequisites);
        
        onPath = vector<bool>(numCourses);
        visited = vector<bool>(numCourses);
        
        for (int i = 0; i < numCourses; i++) {
            // 遍历图中的所有节点
            traverse(graph, i);
        }
        // 只要没有循环依赖可以完成所有课程
        return !hasCycle;
    }

    void traverse(vector<vector<int>>& graph, int s) {
        if (hasCycle) {
            // 如果已经找到了环，也不用再遍历了
            return;
        }

        if (onPath[s]) {
            // s 已经在递归路径上，说明成环了
            hasCycle = true;
            return;
        }
        
        if (visited[s]) {
            // 不用再重复遍历已遍历过的节点
            return;
        }
      
        visited[s] = true;
        onPath[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        onPath[s] = false;
    }

    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
         vector<vector<int>> graph(numCourses);
    for (int i = 0; i < numCourses; i++) {
        graph[i] = vector<int>();
    }
    for (auto& edge : prerequisites) {
        int from = edge[1], to = edge[0];
        graph[from].push_back(to);
    }
    return graph;
    }
};

bfs版本

bfs借助“入度”数组来判断是否存在环

思路：

1、构建邻接表，和之前一样，边的方向表示「被依赖」关系。

2、构建一个 indegree 数组记录每个节点的入度，即 indegree[i] 记录节点 i 的入度。

3、对 BFS 队列进行初始化，将入度为 0 的节点首先装入队列。

4、开始执行 BFS 循环，不断弹出队列中的节点，减少相邻节点的入度，并将入度变为 0 的节点加入队列。

5、如果最终所有节点都被遍历过（count 等于节点数），则说明不存在环，反之则说明存在环。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 建图，有向边代表「被依赖」关系
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        // 构建入度数组
        vector<int> indegree(numCourses);
        for (auto& edge : prerequisites) {
            int from = edge[1], to = edge[0];
            // 节点 to 的入度加一
            indegree[to]++;
        }

        // 根据入度初始化队列中的节点
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                // 节点 i 没有入度，即没有依赖的节点
                // 可以作为拓扑排序的起点，加入队列
                q.push(i);
            }
        }

        // 记录遍历的节点个数
        int count = 0;
        // 开始执行 BFS 循环
        while (!q.empty()) {
            // 弹出节点 cur，并将它指向的节点的入度减一
            int cur = q.front();
            q.pop();
            count++;
            for (int next : graph[cur]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                    q.push(next);
                }
            }
        }

        // 如果所有节点都被遍历过，说明不成环
        return count == numCourses;
    }
  
    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
         vector<vector<int>> graph(numCourses);
    for (int i = 0; i < numCourses; i++) {
        graph[i] = vector<int>();
    }
    for (auto& edge : prerequisites) {
        int from = edge[1], to = edge[0];
        graph[from].push_back(to);
    }
    return graph;
    }
};

按道理都需要 visited 数组防止走回头路，这里的 BFS 算法其实是通过 indegree 数组实现了 visited 数组的作用，只有入度为 0 的节点才能入队，从而保证不会出现死循环。

拓扑排序

图的 DFS 逆后序遍历顺序，或者 BFS 的入度数组遍历顺序，就是拓扑排序的结果。

力扣210

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

dfs版本

什么是拓扑排序？

简单来说就是把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的。

很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序。

如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。

我们复用上文的dfs判断环的代码逻辑，然后将后序遍历的结果反转就得到结果了。

class Solution {
public:
    // 记录后序遍历结果
    vector<int> postorder;
    // 记录是否存在环
    bool hasCycle = false;
    vector<bool> visited, onPath;

    // 主函数
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        visited = vector<bool>(numCourses);
        onPath = vector<bool>(numCourses);
        // 遍历图
        for (int i = 0; i < numCourses; i++) {
            traverse(graph, i);
        }
        // 有环图无法进行拓扑排序
        if (hasCycle) {
            return vector<int>();
        }
        // 逆后序遍历结果即为拓扑排序结果
        reverse(postorder.begin(), postorder.end());
        return postorder;
    }

    // 图遍历函数
    void traverse(vector<int>* graph, int s) {
        if (onPath[s]) {
            // 发现环
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            return;
        }
        // 前序遍历位置
        onPath[s] = true;
        visited[s] = true;
        for (int t : graph[s]) {
            traverse(graph, t);
        }
        // 后序遍历位置
        postorder.push_back(s);
        onPath[s] = false;
    }

    // 建图函数
    vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites) {
        
    }
};

bfs版本

复用上文bfs判断环的逻辑，使用入度数组判断，bfs遍历顺序收集起来就是答案。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 建图，和环检测算法相同
        vector<vector<int>> graph = buildGraph(numCourses, prerequisites);
        // 计算入度，和环检测算法相同
        vector<int> indegree(numCourses);
        
        for (vector<int> edge : prerequisites) {
            int from = edge[1], to = edge[0];
            indegree[to]++;
        }

        // 根据入度初始化队列中的节点，和环检测算法相同
        queue<int> q;
        
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        // 记录拓扑排序结果
        vector<int> res(numCourses);
        
        // 记录遍历节点的顺序（索引）
        int count = 0;
        
        // 开始执行 BFS 算法
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            
            // 弹出节点的顺序即为拓扑排序结果
            res[count] = cur;
            count++;
            
            for (int next : graph[cur]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }

        if (count != numCourses) {
            // 存在环，拓扑排序不存在
            return {};
        }
        
        return res;
    }

private:
    vector<vector<int>> buildGraph(int n, vector<vector<int>>& edges) {
        
    }
};