《算法图解》读书笔记 第六章 广度优先搜索

图

图由节点 （node）和边（edge）组成。

图分为有向图和无向图。

队列

队列只支持两种操作：入队和出队 。

队列是一种先进先出 （First In First Out，FIFO）的数据结构，而栈是一种后进先出 （Last In First Out，LIFO）的数据结构。

广度优先搜索

广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：

• 第一类问题：从节点A出发，有前往节点B的路径吗？
• 第二类问题：从节点A出发，前往节点B的哪条路径最短？（最短路径问题）

回答第二类问题需要借助队列，否则找到的可能不是最短路径，实现代码如下：

from collections import deque
search_queue = deque() ←------------创建一个队列
search_queue += graph["you"] ←------将你的邻居都加入到这个搜索队列中

while search_queue: ←------只要队列不为空
    person = search_queue.popleft() ←------就取出其中的第一个人
    if person_is_seller(person): ←------检查这个人是否是芒果销售商
        print person + " is a mango seller!" ←------是芒果销售商
        return True
    else:
        search_queue += graph[person] ←------不是芒果销售商。将这个人的朋友都加入搜索队列
return False ←------如果到达了这里，就说明队列中没人是芒果销售商

使用一个列表来记录检查过的人，这很重要。否则可能会陷入无限循环，实现代码如下：

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = [] ←------------------------------这个数组用于记录检查过的人
	while search_queue:
        person = search_queue.popleft()
        if person not in searched: ←----------仅当这个人没检查过时才检查
            if person_is_seller(person):
                print person + " is a mango seller!"
                return True
            else:
                search_queue += graph[person]
                searched.append(person) ←------将这个人标记为检查过
    return False
	
search("you")

广度优先搜索的运行时间为O (人数 + 边数)，这通常写作O (V + E )，其中V 为顶点（vertice）数，E 为边数。

小结

• 广度优先搜索指出是否有从A到B的路径。如果有，广度优先搜索将找出最短路径。
• 面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题。
• 有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。
• 无向图中的边不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约会，而rachel也与ross约会”。
• 队列是先进先出（FIFO）的。
• 栈是后进先出（LIFO）的。
• 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
• 对于检查过的人，务必不要再去检查，否则可能导致无限循环。