专栏首页章鱼的慢慢技术路《算法图解》第六章笔记_广度优先搜索

《算法图解》第六章笔记_广度优先搜索

软件环境:Python 3.7.0b4

一、算法描述

假设你经营着一家芒果农场,需要寻找芒果销售商,以便将芒果卖给他。为此,我们可以通过广度优先搜索算法,在朋友中查找出符合条件的芒果销售商。

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

  • 第一类问题:从节点A出发,有前往节点B的路径吗?(在你的人际关系网中,有芒果销售商吗?)
  • 第二类问题:从节点A出发,前往节点B的哪条路径最短?(哪个芒果销售商与你的关系最近?)

二、实现图

将下列关系图用散列表实现

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

注:Anuj、Peggy、Thom和Jonny都没有邻居,这是因为虽然有指向他们的箭头,但没有从他们出发指向其他人的箭头。这被称之为有向图(directed graph),其中的关系是单向的。而无向图(undirected graph)没有箭头,直接相连的节点互为邻居。

三、实现算法

概述广度优先搜索算法的工作原理:

完整实现代码如下:

from collections import deque

def person_is_seller(name):
      return name[-1] == 'm'

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

四、小结

  • 队列是先进先出的。
  • 栈是后进先出的。
  • 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必须是队列。
  • 对于检查过的人,务必不要再去检查,否则可能导致无限循环。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《算法图解》第六章笔记

    Zoctopus
  • 《算法图解》第七章笔记_迪杰斯特拉算法

    Zoctopus
  • 【总结】牛客职播第十期:程盟有你,way来可期

    Zoctopus
  • 《算法图解》第六章笔记

    Zoctopus
  • SAP最佳业务实践:FI–应付账款(158)-7 F110支付发票

    4.8 F110选择需要支付的发票(运行付款建议) 这一步骤将选择需要支付的发票。 必须不激活支付发布清单和直联支付(EPIC)应用程序。 如果激活了支付发布清...

    SAP最佳业务实践
  • 现在,Serverless 真的已经成熟了吗?

    每年,软件工程行业都会冒出各种新工具和新趋势。由于我已经研究一段时间了,我想是时候开始开发一个像样的雷达工具,来发现哪些趋势将产生持久的影响,而哪些趋势将虎头蛇...

    深度学习与Python
  • mysql索引优化

    当数据保存在磁盘类存储介质上时,它是作为数据块存放。这些数据块是被当作一个整体来访问的,这样可以保证操作的原子性。硬盘数据块存储结构类似于链表,都包含数据部分,...

    哲洛不闹
  • CS229 课程笔记之十五:强化学习与控制

    本章将开始介绍「强化学习」与适应性控制。在监督学习中,对于训练集我们均有明确的标签,算法只需要模仿训练集中的标签来给出预测即可。但对于某些情况,例如序列性的决策...

    口仆
  • 大索引技术,大数据的未来

    不管你信也好,不信也好,大数据时代真的来临了,随着Hadoop技术的普及,其生态圈发展的越来越壮大,Hive、Hbase、Spark、Storm等的一系列新名词...

    用户1756920

扫码关注云+社区

领取腾讯云代金券