{面试常见算法80题: {图: [广度优先搜索]}}
介绍
广度优先搜索可以找到起点到目的顶点的最短路径。遍历一个图,和遍历一个树是类似的,但是图里面可能存在环,所以遍历的时候,可能会回到先前已经经过的顶点。为了避免这种情况,用一个数组来保存顶点的状态。
比如下面的一个图,我们从顶点 2 开始,当我们到达顶点 0 时,我们寻找所有与它相邻的顶点,发现 2 也与它相邻。如果我们不把访问过的顶点打上标记,那么我们会回到顶点 2 ,这样会造成一个无限循环。
简便起见,假设从起始顶点可以到达任何其他的顶点。利用广度优先搜索来遍历这个图,可以得到 2, 0, 3, 1 。
思路
- 构造 Graph 类,添加可以连通的两个顶点(即有方向的边)
- 构造一个包含 False , True 的列表,用来记录顶点是否被访问过
- 构造一个队列式的列表,每次从中取出一个元素作为当下的起点,并从列表中删除该顶点
- 起点被访问后,寻找它能够到达的其他顶点
- 如果其他顶点没有被访问过,则修改它的状态,表示已访问
- 当队列中没有元素时,说明所有顶点都已经访问过
代码
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list) # A
def addEdge(self, boy, girl):
self.graph[boy].append(girl) # B
def BFS(self, start):
visited = [False] * (len(self.graph)) # C
queue = []
queue.append(start)
visited[start] = True # D
while queue:
start = queue.pop(0)
print(start, end=' | ') # E
for i in self.graph[start]:
if visited[i] is False:
queue.append(i)
visited[i] = True # F
graph = Graph()
graph.addEdge(0, 1) # G
graph.addEdge(0, 2)
graph.addEdge(1, 2)
graph.addEdge(2, 0)
graph.addEdge(2, 3)
graph.addEdge(3, 3)
print("广度优先搜索的结果是(从2开始):")
graph.BFS(2) # H
输出
广度优先搜索的结果是(从2开始):
2 | 0 | 3 | 1 |
解读
- A. collections 库里的 defaultdict 函数,这里是以 list 为参数,它构造的字典形如:{key1: [value1, value2], key2: [value3, value2, value5], key3: []}
详细说明可见: collections.defaultdict
- B. 类似于:{boy1: [girl1, girl2], boy2: [girl2], boy3: [girl1, girl3, girl2]} ~请勿多想哦~
经过步骤 G 添加连接的边之后:
self.graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
意思是一个顶点可通向其他哪几个顶点, defaultdict(list) 完美实现了这个功能。
- C. 这是一个精妙的步骤,构造了一个以元素为索引,只包含真假值的列表。经过步骤 G , self.graph 中有 4 个键值对,所以长度为 4 , 现在:visited = [False, False, False, False]
- D. 把 visited 列表中开始顶点位置的 boolean 值转换成 True, 步骤 H 中传入的起点是 2 。 queue 中也加入起始顶点,现在:visited = [False, False, True, False] queue = [2]
- E. 打印 queue 中的第一个元素, pop 会将这个元素从 queue 中取出,不保留原值。Pyhton3 的 print 变成了函数,可以自定义 end 参数,表示打印字符串后需要输出的内容。现在:queue = [] start = 2
打印输出: 2 |
- F. 这个 for 循环是整段代码的核心。下面一步步说明:
- 最开始 start 是 2, 查询上面步骤 B 中生成的字典,得到 self.graph[2] = [0, 3], i = [0, 3]
- 第一次循环, visited[0] 是否是 False 呢?查看步骤 D 中得到的列表,确实是 False ,进入循环, queue添加 0 , visited[0] 重新赋值,造成以下结果:queue = [0] visited = [True, False, True, False]
- 第二次循环, visited[3] 确实还是 False, 于是:queue = [0, 3] visited = [True, False, True, True]
- for 循环结束之后,返回到 while 循环,发现 queue = [0, 3] , 非空,于是进入 while 循环,取出 queue[0],正好也是 0 ,并打印,现在:queue = [3] start = 0
打印输出: 2 | 0 |
- 再次来到 for 循环,这次 self.graph[0] = [1, 2] , 发现 visited[1] = False ,于是 queue 添加 1, visited[1] 赋值为 True , 现在:queue = [3, 1]
visited = [True, True, True, True]
- 有趣的地方来了。第二次循环, visited[2] 这时候已经是 True ,所以不会进入 for 循环,直接跳到 while 循环的开始
- 这时候 queue = [3, 1] , 非空,于是进行 pop 和 print 操作,之后:queue = [1] start = 3
打印输出: 2 | 0 | 3 |
- 此时 self.graph[3] = [3], 但是 visited[3] = True, 所以不会再进入 for 循环,直接跳到 while 循环的开始
- 此时 queue = [1] 非空,同样进行 pop 和 print 操作,之后:queue = [] start = 1
打印输出: 2 | 0 | 3 | 1 |
- 这时 self.graph[1] = 2 , 但是 visited[2] = True, 所以同样不会进入 for 循环,直接跳到 while 循环的开始
- 另一个有趣的地方。这时候 queue = [] , 是空的,在 Python 中空的列表是 False ,所以不会进入 while 循环,程序就此结束。
- G. 初始化, graph 变成 Graph 类的一个实例
- H. 将起点 2 作为参数传递给 Graph 类中的 BFS 函数
总结
需注意,这里的情况是给定一个顶点,它可以到达其他任何顶点,但在非连通图中有些顶点可能无法达到。这时候若要遍历图中的所有顶点,可以让广度优先搜索从所有的顶点开始。
该算法的时间复杂度是 O(V+E), V 是所有的顶点数,E 是所有的边数。
附录
参考链接: Breadth First Traversal for a Graph
参考书籍:
- Algorithms, Robert Sedgewick and Kevin Wayne
- The Art of Computer Programming, Donald Knuth
- 《数据结构与算法——Python语言描述》,裘宗燕
文章全文(GitHub): {面试常见算法80题: {图: [广度优先搜索]}}
测试通过的代码(Python3): Graph-1.py
本系列文章的 GitHub 地址: tarvos21/80algorithms
欢迎讨论,提 issuse 和 pull request,共同学习。