算法图算法

拓扑排序

字数统计: 2k字   |   阅读时长: 9分
, ,

摘要: 拓扑排序原理、代码模板、题目列表

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumFloyd算法的原理与代码模板plings

本文我们学习拓扑排序的原理、给出代码模板和题目列表，然后解决力扣 210.

拓扑排序问题

拓扑排序：对与一个 DAG $D=(V,E)$，将所有点排成一个线性序列，使得 $\forall u,v \in V$，若 $uv \in E$，则在线性序列中 u 出现在 v 之前。

从集合论角度，拓扑排序相当于由某个集合上的一个偏序，得到该集合上的一个全序。

BFS拓扑排序 (Kahn算法)

Kahn(1937-)

Kahn 是美国工程师，主要贡献是与瑟夫(Cerf)领导了 TCP/IP 协议的设计与实现（论文《A Protocal for Packet Network Intercommunication》），制定了网络的基本设计原则。2004 年获得图灵奖。

Kahn 算法是通过 BFS 进行拓扑排序的算法，这个算法是要找出所有入度为 0 的点。之后在将这些点删除，形成的新图又有了新的入度为 0 的点，然后再删除这些点，循环往复。直到所有点处理完毕，拓扑排序结束。

1
2
3
4
5
6
7
建图，记录入度 indegrees
将入度为 0 的点加入队列
结果数组为 result
BFS:
    从队列中取出一个点，该点的入度为零，将其输出到 result。
    枚举它的所有未访问过的相邻节点 son
        将其入度 - 1，此时入度如果被减为 0，则加入队列。

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> top_sort(const vector<vector<int> >& g, vector<int>& indegrees)
{
    queue<int> q;
    for(int i = 0; i < n; ++i)
    {
        if(indegrees[i] == 0)
            q.push(i);
    }
    vector<int> result;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        result.push_back(cur);
        for(int son: g[cur])
        {
            --indegrees[son];
            if(indegrees[son] == 0)
                q.push(son);
        }
    }
    return result;
}

判定环

判定环: 当循环退出后，如果队列里还有内容，则图里有环。

用拓扑排序判环的话，有向图和无向图稍微有点区别：

  • 对于有向图，队列里的初始内容为入度为 0 的点；
  • 对于无向图，队列里的初始内容为度小于等于 1 的点。

时间复杂度 $O(|V| + |E|)$。

DFS 拓扑排序

对有向图进行 DFS，访问节点顺序的逆序就是一个拓扑排序结果。因此可以在 DFS 的回溯阶段将当前节点加入到遍历到的节点的列表中，相当于 DFS 后序遍历。

但这里有一个问题有如果有向图有环，照样可以 DFS 产生一个访问节点顺序的逆序。解法是在进行 DFS 后序遍历的时候，顺便判定一下环，中间只要判定到环，就提前退出，拓扑排序的结果返回 {}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
建图，记录入度 indegrees
将入度为 0 的点加入集合 S
结果数组为 result (反序的，结果要 reverse 一下)
for node in S:
    dfs(node)

dfs(node):
    若 node 未被访问过:
        标记 node 已经被访问
        for v in son(node):
            dfs(v)
        将 node 加入 result
    若 node 正在访问中但尚未回溯:
        遇到了环，拓扑排序不存在

注意将顶点 node 添加到 result 中的时机是在 dfs(node) 方法即将退出之时。为什么在 dfs(node) 方法的最后将该顶点添加到一个集合中，就能保证这个集合就是拓扑排序的结果呢？

因为只要当前顶点还存在边指向其它任何顶点，它就会递归调用 dfs 方法，而不会退出。当 dfs(node) 即将退出时，意味着当前顶点 node 没有指向其它顶点的边了，即当前顶点是一条路径上的最后一个顶点。

代码模板 (C++)

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
vector<int> top_sort(const vector<vector<int> >& g, vector<int>& indegrees)
{
    int n = g.size();
    vector<int> result;
    vector<int> visited(n, 0);
    for(int i = 0; i < n; ++i)
    {
        if(indegrees[i] == 0)
            if(!dfs(g, i, visited, result))
                return {};
    }
    reverse(result.begin(), result.end());
    return result;
}

bool dfs(const vector<vector<int> >& g, int node, vector<int>& visited, vector<int>& result)
{
    if(visited[node] == 2)
        return true;
    if(visited[node] == 1)
        return false;
    visited[node] = 1;
    for(int son: g[node])
        if(!dfs(g, son, visited, result))
            return false;
    result.push_back(node);
    visited[node] = 2;
    return true;
}

判定环

dfs 实现拓扑排序顺便实现了判定环，实际就是在判定环的代码上加了一行：

1
result.push_back(node);

模板题

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

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

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

提示：

1
2
3
4
5
6
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：
输入：numCourses = 1, prerequisites = []
输出：[0]

代码1：BFS 拓扑排序

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
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int> > g(numCourses);
        vector<int> indegrees(numCourses, 0);
        for(vector<int> &prerequisite: prerequisites)
        {
            g[prerequisite[1]].push_back(prerequisite[0]);
            ++indegrees[prerequisite[0]];
        }

        vector<int> result = top_sort(g, indegrees);
        if((int)result.size() != numCourses) return vector<int>();
        return result;
    }

    vector<int> top_sort(const vector<vector<int> >& g, vector<int>& indegrees)
    {
        int n = g.size();
        queue<int> q;
        for(int i = 0; i < n; ++i)
        {
            if(indegrees[i] == 0)
                q.push(i);
        }
        vector<int> result;
        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            result.push_back(cur);
            for(int son: g[cur])
            {
                --indegrees[son];
                if(indegrees[son] == 0)
                    q.push(son);
            }
        }
        return result;
    }
};

代码2：DFS 拓扑排序

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
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int> > g(numCourses);
        vector<int> indegrees(numCourses, 0);
        for(vector<int> &prerequisite: prerequisites)
        {
            g[prerequisite[1]].push_back(prerequisite[0]);
            ++indegrees[prerequisite[0]];
        }

        vector<int> result = top_sort(g, indegrees);
        if((int)result.size() != numCourses) return vector<int>();
        return result;
    }

    vector<int> top_sort(const vector<vector<int> >& g, vector<int>& indegrees)
    {
        int n = g.size();
        vector<int> result;
        vector<int> visited(n, 0);
        for(int i = 0; i < n; ++i)
        {
            if(indegrees[i] == 0)
                if(!dfs(g, i, visited, result))
                    return {};
        }
        reverse(result.begin(), result.end());
        return result;
    }

    bool dfs(const vector<vector<int> >& g, int node, vector<int>& visited, vector<int>& result)
    {
        if(visited[node] == 2)
            return true;
        if(visited[node] == 1) // 环
            return false;
        visited[node] = 1;
        for(int son: g[node])
            if(!dfs(g, son, visited, result))
                return false;
        result.push_back(node);
        visited[node] = 2;
        return true;
    }
};

拓扑排序的存在性和唯一性

  • 存在：拓扑排序结果的长度为 n
  • 唯一：队列的 size 始终为 1
  • 参考文章：建图的CornerCase

拓扑排序的方案数

参考文章：拓扑排序的方案数。

拓扑排序题目列表

Share