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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
| '''
AOV 网络 Activity On Vertex Network
用顶点表示活动，用边表示活动之间的优先顺序，这样的图就是AOV网。
拓扑序：如果图中v 到 w有一条有向路径，则v 一定排在 w之前。
满足此条件的顶点序列称为拓扑序。
拓扑排序：获得一个拓扑序的过程。
AOV 如果有合理的拓扑序，则必定是 有向、无环、图。
（Directed、 Acyclic、 Graph, ADG ）
因为，如果有一个cyclic环 ，v就必须在v开始前结束，逻辑矛盾。
拓扑排序大概描述：
没有前驱顶点的点，它的入度 都是 0 ，
每次选择 入度 为 0 的点，
并将其从图中抹掉，
加入一个队列。
当把原来的点摸光的时候，一个拓扑序的队列 就产生了。
拓扑排序 基础算法伪代码：
def TopSort():
for count in range(v_num): # /* O(V) */
v = 未输出 的 入度为0 的顶点 # /* O(V) */
if 这样的v 不存在,且还有未输出的点：
Error 图中有回路, 无法完成拓扑排序。
break
输出v、或者记录v的输出序号
for v 的每个邻接点 w：
Indegree[w] -= 1 # 通过下一个结点的入度-1，完成对上一个结点的抹除操作。
如果 v = 未输出 的 入度为0 的顶点
用遍历所有结点的方法，总的 T = O(V**2)
改进：
随时将入度 为0 的点 放到一个容器里,以下代码用队列这种容器存
（输出顶点那步的时间复杂度变成常数级，因为只是从容器中输出。）
拓扑排序 改进算法伪代码：
def TopSort():
for 图中每个顶点 v：
if Indegree[v] == 0: #如果入度为0
Enqueue(v,Q) # 入队列
while !IsEmpty(Q):
v = Dequeue(Q)
输出，或者记录v的输出序号
count ++
for v 的每个邻接点 w：
if --Indegree[w] == 0:
Enqueue(w,Q)
if count != v_num: # 图中依然有点未输出。
Error 图中有回路
每个点完成出入队列一次 O(V)
每个点完成找邻接点，遍历边。O(E)
时间复杂度为 O(V + E)
稀疏图 O(V + E)
稠密图 O(V + V**2)
以上算法 还能用于检验，图是否是 有向无环图DAG 。
'''
'''
1\数学1
-> 3\高数
2\数学2 --
--> 4\操作系统
--
6\数据结构 -> 5\算法
'''
class Graph():
def __init__(self,n_vertices,data):
self._n_vertices = n_vertices
self.G = [[] for _ in range(self._n_vertices)]
self.data = data(n_vertices)
def add_edge(self,pro_vertices,new_vertices,edge_weight):
self.G[pro_vertices].append({new_vertices:edge_weight})
self.data.indegree[new_vertices] += 1
def show_Graph(self):
for i in range(self._n_vertices):
print(self.G[i])
print('入度的list为：',self.data.indegree)
class data():
def __init__(self,n_vertices):
self.indegree = [0 for _ in range(n_vertices)]
graph = Graph(6,data)
graph.add_edge(0,2,1)
graph.add_edge(1,2,1)
graph.add_edge(2,3,1)
graph.add_edge(4,3,1)
graph.add_edge(5,4,1)
graph.show_Graph()
def TopSort():
Q = []
out = []
count = 0
for v in range(len(graph.G)):
if graph.data.indegree[v] == 0:
Enqueue(v,Q)
print(Q)
while IsEmpty(Q) == False:
v = Dequeue(Q)
out.append(v)
print(v)
count += 1
for w in near_Node(v):
graph.data.indegree[w] -= 1
if graph.data.indegree[w] == 0:
Enqueue(w,Q)
if count != len(graph.G):
return '图中有回路，无法拓扑序。'
return out
def Enqueue(v,Q):
Q.append(v)
def Dequeue(Q):
return Q.pop(0)
def IsEmpty(Q):
return len(Q) == 0
def near_Node(v,list_=[]):
if graph.G[v] != []:
list_ = [key for dic in graph.G[v] for key in dic.keys()]
return list_
if __name__ =='__main__':
out = TopSort()
print('为有向无环图DAG，拓扑序为：',out)
|