0%

BFS and DFS

BFS

广度优先搜索(Breadth-First-Search),我们平常都把简称为 BFS。直观地讲,它其实就是一种“地毯式”层层推进的搜索策略,即先查找离起始顶点最近的,然后是次近的,依次往外搜索。理解起来并不难,所以我画了一张示意图,你可以看下。

时空分析

每个节点入队和出队一次, 循环总次数为0(V), 检查邻接表所有的次数为O(E), 总时间为 O(V+E)

最短路径(无权最短路径)

  • 距离定义:从 s 到 v 经过的最少的边, 记为 d(s,v), 不可达 d(s,v) -> +inf
  • 引理: \[ \forall(u,v) \in E, \ d(s,v) \leq d(s,u) + 1\]
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
from collections import deque

def BFS(graph, s, t):
visited = [None] * len(graph)
prev = [-1] * len(graph)
queue = deque()

queue.append(s)
visited[s] = True

while queue:
s = queue.popleft()
for node in graph[s]:
if not visited[node]:
prev[node] = s
if node == t:
return prev
visited[node] = True
queue.append(node)

return None


def print_path(prev,s,t):
if prev[t] != -1 and s != t:
print_path(prev,s, prev[t])
print(str(t), end = " ")




if __name__ == '__main__':
g = {0:[1,3],1:[0,2,4],2:[1,5],3:[0,4],4:[1,3,5,6],5:[2,4,7],6:[4,7],7:[5,6]}
prev = BFS(g,0,7)
print_path(prev,0,7)
  1. visited是用来记录已经被访问的顶点,用来避免顶点被重复访问。如果顶点 q 被访问,那相应的 visited[q] 会被设置为 true。

  2. queue是一个队列,用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的,也就是说,我们只有把第 k 层的顶点都访问完成之后,才能访问第 k+1 层的顶点。当我们访问到第 k 层的顶点的时候,我们需要把第 k 层的顶点记录下来,稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以,我们用这个队列来实现记录的功能。

  3. prev用来记录搜索路径。当我们从顶点 s 开始,广度优先搜索到顶点 t 后,prev 数组中存储的就是搜索的路径。不过,这个路径是反向存储的。prev[w] 存储的是,顶点 w 是从哪个前驱顶点遍历过来的。比如,我们通过顶点 2 的邻接表访问到顶点 3,那 prev[3] 就等于 2。为了正向打印出路径,我们需要递归地来打印,你可以看下 print() 函数的实现方式。

DFS

深度优先搜索(Depth-First-Search),简称 DFS。最直观的例子就是“走迷宫”。

假设你站在迷宫的某个岔路口,然后想找到出口。你随意选择一个岔路口来走,走着走着发现走不通的时候,你就回退到上一个岔路口,重新选择一条路继续走,直到最终找到出口。这种走法就是一种深度优先搜索策略。

实际上,深度优先搜索用的是一种比较著名的算法思想,回溯思想。这种思想解决问题的过程,非常适合用递归来实现。

时空分析

深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比,递归调用栈的最大深度不会超过顶点的个数,所以总的空间复杂度就是 O(V)

深度优先搜索算法的时间复杂度是 O(E),E 表示边的个数。

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


import copy

def print_path(prev,s,t):
if prev[t] != -1 and s != t:
print_path(prev,s, prev[t])
print(str(t), end = " ")

def DFS(graph,s,t):
visited = [None] * len(graph)
prev = [-1] * len(graph)
visited[s] = True

res,flag = None, False

def recur_dfs(graph,s,t, prev, visited):
nonlocal res, flag

if flag:
return

if s == t:
flag = True
res = copy.copy(prev)
return

for node in graph[s]:
if not visited[node]:
prev[node] = s
visited[node] = True
recur_dfs(graph,node,t,prev,visited)
prev[node] = -1
visited[node] = False

recur_dfs(graph,s,t, prev, visited)

return res


if __name__ == '__main__':
g = {0:[1,3],1:[0,2,4],2:[1,5],3:[0,4],4:[1,3,5,6],5:[2,4,7],6:[4,7],7:[5,6]}
res = DFS(g,0,7)
print_path(res,0,7)