《算法图解》总结第 6 章：广度优先搜索

2023-11-17

仅用于记录学习，欢迎批评指正，大神勿喷

系列文章目录

文章目录

系列文章目录
基础知识
应用案例
算法实现

基础知识

一、最短路径问题

举例说明最短路径的含义：假设某人居住在旧金山，想要乘公交从双子峰前往金门大桥，换乘最少的的乘车路线就被称为最短路径。这种问题被称为最短路径问题。

二、广度优先搜索

解决最短路径问题的算法被称为广度优先搜索。
广度优先搜索是一种用于图的查找算法，可回答两类问题：
（1）从节点A出发，是否有前往节点B的路径；
（2）如果有，寻找前往节点B的最短路径。

三、队列

队列类似于栈，不能随机访问队列中的元素，队列只支持两种操作：入队和出队，与栈【stack()】先进后出的数据结构不同的是，队列【deque()】是一种先进先出的数据结构。

四、图

图由节点和边组成，一个节点可能与众多节点直接相连，这些节点被称为邻居。图模拟一组连接，用于模拟不同的东西是如何相连的。可用散列表来实现图，键-值对的添加顺序无关紧要，因为散列表是无序的，图分为有向图和无向图，有向图分为单向图和双向图，双向图和无向图是等价的，均表示直接相连的节点互为邻居。

应用案例

案例：从“你”的朋友中找到关系最近的芒果销售商，朋友是一度关系，朋友的朋友是二度关系。
案例分析：
首先，建立“你”的人际关系：

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

其次，为了辨别亲疏关系，引入队列

from collections import deque
search_deque = deque()
search_deque += graph["you"]
# 只要队列不为空，提取队列第一人
while search_deque:
    person = search_deque.popleft()
# 判断这个人是不是芒果销售商
    # 如果是，打印名字加是个芒果销售商（注：要编写这个人是否是芒果销售商的函数）
    if people_is_seller(person):
        print(person + " is a mango seller")
    # 如果不是，在队列后面添加这个人的人际关系
    else:
        search_deque += graph[person]

将某人是否是芒果销售商的函数补充完整，在此假设某人姓名的结尾是以“m”结尾，那么此人是芒果商。编码如下：

# 定义某人是否是芒果销售商函数
def people_is_seller(name):
    return name[-1] == "m"

此外，我们还观察到“peggy”既是“bob”的朋友，也是“alice”的朋友，当“bob”和“alice”均不是芒果销售商时，“peggy”将会被加入队列两次，但是我们仅需检查一次，为避免浪费，我们在检查过后将其标记为已检查，且不再检查其他，同时此措施也可避免当两人或多人之间的人际关系是环形时造成无限循环。

算法实现

完整Python代码如下：

# 引入队列
from collections import deque

# 创建散列表
graph = {}
graph["you"] = ["alice","bob","claire"]
graph["bob"] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["tom","jonny"]
graph["anuj"] =[]
graph["peggy"] = []
graph["tom"] = []
graph["jonny"] = []

# 定义某人是否是芒果销售商函数
def people_is_seller(name):
    return name[-1] == "m"

# 广度优先搜索
def search(name):
    # 创建队列
    search_deque = deque()
    # 加入队列
    search_deque += graph["you"]
    # 创建数组记录已检查过的人
    searched = []
    # 当且仅当队列不为空时，进行广度优先搜索
    while search_deque:
        # 删除队列第一人，并将此人定义为person
        person = search_deque.popleft()
        # 检查此人是否在已检查的数组中，当且仅当没检查过才开始检查
        if not person in searched:
            # 判断此人是否是芒果销售商
            # 如果是，打印名字加是个芒果销售商
            if people_is_seller(person):
                print(person + " is a mango seller !")
             # 如果不是，在队列后面添加此人的人际关系，并将此人添加到已检查的数组中    
            else:
                search_deque += graph[person]
                searched.append(person)
    # 当队列为空时，返回False
    return False

测试：

search("you")

输出结果：

tom is a mango seller !

False

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)