对图中所有节点的探索及访问操作就是遍历,这是很多问题的万能钥匙。图中有两种基本的遍历策略:深度优先搜索和广度优先搜索。

图中任意两点都是连通的,那么图就被称为连通图,连通也有可能是通过另外的节点连通。连通分量就是指的目标图中最大而且独立的连通子图。找出这种连通分量的方法之一就是从图中的某个部分开始,逐步的扩大其连通子图的确认范围,直到再也无法向外连通为止。

有下面一个证明,对于任何一个连通图,总是能够找到节点的一个排序,对于任何i=1,…,n,其子图节点也都是连通的。也就是说,按照这个顺序,可以将所有节点都一一访问到。主要思想如下:需要从i-1中推导出i的情况,因为图前i-1个节点所组成的子图是连通的,然后在前i-1中选择一个节点u,在剩余节点中选出v,在u到v的路径中,可以找到最后一个在目前连通分量的节点x和在剩余节点的第一个节点y,这样将y加入连通分量中,这样就可以使得连通分量进行扩张,直到全部加入为止。

按照这种方式持续的向连通分量中添加新节点,最终会构建出一个树结构,这种树结构就是遍历树,正在遍历的连通分量的生成树。

向外扩展的时候,新访问到的节点的邻居节点就会称为边沿节点,所以需要维护边沿节点的集合,反复在该集合中排除掉访问过的节点,并且向其中加入它们的邻居节点,这样就构成了一个想要访问但是未完成访问的节点列表。下面的代码就是这样的思想实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def walk(G, s, S=set()):
P, Q = dict(), set()
P[s] = None # 起始节点没有上一级节点
Q.add(s) # Q表示目前访问的前趋节点,边沿节点的集合
while Q:
u = Q.pop()
# G[u]与已经访问的节点还有不允许访问的节点的差集,
# 这里也就是在边沿节点中排除已经访问过的节点,只向边沿节点集合中加入未访问的节点
for v in G[u].difference(P, S):
Q.add(v) # 将每一个u可以访问到的节点加入Q,然后进行遍历
P[v] = u # 这里就是一个生成树,已经访问过的节点
return P
a, b, c, d, e, f, g = range(7)
N = {
e: {f},
b: {f, c},
a: {b, f},
d: {e, f},
c: {d},
f: {b},
g: {c}
}
p = walk(N, a)

如果要找出图中所有的连通分量:

1
2
3
4
5
6
7
8
9
def components(G):
comp = []
seen = set()
for u in G:
if u in seen: continue # 跳过已经访问过的节点
P = walk(G, u)
seen.update(P)
comp.append(P)
return comp # 存储了每一个独立的连通分量

找出图中连通分量应该是一个Θ(V+E)时间的操作,因为图中的边和节点都是必须要探索的,几乎所有的遍历算法运行时间都是如此。

迷宫问题

一直向左走的策略,其实是因为这个迷宫没有环路,迷宫始终只有一面内墙。所以顺着这种遍历策略,就可以探索到所有节点,每条通道经过两次,两个方向各一次。

1
2
3
def tree_walk(T, r):
for u in T[r]:
tree_walk(T, u)

一种递归思想,可以用一种比喻来形容就是,在某个丁字路口,可以向左也可以向右,如果向左,那么就相当于递归调用,一直向左,直到走到尽头,然后就会回溯,走到最近的丁字路口,然后向右走。所以回溯这个操作通常被隐藏在递归操作中。每次当递归调用返回的时候,其实都会自动返回到调用发起的那个点上。

停止循环遍历

其实核心在于,避免访问之前走过的路径,无论朝哪个方向走,如果走到了一个走到的路口,那么就应该回溯回来。所以这个算法主要就是要纪录哪些节点已经访问过了,防止再次进入这个节点。

1
2
3
4
5
6
7
def rec_dfs(G, s, S=None):
# S是已经访问过的节点
if S is None: S = set()
S.add(s)
for u in G[s]:
if u in S: continue # 已经访问过的就不再去访问了
rec_dfs(G, u, S)

深度优先搜索

任何递归函数都是可以用迭代操作来重写的,一种做法是用自己的栈来模拟调用栈,也就是对于即将访问的节点列表形成一个栈,后进先出即可。下面是一个迭代版的深度优先搜索:

1
2
3
4
5
6
7
8
9
10
11
def iter_dfs(G, s):
S, Q = set(), []
# S纪录已经访问的节点
Q.append(s)
# Q记录将要访问的节点
while Q:
u = Q.pop() # 弹出最后一个元素
if u in S: continue
S.add(u)
Q.extend(G[u])
yield u

之前的walk函数使用set作为队列类型,可以通过差集来排除对相同节点的多次访问,但是如果像现在这样使用队列,那么就可以允许多次出现相同的节点。这样的问题通过if u is S: continue来解决。这样的深度优先搜索无法探索到一个完整的连通分量,因为这个算法适用于有向图,所以一个节点没有入度的话,就无法遍历到。下面是一个通用性的图遍历函数:

1
2
3
4
5
6
7
8
9
10
def traverse(G, s, qtype=set):
S, Q = set(), qtype()
Q.add(s)
while Q:
u = Q.pop()
if u in S: continue
S.add(u)
for v in G[u]:
Q.add(v)
yield u

这个函数比上面的迭代版更加通用,可以指定自己的队列类型,可以借助队列中的append和pop方法,来实现一个栈。

深度优先的时间戳

DFS中,形成的生成树被称为深度优先树,DFS树的结构也取决于其中节点被访问的顺序。而且在这类树结构中,任意节点u下所有的后代节点都将会在u开始被探索到完成回溯操作之间这段时间被处理。for s in G[u]根据u下面多个分支可能会有多次节点的回溯,最终探索完u后返回。再在上一层节点中,也就是u的兄弟节点进行遍历。

该算法的具体回溯时间,为每个节点添加时间戳即可,一种是代表这个节点被探索的时间,一个是代表这个节点完成探索的时间。

1
2
3
4
5
6
7
8
9
10
11
def dfs(G, s, d, f, S=None, t=0):
if S is None: S = set()
# 开始探索的时间
d[s] = t; t += 1
S.add(s)
for u in G[s]:
if u in S: continue
# t在根据遍历的每一个节点而改变时间
t = dfs(G, u, d, f, S, t)
f[s] = t; t += 1
return t

根据DFS的属性,每个节点在DFS树中该节点的各个后代节点被探索之前发现,以及它们处理之后被完成,显而易见。

拓扑排序

如果在DAG有向非环路图中执行DFS算法,就可以简单的根据完成时间递减来对节点排序,完成时间越晚,说明这个节点更加重要,被大部分节点所依赖,这种排序就是拓扑排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dfs_topsort(G):
S, res = set(), []
def recurse(u):
if u is S: return
S.add(u)
for v in G[u]:
recurse(v)
# 越早append进res列表的,说明其拓扑排序越在后面
# 所以最后要进行逆序
res.append(u)
for u in G:
recurse(u)
res.reverse()
return res

现在发现学的越多,忘的越多,需要好好深入体会理解了。

无限迷宫和最短路径问题

DFS的问题在于可能没法直接快速找到迷宫口,因为第一次在路口选择的时候选择错了,所以需要走很远等待回溯回来。因此这个问题就是在一个既定状态空间内寻找解决方案。所以这个算法基本思想就是先是一步能访问到的所有节点,然后再去找两步能够访问到的所有节点。

下面是一个迭代深度的深度优先算法,IDDFS,是一种运行深度受限制,有限深度递增的DFS。其中的yielded的全局性集合,由第一时间被探索过的以及因此被递交的节点组成。主循环会从0到len(G)-1(可能的最大深度)的每个深度限制,遍历这些深度的所有节点,将新的没有访问过的节点加入yielded中。

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
def iddfs(G, s):
yielded = set()
def recurse(G, s, d, S=None):
print("inner s:", s)
print("yielded:", yielded)
print("S:", S)
if s not in yielded:
# 在这里返回之前没有访问过的节点,所以已经在yielded的节点就不会再返回了
yield s
# 将s加入已经遍历过的节点
yielded.add(s)
if d == 0: return
if S is None: S = set()
S.add(s)
for u in G[s]:
# 对于s周围的节点,继续迭代,直到d=1
print('inner u:', u)
if u is S:
print("inner seen u:", u)
continue
# 每一级都会打印
for v in recurse(G, u, d-1, S):
print("inner d:", d)
print("inner v:", v)
yield v
n = len(G)
# 对每一层都进行遍历,每一次遍历都是独立的,S会被清空
# 但是yielded就是持续保存的,每一次遍历就把当前每一层的就加入了
# 怎么感觉这就是广度优先遍历啊
for d in range(n):
# 如果都已经遍历过了
print("layer:", d)
if len(yielded) == n: break
for u in recurse(G, s, d):
print("outer u:", u)
yield u
print('-----------')
a, b, c, d, e, f, g = range(7)
N = {
e: {f},
b: {f, c},
a: {b, f},
d: {e, f},
c: {d},
f: {b},
g: {c}
}
for ele in iddfs(N, a):
# print(ele)
pass

仔细体会,如果在探索无边界图结构,要寻找到某一个特定节点,需要持续尝试更大的深度限制,直到找到。如果图结构本身是一条路径,从一个端点开始执行IDDFS的话,运行时间是平方级的。但是大部分节点在树的底层的话,运行时间就应该是线性级或者接近于线性级的。

广度优先搜索

其实主要就是在DFS算法中将栈数据结构变成先进先出即队列数据结构,也就是最先搜索到的节点,最先遍历。这样就可以对图结构进行逐层搜索了。代码也简单:

1
2
3
4
5
6
7
8
9
10
def bfs(G, s):
P, Q = {s: None}, deque([s])
while Q:
# 先进先出,保证逐层搜索
u = Q.popleft()
for v in G[u]:
if v in P: continue
P[v] = u # 记录父节点
Q.append(v)
return P

如果要获取从a到u的路径,就可以从u开始,寻找其父节点,直到找到a为止

1
2
3
4
5
path = [u]
while P[u] is not None:
path.append(P[u])
u = P[u]
path.reverse()

在一种情况下,IDDFS的情况是好于BFS的,当搜索目标是一个巨大的树结构,IDDFS因此不需要存储自己访问过的节点,只需要存储从起点出发的单条路径就可以了。但是BFS要在内存中存储全体的前沿节点。所以说IDDFS的内存用量会更少。

deque双端队列

BFS算法中,使用的是双端队列,这种队列使用链表,前后端的追加和pop都属于常数级操作。deque类的实现是一个块空间的双向链表,每个独立元素都是一个数组。

强连通分量

强连通分量或者强分量,是有向化的连通分量,一个图结构的连通分量是让里面所有节点彼此到达的最大子图。强连通分量的话就需要对其中的边的方向进行跟踪。所有强连通分量应该是让有向路径上所有节点彼此到达的最大子图。

一般情况下,如果只要任何一个强分量X有一条边通往另外一个强分量Y,X中最后完成遍历的时间就一定会晚于Y中最后完成的时间。另外一张有向图中可能有多个强连通分量,但是有一点就是这些强连通分量之间应该是没有环路的,要不然就会合并成一个强连通分量,另外将每一个强连通分量作为一个整体的话,那么这些强连通分量就会组成一个DAG,即有向无环路图。

这样要找到所有的强连通分量的话,就需要首先找到原图结构中没有任何入边的强连通分量,也就是翻转链接每个强连通分量的有向边后没有出度的强连通分量。也就是查找的是强连通分量图的拓扑排序的第一个强连通分量,然后查找第二个等。翻转边之后使得我们一次只能探索一个强连通分量。下面是算法代码:

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
'''strongly connected components'''
def tr(G):
'''翻转G中的边线关系,其目的是为了一次只遍历一个scc'''
GT = {}
for u in G: GT[u] = set()
for u in G:
for v in G[u]:
GT[v].add(u)
return GT
def dfs_topsort(G):
# 首先将每个节点的入度找出来
count = dict((u, 0) for u in G)
for u in G:
for v in G[u]:
count[v] += 1
# 从入度为0的点开始遍历,入度为0的点肯定是先开始的
Q = [u for u in G if count[u] == 0]
S = []
while Q:
u = Q.pop()
S.append(u)
# 去掉u之后,u指向的节点入度都减1
for v in G[u]:
print(v)
count[v] -= 1
if count[v] == 0:
Q.append(v)
return S
def walk(G, s, S=set()):
P, Q = dict(), set()
P[s] = None
Q.add(s)
while Q:
# 后加入的后访问,所以就是dfs
u = Q.pop()
# Q是即将访问的节点,也就是前沿节点
# u是v的父节点
for v in G[u].difference(P, S):
Q.add(v)
P[v] = u
return P
def scc(G):
GT = tr(G)
# sccs 将记录每个连通分量的生成树
sccs, seen = [], set()
# 返回拓扑排序的节点顺序
for u in dfs_topsort(G):
# 跳过已经遍历过的节点,然后从u节点开始遍历翻转后的图
if u in seen: continue
# 翻转后的图,一次就只会遍历一个强分量了
# 这里返回一个图遍历的生成树
C = walk(GT, u, seen)
seen.update(C)
sccs.append(C)
return sccs
a, b, c, d, e, f = range(6)
N = {
e: {f},
b: {c},
a: {b, f},
d: {e, f},
c: {d},
f: set()
}
print(scc(N))

小结

一个图结构的遍历过程主要包括:维护一个用来存放待探索节点的to-do列表,一种队列,并从中去除已经访问的节点,最初,列表只有遍历的起点,在之后的每一步,都会访问其中一个节点,从列表中去除它,然后将其邻居节点加入列表中。在列表中,项目的调度顺序决定了实现的遍历类型。如果使用stack,那么实现的就是深度优先搜索,如果使用队列,FIFO实现的就是广度优先搜索。

广度优先搜索用来在一个节点到另外一个节点之间寻找未加权的最短路径,还有一种,迭代深度的DFS,也具有BFS的作用,但是在大型树结构的搜索中所起到的作用会跟大一些。

参考自:Python 算法教程 – Magnus Lie Hetland