[python刷题模板] 拓扑排序(Topological Sorting)

一、 算法&数据结构

1. 描述

拓扑排序(Topological Sorting)通常用来解决依赖关系问题。

拓扑排序通常用来“排序”具有依赖关系的任务。
比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边 表示在做任务 B 之前必须先完成任务 A。
故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。
1
2
3
4
5

• 注意拓扑排序只能在DAG（有向无环图）上跑。
• 如果拓扑排序在图上跑不完，说明这图有环（非合法DAG），拓扑排序会卡在进环的位置（它的其中一个访问节点需要先走过它，即有环，因此它的入度无法降为0。）
• 算法描述：
  • 首先要对所有点初始化入度。（这一句非常重要，不要只计算在边上的点！一定要初始化图里所有点！）
  • 然后建图，计算每个点的入度。
  • 把入度为0的点加入队列。（其实就是有向图的起点，可能有多个，树(单源)的话只有一个）
  • 对队列进行遍历：取出队列中的点u，访问它所有相邻的孩子v，让v入度-1,如果v的入度==0,那可以放入队列，继续向后搜索。
  • 遍历完毕。如果有没遍历到的点，那这图存在环不是DAG。

2. 复杂度分析

1. O(n+m),n和m分别是点和边的数量。

3. 常见应用

1. 判断有依赖关系的图（有向图），是否能遍历完（判断是否合法DAG）。
2. 判断有依赖关系的图（有向图），最多能遍历多少个节点。
3. 对有依赖关系的图，如果是合法DAG，输出拓扑序。

4. 常用优化

1. 一定初始化indegree每个点！
2. python3.9加了一个拓扑排序的库，作用有限，不是都能用，速度也一般，特定条件可以减少码量，不建议使用。

二、 模板代码

1. 模板题。明确给依赖关系，判断是否是DAG，且输出拓扑排序。

例题: 210. 课程表 II
建完图直接跑拓扑排序，最后判断长度是否是n即可知道是否跑完。
这题和剑指 Offer II 113. 课程顺序是一样的

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        indegree = [0] * numCourses
        g = defaultdict(list)
        for a,b in prerequisites:
            g[b].append(a) 
            indegree[a] += 1
        
        q = deque([i for i,v in enumerate(indegree) if v == 0])
        ans = []
        while q:
            u = q.popleft()
            ans.append(u)
            for v in g[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        return ans if len(ans) == numCourses else []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 询问是否能访问完整个图，即图是否DAG

链接: 207. 课程表

直接裸跑DAG

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for v,u in prerequisites:  # 注意题目反着给依赖
            g[u].append(v)
            indegree[v] += 1
        
        q = deque([u for u,x in enumerate(indegree) if x==0])
        visited = []
        while q:
            u = q.popleft()
            visited.append(u)
            for v in g[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)            

        return len(visited) == numCourses
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. 树上DP，拓扑序DP

链接: 1462. 课程表 IV

这题其实是求有向图任意两点的连通性，数据范围100，floyd就能跑，码量也小。但是没有拓扑排序快。

• 维护每个节点的所有长辈节点：fathers = [set() for _ in range(numCourses)]
• 跑拓扑排序时，状态转移为fathers[v] = fathers[u] + u
• 最后对每个询问，判断u是不是在v的长辈里即可。

class Solution:
    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        graph = defaultdict(list)
        indegree = [0] * numCourses
        for a,b in prerequisites:
            graph[a].append(b)
            indegree[b] += 1
        
        q = deque([i for i in range(numCourses) if indegree[i] == 0])
        fathers = [set() for _ in range(numCourses)]
        while q:
            u = q.popleft()
            for v in graph[u]:
                fathers[v].add(u)
                fathers[v].update(fathers[u])
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)

        return [ u in fathers[v] for u,v in queries]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4. 从中途节点开始遍历，初始不是入度0的节点。

链接: 2115. 从给定原材料中找到所有可以做出的菜

这题给出每个材料和菜的依赖关系，给出一些成品菜，因此可以从中途节点开始遍历,对联初始化为给定的节点。

参考链接: [英雄星球六月集训LeetCode解题日报] 第30日 拓扑排序

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        n = len(recipes)
        indegree = defaultdict(int)
        graph = defaultdict(list)
        for i in range(n):
            recipe = recipes[i]
            indegree[recipe] += len(ingredients[i])
            for ingredient in ingredients[i]:
                graph[ingredient].append(recipe)
                indegree[ingredient] += 0
        
        q = deque(supplies)
        visited =set(supplies)
        while q:
            u = q.popleft()
            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    visited.add(v)
                    q.append(v)
        return [r for r in recipes if r in visited]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5. 子序列的顺序转化为依赖关系/判断DAG路径数量

链接: 剑指 Offer II 115. 重建序列

• 这题没明确说依赖关系，实际上，对于子序列来说，两个数字在原数组中的相对位置是不变的，因此依赖关系是位置先后。
• 我们对pairwise建立依赖关系即可。
• 本题要求答案是唯一序列，因此任意时间队列长度>=2表示路径不唯一返回False。
• 最后判断拓扑序列是否是给出的序列。

参考链接: [英雄星球六月集训LeetCode解题日报] 第30日 拓扑排序

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        g = defaultdict(list)
        indegree = [0]*(n+1)
        for seq in sequences:
            for i in range(1,len(seq)):
                g[seq[i-1]].append(seq[i])
                indegree[seq[i]] += 1
        
        visited = []
        q = deque([i for i in range(1,n+1) if indegree[i] == 0])
        while q:
            if len(q) >= 2:
                return False
            u = q.popleft()
            visited.append(u)
            for v in g[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        return visited == nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6. 字典序转化为依赖关系

链接: 剑指 Offer II 114. 外星文字典

• 这题也没明确说依赖关系，需要自己按题目给出的规则构建。
• 一定要注意，构建时不一定会遍历到所有节点，本题字典序，只需比较第一个不同的字符，后续字符break了，但他们依然在字典中。
• 最后要判断是否是合法DAG，依然是判长度。

参考链接: [英雄星球六月集训LeetCode解题日报] 第30日 拓扑排序

---

• 这里特别再给出一份代码，是使用Python3.9的库。
• 用库的好处是缩短码量，不用手动处理入度，但依然注意把所有节点入图。

手写

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        n = len(words)
        cs = set(''.join(words))
        graph = collections.defaultdict(list)        
        indegree = [0]*26
        for word1, word2 in pairwise(words):
            l,r = len(word1),len(word2)
            k = 0
            # 规则1， 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
            while k < min(l,r):
                c1,c2 = word1[k],word2[k]
                if c1 != c2:
                    graph[c1].append(c2)
                    indegree[ord(c2)-ord('a')] += 1
                    break
                k += 1
            # 规则2，如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
            if k == r and l > r:
                return ''
                
        ans = ''
        # 拓扑排序
        q = deque([chr(ord('a')+i) for i,v in enumerate(indegree) if v==0 and chr(ord('a')+i) in cs])
        visited = []
        while q:
            u = q.popleft()  # 取出队列中的点
            visited.append(u)
            for v in graph[u]:  
                indegree[ord(v)-ord('a')] -= 1  # u遍历到的所有点v，入度-1
                if indegree[ord(v)-ord('a')] ==0:  # 如果v的入度变成0，则放入队列。
                    # visited.append(v)
                    q.append(v)
        if len(visited) == len(cs):
            return ''.join(visited)
        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

from graphlib import TopologicalSorter

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        n = len(words)
        cs = set(''.join(words))
        from graphlib import TopologicalSorter       
        ts = TopologicalSorter()                
        for c in cs:
            ts.add(c)
        for word1, word2 in combinations(words,2):
            l,r = len(word1),len(word2)
            k = 0
            # 规则1， 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
            while k < min(l,r):
                c1,c2 = word1[k],word2[k]
                if c1 != c2:
                    ts.add(c2, c1)
                    break
                k += 1
            # 规则2，如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
            if k == r and l > r:
                return ''
        try:
            return ''.join(ts.static_order())    
        except:
            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

三、其他

1. 拓扑排序没怎么接触过，写这篇模板是为了记录。之后要多刷题巩固。
2. 拓扑排序也有DFS实现，没看懂，待学习。

四、更多例题

• 待补充

五、参考链接

• 待补充