做此广告的网站,平面设计师磨刀石,可以自己做网站的网址,企业 wordpress 主题目录
1#xff09;图简介
2#xff09;图是什么
3#xff09;广度优先搜索
4#xff09;实现图
5#xff09;实现算法
6#xff09;小结 本章内容; 学习使用新的数据结构图来建立网络模型#xff1b; 学习广度优先搜索#xff1b; 学习有向图和无向图…目录
1图简介
2图是什么
3广度优先搜索
4实现图
5实现算法
6小结 本章内容; 学习使用新的数据结构图来建立网络模型 学习广度优先搜索 学习有向图和无向图 学习拓扑排序这种排序算法指出了节点之间的依赖关系。
1图简介
假设你住在旧金山要从双子峰前往金门大桥。你想乘公交车前往并希望换乘最少。可乘坐的公交车如下 从图中我们可以发现前往进门大桥的最短路径需要三步这种问题被称为最短路径问题(shorterst-path problem)。 要确定如何从双子峰前往金门大桥需要两个步骤 使用图来建立问题模型。 使用广度优先搜索解决问题。
2图是什么
图模拟一组连接图由节点(node)和边(edge)组成。 3广度优先搜索
广度优先搜索是一种用于图的查找算法。可回答两类问题
从A节点有前往节点B的路径吗哪条路径最短
下面来看一个例子假设你经营这一个芒果农场需要寻找芒果经销商以便将芒果卖给他。为此你可在朋友中查找。 这种查找很简单首先创建一个朋友名单。然后依次检查名单中的每个人看看他是否是芒果销售商。 假设你没有朋友是芒果销售商那么你必须在朋友的朋友中查找。 检查名单中的每个人时你都将其朋友加入名单。 1.查找最短路径
人物关系如图所示 在你看来一度关系胜过二度关系二度关系胜过三度关系等等。因此你应现在一度关系中搜索确定其中没有芒果销售商后才在二度关系中搜索。广度优先搜索就是这样做的
2.队列
队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队如果你排在他前面你讲先上车。队列只有两种操作入队和出队。 队列是一种先进先出First In First OutFIFO的数据结构而栈是一种后进先出Last In First Out, LIFO的数据结构。 4实现图
使用散列表表示节点与节点之间的关系 有向图与无向图关系如图 5实现算法
概述一下算法原理 寻找芒果销售商的Python源码为
#从标准库导入队列元素
from collections import dequedef person_is_seller(name):return name[-1] mgraph {}
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]# This array is how you keep track of which people youve searched before.searched []while search_queue:#队首元素出队person search_queue.popleft()# Only search this person if you havent already searched them.if not person in searched:if person_is_seller(person):print person is a mango seller!return Trueelse:search_queue graph[person]# Marks this person as searchedsearched.append(person)return Falsesearch(you)6小结
广度优先搜索指出是否有从A到B的路径。 如果有广度优先搜索将找出最短路径。面临类似于寻找最短路径的问题时可尝试使用图来建立模型再使用广度优先搜索来解决问题。有向图中的边为箭头箭头的方向指定了关系的方向。 无向图中的边不带箭头其中的关系是双向的。 队列是先进先出FIFO的。 栈是后进先出LIFO的。你需要按加入顺序检查搜索列表中的人否则找到的就不是最短路径因此搜索列表必须是队列。对于检查过的人务必不要再去检查否则可能导致无限循环。
