概念

AOV 网：将工程分成很多活动，在有向图环图中，顶点表示活动，有向边表示活动的先后关系，称为 AOV 网

笔记

能够拓扑排序的图，一定是有向无环图

有向图环图，一定能够拓扑排序

注意

在图中表示 B 依赖 A，一般用 A->B，其中 A 称为 B 的直接前驱，B 称为 A 的直接后继

警告

如果图中存在环，那么拓扑排序后的结果是空

AOV 和 AOE 的区别：

AOV：顶点表示活动，边表示活动之间的依赖关系

AOE：边表示活动，顶点表示事件，边上的权重表示活动需要的时间，AOE 网络中从起点到终点最短的时间为关键路径，一般用来分析一个项目至少需要多少时间，以及每个活动的机动时间

方法

Kahn 算法

笔记

其实是 BFS 思路

从 DAG （有向无环图）中选择入度为 0 的点输出，删除该顶点和它为起点的所有边，也就是把它指向的所有点的入度减去1，直到图中不存在点，或者不存在入度为 0 的点（就是出现了环）

最好采用邻接表来存储图，并且用一个队列表示入度为 0 的顶点，用一个数组表示入度

如果在删边的过程中出现了入度为 0 的顶点，需要再加入到队列中

DFS

从每个未访问的节点开始遍历，访问一个节点及后面所有节点之后，将点添加到栈里，再将栈反转

题目

LC 0210. 课程表 II

https://leetcode-cn.com/problems/course-schedule-ii

BFS 解法

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> u;
        vector<int> d(numCourses, 0);  // 节点的入度

        // 转换为邻接表
        for(int i = 0; i < (int)prerequisites.size(); i++){
            int x = prerequisites[i][0], y = prerequisites[i][1];

            u[y].push_back(x);
            d[x]++;
        }
        // 放入所有入度为 0 的点到队列中
        queue<int>q;
        for(int i = 0; i < numCourses; i++){
            if(d[i] == 0) q.push(i);
        }
        vector<int> res;
        while(!q.empty()){
            int t = q.front();
            q.pop();

            res.push_back(t);

            for(int c: u[t]){  // 找到该点的所有邻接点，将入度减一，如果入度减为 0，加入到队列中
                if((--d[c]) == 0){
                    q.push(c);
                }
            }
        }

        if((int)res.size() != numCourses) return {};  // 说明出现了环
        return res;
    }
};

DFS 解法

注意用两个标记数组用来判断某个数是否出现过，其中局部数组是判断图中是否含有环的，局部数组是防止加入重复的元素， 并且在递归时，先判断是否含有环，再判断是否重复，因为出现环时数字必然是重复的

class Solution {
private:
    unordered_map<int, vector<int>> u;
    vector<bool> g_used;  // 全局是否出现过
    vector<bool> l_used; // 局部是否出现过
    vector<int> res;
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        for(int i = 0; i < numCourses; i++){
            g_used.push_back(false);
            l_used.push_back(false);
        }
        
        for(int i = 0; i < (int)prerequisites.size(); i++){
            int x = prerequisites[i][0], y = prerequisites[i][1];

            u[y].push_back(x);
        }

        
        for(int i = 0; i < numCourses; i++){
            if(!dfs(i, l_used)) return {};
        }

        reverse(res.begin(), res.end());
        return res;
    }

    bool dfs(int i, vector<bool>&l_used){
        if(l_used[i]) return false;
        if(g_used[i]) return true;

        g_used[i] = true;
        l_used[i] = true;
        for(int c: u[i]){
            if(!dfs(c, l_used)) return false;
        }
        l_used[i] = false;
        res.push_back(i);
        return true;
    }
};

参考链接

图论 (opens new window)

拓扑排序概念 (opens new window)