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
69
70
71
72
73
74
75
76
77
|
import typing as t
from collections import deque
class Graph(object):
def __init__(self, vex: int):
"""
构造基本邻接表
:param vex: 顶点个数
"""
self.vex = vex
self.adj = [[] for _ in range(vex)]
def add_vex(self, s: int, m: int):
"""
构造边 s->t
"""
self.adj[s].append(m)
def topological_sorting_kahn(self) -> t.List:
"""
Kahn (卡恩) 算法, 根据入度是否为0去排序
时间复杂度为O(V+E), 空间复杂度为O(V)
算法思路:
1.遍历整个邻接表，根据逆链接表思维，构造入度集
2.利用双向队列，将当前轮满足入度为0的结点入队。
3.依次从队中出一个结点，将该结点指向的所有结点的入度边 - 1，若此时满足入度边==0, 则将对应结点入队。
4.重复执行2-3步骤，直到队空。得到拓扑排序结果，并且图中不存在环路。
"""
res = []
penetration = [0 for _ in range(self.vex)]
for i_r, r in enumerate(self.adj):
r: t.List
for i_c, c in enumerate(r):
penetration[c] += 1
q = deque()
for i_j, j in enumerate(penetration):
if j == 0:
q.append(i_j)
while q:
node: int = q.popleft()
res.append(node)
for i_c, c in enumerate(self.adj[node]):
penetration[c] -= 1
if penetration[c] == 0:
q.append(c)
return res
def topological_sorting_dfs(self):
"""
TODO: DFS实现拓扑排序
算法思想：
1.根据邻接表构建出逆邻接表
2.DFS遍历逆邻接表中的顶点和对应的入度边结点，当某个结点没有入度结点，则将自身状态设置为-1,添加到拓扑排序数组中。
"""
pass
graph = Graph(6)
graph.add_vex(0, 2)
graph.add_vex(1, 2)
graph.add_vex(1, 4)
graph.add_vex(2, 3)
graph.add_vex(3, 5)
graph.add_vex(4, 5)
res_kahn = graph.topological_sorting_kahn()
print('Kahn算法', res_kahn)
|