《算法图解》第六章笔记

软件环境: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 条评论
登录 后参与评论

相关文章

来自专栏lgp20151222

Java的常量接口思考,项目中的常量是放在接口里还是放在类里呢?

最近在看一本书 Java与模式,里面提了一句不建议使用常量接口,甚至举了个java源码的反例,

1311
来自专栏极客猴

Python 中连接字符串效率最高的方式是哪种呢?

在编码过程中,我们经常需要对字符串进行连接处理操作。如果我们能使用优雅的方式来处理字符串连接,那么程序内存开销会小很多。

942
来自专栏北京马哥教育

Python 的正则表达式彩蛋

虽然我觉得在 Python 的标准库里的确有不少很恶心的库,但是 re 库肯定不属于这种。尽管它真的有年头没有更新了,但是在我看来,仍不失为动态语言中最好的库...

2887
来自专栏小詹同学

Python系列之零——从零说起!!!

2017年可谓是人工智能元年,要问哪个行业最火,詹小白不敢确定,但要问哪个编程语言最热门,好吧,詹小白还是不敢说太满。但是!至少从舆论Pytho...

36610
来自专栏老九学堂

1分钟彻底理解C语言指针的概念

计算机中所有的数据都必须放在内存中,不同类型的数据占用的字节数不一样,例如 int 占用4个字节,char 占用1个字节。为了正确地访问这些数据,必须为每个字节...

4658
来自专栏互联网技术栈

读《重构:改善既有代码的设计》

984
来自专栏顶级程序员

让你的 Python 代码优雅又地道

在Python社区文化的浇灌下,演化出了一种独特的代码风格,去指导如何正确地使用Python,这就是常说的pythonic。一般说地道(idiomatic)...

4535
来自专栏北京马哥教育

如何写出优雅又地道的Python代码?

译序 如果说优雅也有缺点的话,那就是你需要艰巨的工作才能得到它,需要良好的教育才能欣赏它。 —— Edsger Wybe Dijkstra 在Python社...

35810
来自专栏AI科技大本营的专栏

送书 | Python编程:从入门到实践

本文摘自《Python编程:从入门到实践》一书,本书是Amazon编程入门类榜首图书,是一本全面的Python编程从入门到实践教程,带领读者快速掌握编程基础知识...

57310
来自专栏郭霖

Android最佳性能实践(三)——高性能编码优化

在前两篇文章当中,我们主要学习了Android内存方面的相关知识,包括如何合理地使用内存,以及当发生内存泄露时如何定位出问题的原因。那么关于内存的知识就讨论到这...

20610

扫码关注云+社区

领取腾讯云代金券