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
|
'''
深度优先搜索 Depth First Search DFS
DFS伪码描述：
def DFS():
vistited[V] = True
for V 的每个邻接点 w:
if !vistited[w] :
DFS(w)
可以看出DFS 类似于树的先序遍历。
# 加法法则，如果算法的代码是平行增加的，那么就需要加上相应的时间复杂度。
# 乘法法则，如果算法的代码增加的是循环内的嵌套或者函数的嵌套，那么就需要乘上相应的时间复杂度。
************************************
图的遍历
实质上就是对每个顶点查找其邻接点的过程。（就是把邻接表或者邻接矩阵等模型画出来的过程，而不是画图的点边结构。）
************************************
N 个顶点、 E 条边，时间复杂度：
邻接表：O(N+2E) = O(N+E)
# 遍历某个顶点的所有邻接点的复杂度为O(ei),
# ei为每个顶点的邻接点个数,也就是每条链表的边数。
# 所以邻接表版的 dfs 遍历所有邻接点的时间复杂度为
# O(e1 + e2 + e3 + .... + en) ，
# 因为所有边数之和为 E , 所以时间复杂度为 O(2E)= O(E)，
# 又因为访问每个顶点都必须被访问一次, 比如设置vis[i] = true，
# 这个操作一共要执行 V 次，所以，
# 设置所有顶点为已访问的时间复杂度为O(V),
# 所以总的时间为查找所有邻接点的时间加上设置每个顶点为已访问的时间，
# 总的时间为 O(E) + O(V) = O(E + V)。
邻接矩阵：O(N**2)
# 嵌套的循环。
# 邻接矩阵与邻接表遍历过程不同在于，
# 对于邻接矩阵来说查找某个顶点的所有邻接点的过程必须遍历所有顶点，
# 无论是否邻接都必须判断一次。
# 所以查找每个顶点的邻接点的时间复杂度都为O(n),
# 共有 n 个顶点，这 n 个顶点就表现为递归深度最大为 n,
# 所以总的时间复杂度为 O(n + n + ... + n) = O(n ^2),
# 而设置每个顶点为已访问的时间复杂度为O(n),
# 所以总的时间复杂度为O((n^2 + n), 忽略小阶复杂度，保留大阶复杂度，
# 所以我们通常说它的时间复杂度为 O(n^2)。
'''
'''
广度优先搜索 Bbreadth First Search,BFS
类似 层序遍历,但是多了一个判断是否之前遍历过此结点的操作。
伪码：
def BFS(v):
visited[v] = true
enqueue(v q) 入队列
while(!isempty（q）):
v = dequeue(q) 依次出队列
for (v的每个邻接点 w):
if(!visited[w] ):
visited[w] = true
enqueue(w,q) 邻接点依次入队列
N 个顶点、 E 条边，时间复杂度：
邻接表：O(N+2E) = O(N+E)
邻接矩阵：O(N**2)
# 邻接矩阵如果稀疏，伪码中这一步会非常耗时
# for (v的每个邻接点 w):
'''
'''
为什么需要两种遍历方式？
BFS 在靠近 目标位置的情况下，适合。
DFS 在路径方向正确的情况下，适合。
'''
'''
图联不通怎么办？
联通：如果从v到w 存在一条路径，就称v 和w 是联通的。
"路径的长度" ： 路径中的 边数，（如果带权，则是所有边的权重和。）
如果v 到 w 之间的所有顶点都不同，称为"简单路径"。
回路：起点等于终点的路径。
联通图：图中任意两个顶点均联通。
联通分量：无向图的极大联通子图。（两个极大）
极大顶点数：再加1个顶点就不联通了。
极大边数： 包含子图中所有顶点相连的所有边。
强联通：v 和 w 之间存在双向路径。
强联通图：有向图中任意两个顶点之间均强联通。
强联通分量：有向图的极大联通子图。
# 每一次调用DFS ，就是把 v 所在的联通分量遍历一遍，BFS同理。
def DFS():
vistited[V] = True
for V 的每个邻接点 w:
if !vistited[w] :
DFS(w)
# 补充一个方法，把不联通的图中的每一个联通分量都遍历一遍。
def ListComponents(Graph G):
for each v in G: # 保证图中每一个点都被遍历到。一次DFS会让多个v被打上访问过的标签
if !visited[v]:
DFS(v)
'''
|