算法图解笔记:广度优先搜索

(点击
上方公众号
,可快速关注)

你经常需要解决最短路径问题(shorterst-path problem)。解决最短路径问题的算法被称为 广度优先搜索
。广度优先搜索算法最早由Edward F. Moore 1959年在“如何从迷宫中寻找出路”这一问题中提出。
广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索可以:

  1. 编写国际跳棋AI,计算最少走多少步就可获胜;
  2. 编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方;
  3. 根据你的人际关系网络找到关系最近的医生。

要解决最短路径问题,需要两个步骤。

  1. 使用图来建立问题模型。
  2. 使用广度优先搜索解决问题。

图是什么

图用于模拟不同的东西是如何相连的。图由 节点
(node)和
(edge)组成。一个节点可能与众多节点直接相连,这些节点被称为 邻居
。树是一种特殊的图,其中没有往后指的边。

在图中,边用来表示节点之间的关系,若关系是有方向的,则图为 有向图
(directed graph),此时图中的边有箭头。若关系没有方向,则图为 无向图
(undirected graph),此时图中的边没有箭头,直接相连的节点互为邻居。


如上图是有向图,Rama是Alex的邻居。

广度优先搜索

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

  • 第一类问题:从节点A出发,有前往节点B的路径吗?
  • 第二类问题:从节点A出发,前往节点B的哪条路径最短?

两类问题没有本质区别,在实现层面仅仅第二类需要携带路径的信息,因为最终通常需要返回这个路径。

示例:假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。

算法原理:
(1)创建一个朋友名单。
(2)依次检查名单中的每个人,看看他是否是芒果销售商。
(3)假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。检查名单中的每个人时,你都将其朋友加入名单。
若找到,则表示你与芒果销售商有联系;由于在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系,我们找到的芒果销售商也是关系最近的。
执行过程中,一度关系在二度关系之前加入查找名单,所以我们优先检查一度关系,然后才到二度,依次进行。这需要存储名单的数据结构有“先进先出”的特性,这种数据结构就是队列(queue)。

队列

类似于栈,队列也是一种操作受限的数据结构,你不能随机地访问队列中的元素。队列只支持两种操作: 入队
出队

队列是一种先进先出(First In First Out, FIFO
)的数据结构,而栈是一种后进先出(Last In First Out, LIFO
)的数据结构。

实现图

使用散列表存储每个节点与邻近节点关系。

graph = {}

graph["you"] = ["alice", "bob", "claire"]

graph["bob"] = ["anuj", "peggy"]

graph["alice"] = ["peggy"]

graph["claire"] = ["thom", "jonny"]

graph["anuj"] = []

graph["peggy"] = []

graph["thom"] = []

graph["jonny"] = []

实现算法

算法的工作原理:

需要注意:检查一个人之前,要确认之前没检查过他,这很重要,因为有可能会导致无限循环。
完整算法如下:

from collections import deque


graph = {} graph["you"] = ["alice", "bob", "claire"] graph["bob"] = ["anuj", "peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom", "jonny"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = []

def person_is_seller(name): return name[-1] == 'm'
def search(name): search_queue = deque() search_queue += graph[name] searched = [] while search_queue: person = search_queue.popleft() if not person 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(V + E),其中V为顶点(vertice)数,E为边数。