整个网站与网站模板的区别,单页网站怎么做竞价,wordpress 赞,公司注册费用流程图的搜索#xff08;一#xff09;#xff1a;广度优先搜索算法和深度优先搜索算法
本章主要记录了图的搜索算法#xff0c;和可以解决图的基本问题——最短路径问题的算法。本章主要对图搜索的相关算法进行了介绍#xff1a;广度优先搜索算法、深度优先搜索算法。
下一…图的搜索一广度优先搜索算法和深度优先搜索算法
本章主要记录了图的搜索算法和可以解决图的基本问题——最短路径问题的算法。本章主要对图搜索的相关算法进行了介绍广度优先搜索算法、深度优先搜索算法。
下一章将继续介绍贝尔曼-福特算法、狄克斯特拉算法、A*算法。 离散数学中的图 上图中的圆圈叫作“顶点”也叫“结点”连接顶点的线叫作“边”。也就是说由顶点和连接每对顶点的边所构成的图形就是图。
加权图 有权的边就可以表示顶点之间的“连接程度”
有向图 可以控制方向。
同时有向图也可与加权图结合
根据搜索的顺序不同,图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。
广度优先搜索
广度优先搜索是一种对图进行搜索的算法。假设我们一开始位于某个顶点即起点此时并不知道图的整体结构而我们的目的是从起点开始顺着边搜索直到到达指定顶点即终点。在此过程中每走到一个顶点就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。 设置A为起点G为终点。从A开始搜索将可以从A直达的三个顶点BCD设为下一步候补顶点。 从候补顶点中选出一个顶点。优先选择最早成为候补的那个顶点如果多个顶点同时成为候补那么可以随意选择其中一个。 此处选择了B继续往下搜索。将可以从 B 直达的两个顶点 E 和 F 设为候补顶点。**此时最早成为候补顶点的是C和D于是需要回到C和D继续往下。**依次循环直到找到目标点。
这个例子的搜索顺序为A、B、C、D、E、F、H、I、J、K。 注意候补顶点是用“先入先出”(FIFO)的方式来管理的,因此可以使用“队列”这个数据结构。数据结构复习链表、数组、栈、队列、哈希表、堆、二叉树-CSDN博客
广度优先搜索的特征为从起点开始由近及远进行广泛的搜索。因此目标顶点离起点越近搜索结束得就越快。
*以上例子没有闭环的图叫做“树”。如果图为闭环起点和终点是同一个顶点则搜索步骤相同。
深度优先算法
与广度优先搜索不同深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止,然后再折返,开始搜索下一条候补路径。 主要的区别在于候补顶点的选择不同。与广度优先搜索算法相同起点从A开始并从B、C、D开始往下选择。随机选择了B后候补顶点变为E、F。与广度优先搜索算法不同的是此处则继续选择最新成为候补顶点的点开始往下继续搜索。
这个例子搜索顺序为 A、B、E、K、F、C、H。
候补顶点是用“后入先出”LIFO的方式来管理的因此可以使用“栈”这个数据结构。数据结构复习链表、数组、栈、队列、哈希表、堆、二叉树-CSDN博客
深度优先搜索的特征为沿着一条路径不断往下进行深度搜索。
参考资料我的第一本算法书 (石田保辉 宮崎修一)
