写在前面

主要分为两种思路：利用visited数组与onpath数组的DFS遍历（逆后序排列）、利用队列的BFS遍历（需要用到节点的入度信息）

环检测

DFS（深度优先遍历）

递归遍历的过程同时记录到过的位置，如果中途到过的位置又走了一遍，则肯定存在环。为了避免重复计算，全局记录visited数组。

  • 合适的数据结构：根据题意生成的邻接表
  • 两个数组：vector<int>&visited以及vector<int>&onpath，前者用于减少重复计算，因为对于节点i，如果前面已经遍历过，那么对于它指向的节点也都遍历过，因此不必要再次遍历；后者则是记录当前遍历到达的节点，用于检测是否存在环。
  • 递归函数：对于每一个节点，都应该加入visited数组，onpath则需要在遍历该节点的指向节点后撤销。

BFS（广度优先遍历）

  • 合适的数据结构：队列
  • 邻接表以及计算的每个节点的入度信息
    • 通过比较，入度为零出入栈的数目与总的数目；相等则说明遍历了所有点，不存在环。

拓扑排序

只有在没有有向环的情况下才存在拓扑排序。

DFS对应的逆后序遍历

  • 为什么？
    • 对于任意边v → w，在调用dfs(v) 时，下面三种情况必有其一成立:
      1. dfs(w)已经被调用过且已经返回了（w已经被标记）。
      2. dfs(w) 还没有被调用（w 还未被标记），因此 v → w 会直接或间接调用并返回dfs(w)，且dfs(w) 会在dfs(v) 返回前返回
      3. dfs(w)已经被调用但还未返回。证明的关键在于，在有向无环图中这种情况是不可能出现的，这是由于递归调用链意味着存在从w 到v 的路径，但存在v → w 则表示存在一个环。
    • 在两种可能的情况中，dfs(w) 都会在dfs(v) 之前完成，因此在后序排列中w 排在v 之前而，在逆后序中w 排在v 之后。因此任意一条边v → w 都如我们所愿地从排名较前顶点指向排名较后的顶点。

BFS对应的前序队列

这个很好理解，如果最后没有环且依次遍历了所有的节点，那这个排序自然就是拓扑排序的。

代码实现

DFS版本

class Solution {
public:
    // 被依赖的构建下的graph的后序遍历的逆序刚好的拓扑排序
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建邻接表及访问数组及路径
        hasCycle=false;
        vector<vector<int>> graph=buildGraph(numCourses,prerequisites);
        vector<bool> visited(numCourses,false);
        vector<bool> onpath(numCourses,false);

        // 以每个节点开始一次
        for(int i=0;i<numCourses;i++){
            traverse(graph,i,visited,onpath);
        }
        // 
        // 根绝hasCycle返回结果值
        if(hasCycle)
            return {};
        // 逆序输出
        int i=0,j=postOrder.size()-1;
        while(i<=j){
            swap(postOrder[i],postOrder[j]);
            i++;
            j--;
        }
        return postOrder;         
    }
    // 构建邻接表
    vector<vector<int>> buildGraph(int numCourses,vector<vector<int>>&prerequisites){
        vector<vector<int>> graph(numCourses);
        for(int i=0;i<prerequisites.size();i++){
            int from=prerequisites[i][1];
            int to=prerequisites[i][0];
            graph[from].push_back(to);
        }
        return graph;
    }

    // traverse 递归函数
    void traverse(vector<vector<int>>&graph,int s,vector<bool>& visited,vector<bool>& onpath){
        if(onpath[s]){
            hasCycle=true;
            return;
        }
        // 剪枝，避免重复计算
        if(visited[s]) return;
        visited[s]=true;
        onpath[s]=true;
        for(auto t:graph[s]){
            traverse(graph,t,visited,onpath);
        }
        // 后序遍历
        postOrder.push_back(s);
        onpath[s]=false;
        return;
    }
private:
    vector<int> postOrder;
    bool hasCycle;
};

BFS版本

class Solution {
public:
    // BFS的前序遍历就是拓扑排序，不存在环的情况下
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建邻接表及入度表
        vector<vector<int>> graph=buildGraph(numCourses,prerequisites);
        vector<int> indegree=buildDegree(numCourses,prerequisites);

        //  BFS 队列, 入度为零的节点先入队
        queue<int> Q;
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0)
                Q.push(i);
        }
        // 前序返回顺序
        vector<int> preOrder;
        // 计数变量
        int count=0;
        while(!Q.empty()){
            int cur=Q.front();
            Q.pop();
            count++;
            preOrder.push_back(cur);
            for(auto s:graph[cur]){
                indegree[s]--;
                if(indegree[s]==0)
                    Q.push(s);
            }
        }
        if(count==numCourses)
            return preOrder;
        return {};
    }
    // 构建入度表
    vector<int> buildDegree(int numCourses,vector<vector<int>>& prerequisites){
        vector<int> indegree(numCourses);
        for(int i=0;i<prerequisites.size();i++){
           //  int from=prerequisites[i][1];
            int to=prerequisites[i][0];
            indegree[to]++;   // 入度加1
        }
        return indegree;
    }
    // 构建邻接表
    vector<vector<int>> buildGraph(int numCourses,vector<vector<int>>&prerequisites){
        vector<vector<int>> graph(numCourses);
        for(int i=0;i<prerequisites.size();i++){
            int from=prerequisites[i][1];
            int to=prerequisites[i][0];
            graph[from].push_back(to);
        }
        return graph;
    }
};

$\cdots$ end $\cdots$