广度优先搜索 BFS

「总结自《Grokking Algotithms》这本书第六章内容」

在 BFS(Breadth-First Search) 算法中,图是什么?

图用来模拟不同东西是如何连接的。比如,在一个游戏中,模拟谁欠谁钱。如 Alex 欠 Rama 钱,将会如下所示:

下面是多个人欠钱的情况:

可以看出图是由一系列节点(node)和边(edge)组成的。一个节点可能与多个节点直接相连接,这时候这些节点称为邻居

广度优先算法

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

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

首先讲第一类问题。假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。首先,你需要在你的通讯录中查找,一个个查看过去,看其是否为芒果销售商。如果你的朋友中没有一个是芒果销售商,那么就从朋友的朋友中查找。

这时,检查名单中的每个人时,都将其朋友加入名单。这样一来,不仅需要在朋友中查找,还需要在朋友中的朋友中查找。使用这种算法将搜遍你的整个人际关系网,直到找到芒果销售商。这就是第一类问题的广度优先搜索。

第二类问题,就是在有路径的前提下,寻找最短距离。现在我们在刚才第一类问题的基础上,解决第二类问题 - 谁是关系最近的芒果销售商?

现在假设朋友是一度关系,朋友的朋友是二度关系,朋友的朋友的朋友是三度关系,以此类推。首次在一度关系中寻找;没有的话,再在二度关系中寻找。按照这个顺序检查名单中的每一个人,看其是否为芒果销售商。

因为,广度优先查找是从一度关系中开始查找的,整个遵从的是从最近的关系查找到最远的关系查找。所以,广度优先搜索找到的是最短的距离。

队列

因为 BFS 从最近的关系开始查找,所以对查找的名单也需要进行一定的排列。比方说,Alex 是一度关系,Rama 是二度关系。在添加列表的时候,Alex 是先加入列表的,Rama 是后就加入列表的。需要先检查 Alex,后检查 Rama,而不能先检查 Alex,后检查 Rama。有一个数据结构可以解决这个问题,就是队列(queue)。

队列的原理和排队等车的原理类似。先(早)排队的人先上车,队列也一样,是一种先进先出(First In First Out,简称 FIFO)的数据结构。

队列只支持两种操作:入队出队。这样先加入的元素会在后加入的元素之前出队。因此队列适合 BFS 算法。

实现图

我们可以使用散列表(Hash Table)来实现图。代码如下所示:

# 实现图
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"] = []

关系如下:

实现 BFS 算法

首先概述一下整个算法的过程:

  1. 创建一个队列,用于存储要检查的人
  2. 从队列中弹出一个人
  3. 检查这个人是否是芒果销售商
  4. 判断:
    • 是芒果销售商 → 大功告成
    • 不是 → 将这个人的所有朋友加入队列
  5. 回到第 2 步
  6. 如果队列为空,则说明你的关系网中没有芒果销售商。

代码实现:

# 实现 BFS
from collections import deque

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 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

完整代码

"""
广度优先算法
"""
import json

# 实现 BFS
from collections import deque

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 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


if __name__ == "__main__":

    # 实现图
    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"] = []

    print(json.dumps(graph, indent=4, separators=(',' , ':')))

    # 搜索
    search("you")

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C 语言实现堆排序 (Heap Sort)

    堆排序是一种基于「堆」这一数据结构的排序算法。堆是一种近似完全二叉树的结构,分为大顶堆和小顶堆这两种。

    caoqi95
  • matplotlib 绘制轮廓图和 3D 图

    matplotlib.pyplot.contourf(args, data=None, **kwargs)

    caoqi95
  • sin() 和 cos() 等函数的简单逼近

    Programming 课程布置的作业中要自己实现 sin(),cos(),exp() 等函数。这些函数都可以使用泰勒级数来逼近,如下图所示:

    caoqi95
  • 为什么要进行URL编码!!!

    我们都知道Http协议中参数的传输是"key=value"这种简直对形式的,如果要传多个参数就需要用“&”符号对键值对进行分割。

    用户5224393
  • 为什么要进行 URL 编码???

    我们都知道Http协议中参数的传输是"key=value"这种简直对形式的,如果要传多个参数就需要用“&”符号对键值对进行分割。

    Java技术栈
  • (centos7)jps 找不到命令

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    suveng
  • Web开发须知:URL编码与解码

    通常如果一样东西需要编码,说明这样东西并不适合传输。原因多种多样,如Size过大,包含隐私数据,对于Url来说,之所以要进行编码,是因为Url中有些字符会引起...

    李海彬
  • 联姻A股:中芯国际的国产“芯”梦

    近日,国内晶圆代工龙头中芯国际发布公告,宣布将谋求科创板上市。根据上市公告,中芯国际将发行的人民币股份初始数目不超过16.85亿股,占不超过截止2019年12月...

    刘旷
  • MySQL(六)DQL之常见函数

    leeqico
  • 运维平台中RESTful的Token认证

    在近期要做的RESTful服务API化的过程中,对于开放的API还是需要考虑基本的安全认证的,如果API能够随便被调用,可能对于功能来说是畅通的,如果调用...

    jeanron100

扫码关注云+社区

领取腾讯云代金券