【优选算法】BFS解决拓扑排序 {有向无环图；AOV网；拓扑排序；BFS实现拓扑排序}

一、经验总结

有向无环图

若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）。

当谈到有向图的入度和出度时，我们指的是每个顶点的入度和出度。

• 一个顶点的入度是指指向该顶点的边的数量。
• 一个顶点的出度是指从该顶点出发的边的数量。

AOV网

若用DAG图表示一个工程，其顶点代表活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这样的有向无环图称为顶点表示活动的网络，记为AOV网（Activity-On-Vertex Network）。

拓扑排序

是对DAG图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

如上图中的AOV网的一种拓扑序列为：开始，和面，擀皮，洗菜，剁馅，包饺子，下饺子，完成；

如何及逆行拓扑排序？

1. 找出图中入度为0的点，然后输出
2. 删除与该点相连的边
3. 重复1，2动作，直到图中没有点或没有入度为0的点为止
4. 判断有向图中是否有环：如果循环结束后，图中仍有入度非0的点，说明有向图中有环

BFS实现拓扑排序

0. 准备工作：使用邻接表存储图结构（出边表），使用数组或哈希表统计每个点的入度，利用队列辅助实现BFS；

1. 将所有入度为0的点加入到队列

2. 当队列不为空时：

   1. 拿出队头元素，然后输出（拓扑序列）
   2. 删除与该元素相连的边（将相连的点的入度-1）
   3. 判断与删除边相连的点，如果入度为0则加入到队列中

3. 循环结束后，检查所有的点的入度是否都变为0，如果图中仍有入度非0的点，说明有向图中有环

何时构建AOV网，使用拓扑排序解决问题

1. 题目条件给的是两两活动的先后顺序，要求的是所有活动（整个流程）的先后顺序。
2. 先根据两两活动的先后顺序构建AOV网
3. 再通过拓扑排序得到拓扑序列（所有活动的顺序）。

---

二、相关编程题

2.1 课程表

题目链接

207. 课程表 - 力扣（LeetCode）

题目描述

算法原理

题目中的若干活动存在先后顺序则考虑构建AOV网，问能否完成所有课程的学习实际是问是否能进行拓扑排序。

BFS实现拓扑排序

编写代码

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        unordered_map<int,vector<int>> edges; //用邻接表实现图结构
        vector<int> in(n); //统计所有点的入度
        //建图
        for(auto e : prerequisites)
        {
            int a = e[0], b = e[1]; //b->a
            edges[b].push_back(a);
            in[a]++;
        }
        //将所有入度为0的点加入队列
        queue<int> que;
        for(int i = 0; i < in.size(); ++i)
            if(in[i] == 0) que.push(i);

        //拓扑排序
        while(!que.empty())
        {
            int a = que.front();
            que.pop();
            for(auto e : edges[a])
            {
                --in[e];
                if(in[e] == 0)  que.push(e);
            }
        }

        //判断是否有环
        for(int i = 0; i < in.size(); ++i)
            if(in[i] != 0) return false;

        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

2.2 课程表Ⅱ

题目链接

210. 课程表 II - 力扣（LeetCode）

题目描述

算法原理

BFS实现拓扑排序，与上一道题唯一的不同就是要返回拓扑序列

编写代码

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(n); //用邻接表实现图结构
        vector<int> in(n, 0); //统计所有点的入度
        vector<int> ret; //拓扑排序的结果
        //建图
        for(auto e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }

        //将所有入度为0的点加入队列
        queue<int> que;
        for(int i = 0; i < n; ++i)
            if(in[i] == 0) que.push(i);

        //拓扑排序
        while(!que.empty())
        {
            int t = que.front();
            que.pop();
            ret.push_back(t); //输出到拓扑序列
            for(auto e : edges[t])
            {
                --in[e];
                if(in[e] == 0) que.push(e);
            }
        }

        //判断是否有环
        if(ret.size() == n) return ret;
        else return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

2.3 火星词典

题目链接

LCR 114. 火星词典 - 力扣（LeetCode）

题目描述

算法原理

何时构建AOV网，使用拓扑排序解决问题：

1. 题目条件给的是两两活动的先后顺序，要求的是所有活动（整个流程）的先后顺序。
2. 先根据两两活动的先后顺序构建AOV网
3. 再通过拓扑排序得到拓扑序列（所有活动的顺序）。

编写代码

class Solution {
    unordered_map<char, unordered_set<char>> map; //用邻接表存储图
    unordered_map<char, int> in; //入度哈希表
public:
    string alienOrder(vector<string>& words) {
        //初始化入度哈希表
        for(auto word : words)
        {
            for(auto ch : word)
            {
                in[ch] = 0;
            }
        }
        //建图
        for(int i = 0; i < words.size()-1; ++i)
        {
            for(int j = i+1; j < words.size(); ++j)
            {
                if(!add(words[i], words[j]))
                    return "";
            }
        }
        //将入度为0的点加入队列
        queue<char> que;
        for(auto &[ch, i] : in)
            if(i == 0) que.push(ch);
        //拓扑排序
        string ret; //用于存储最终的拓扑序列
        while(!que.empty())
        {
            char ch = que.front();
            que.pop();
            ret+=ch;
            for(auto e : map[ch])
            {
                --in[e];
                if(in[e] == 0) 
                que.push(e);
            }
        }
        //判断是否有环
        for(auto &[ch, i] : in)
            if(i != 0) return ""; //不合法的字母顺序1
        return ret;
    }

    bool add(string &s1, string &s2)
    {
        int n = min(s1.size(), s2.size());
        int i = 0;
        while(i < n)
        {
            if(s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i]; //a->b;
                if(!map[a].count(b))
                {
                    map[a].insert(b);
                    in[b]++;
                }
                break;
            }
            ++i;
        }
        if(i==s2.size() && i<s1.size()) return false; //不合法的字母顺序2
        else return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68