理解广度优先搜索算法:你朋友里有芒果销售商吗?

难度: 中等    相关标签:广度优先搜索算法

题目来源

看了《算法图解》第六章后,感觉作者广度优先搜索讲解得很到位,例子和算法都很好,在 LeetCode 没找到类似的题目,就想着将他的例子作为一个题目吧!

题目描述

假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。可在你的朋友中查找,假设 m 结尾的朋友就是芒果经营商,请编写一个算法,查看你朋友(人际关系网)里是否有芒果销售商?你的朋友是一度关系,朋友的朋友是二度关系,以此类推。

关系表示方式如下(Python dict):

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"] = []

解题方案

思路

  • 标签:广度优先搜索先进先出队列
  • 使用广度优先搜索。广度优先搜索解决两类问题:1. A 节点是否能到达 B 节点?2. A 节点到 B 节点最短路径(最少换乘数)是多少?
  • 这道题就是属于第一类问题
  • 使用先进先出队列,将你的朋友加入队列,依次检查你的朋友是否是芒果经销商,如果不是,将朋友的朋友链接到队尾,重复操作,直到找到芒果经销商或者所有人都被加入队列
  • 因为存在某个人可能同时是多个人的朋友,避免被重复加入队列,使用一个数组记录检查过的人
  • 时间复杂度:O (V + E) = O (V) + O (E)。 V: vertice 顶点(人数),E: edge 边数(箭头的数量)

代码

Python:

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 # ←------如果到达了这里,就说明队列中没人是芒果销售商


def person_is_seller(name):
return name[-1] == 'm' # 以 m 结尾就是芒果商


search('you')

图解

结语

《算法图解》是一本很好的算法入门书,建议想系统学习算法的小伙伴可以先看一下这本书。

广度优先搜索与深度优先搜索区别:

  • 广度优先搜索:队列实现
  • 深度优先搜索:堆栈实现
DeppWang wechat
个人公众号