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

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

题目来源

看了《算法图解》第六章后，感觉作者广度优先搜索讲解得很到位，例子和算法都很好，在 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')

• Java
• JavaScript

图解

结语

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

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

• 广度优先搜索：队列实现
• 深度优先搜索：堆栈实现