京市保障性住房建设投资中心网站,重庆云阳网站建设,西安网站搭建,百度公司数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第6章广度优先搜索
6.1 简介 广度优先搜索—breadth-first search#xff0c;BFS. 主要内容图和队列。 广度优先搜索能让你能够找出两样东西之间的最短距离#xff0c;比如#xff1a;编写国际跳…数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第6章广度优先搜索
6.1 简介 广度优先搜索—breadth-first searchBFS. 主要内容图和队列。 广度优先搜索能让你能够找出两样东西之间的最短距离比如编写国际跳棋AI(Artificial Intelligence)计算最少走多少步可以获胜或者根据你的人际关系网络找到关系最近的医生。
需要两个步骤 1使用图来建立问题模型。 2使用广度优先搜索解决问题。 6.2 什么是图 图由节点和边组成。一个节点可能与众多节点直接相连这些节点被称为邻居。
6.3 广度优先搜索 广度优先搜索是一种用于图的查找算法可帮助回答两类问题
第一类问题从节点A出发有前往节点B的路径吗第二类问题从节点A出发前往节点B的哪条路径最短
假设你经营着一个芒果农场需要寻找芒果销售商以便将芒果卖给他。为此你可在朋友中查找。
首先创建一个朋友名单然后依次检查名单中的每个人是否是芒果销售商
假设你没有朋友是芒果销售商那么你就必须在朋友的朋友中查找。
检查名单中的每个人时你都将其朋友加入名单。
6.3.1 查找最短路径 一度关系胜过二度关系二度关系胜过三度关系以此类推。
广度优先搜索不仅查找从A到B的路径而且找到的是最短的路径。
只有按添加顺序查找时才能实现这样的目的。
队列(queue)实现按添加顺序进行检查的数据结构。
6.3.2 队列 队列能够实现按添加顺序进行检查的需求。 队列不能随机访问只能支持两种操作入队和出队。
先加入的元素将先出队并被检查。
队列是一种先进先出(First In First Out)的数据结构 栈是一种后进先出(Last In First Out)的数据结构。
6.4 实现图 图是由多个节点组成需要使用代码来实现图。 每个结点都与邻近结点相连散列表可以很好的实现这种关系。
散列表将键映射到值比如将你这个节点映射到所有邻居。
表示这种映射关系的Python代码如下
graph {} #前面提到Python中是用字典来实现散列表。{}表示生成空字典。
graph[you] [alice, bob, claire]
#you被映射到了一个数组因此graph[you]是一个数组包含了you的所有邻居。 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] []
#散列表是无序的因此添加键-值对的顺序不关紧要。有向图(directed graph)有一个节点指向相邻节点单向关系。上图中Anuj,Peggy,Thom,Jonny都没有邻居因为他们没有指向其他节点。
无向图(undirected graph)没有箭头直接连接的节点互为邻居。 下面两图等效
6.5 实现算法 队列实现原理
#首先使用函数deque来创建一个双端队列。
from collections import deque
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 Trueelse:search_queue graph[person] #如果不是将此人的朋友(相邻节点)都加入搜索队列。searched.append(person) #并将此人添加到以搜索过的列表避免再次搜索此人。return False #如果到达这里说明队列中没有芒果销售商#假设以姓名结尾为m的人为芒果销售商。
def person_is_seller(name):return name[-1] m #名字末尾为msearch(you) #函数调用为什么要避免被重复搜索(检查) 上图中Peggy既是Alice的朋友又是Bob的朋友因此她将被加入队列两次因此搜索队列将包含两个Peggy。 检查完一个人后应将其标记为已检查且不再检查如果不这样做就可能会导致无限循环。
因为搜索队列将在包含你和包含Peggy之间反复切换从而造成无限循环。
列表是有序的。如果任务A依赖于任务B在列表中任务A就必须在任务B后面这被称为拓扑排序使用它可根据图创建一个有序表。
6.5.1 树 树是特殊的图其中没有往后指的边。
树是图的子集树都是图图不一定是树。
6.6 小结
队列是先进先出。栈是后进先出。注意避免导致无限循环。
——持续修改完善中…
