bfs和dfs的应用实例分析


本篇文章给大家分享的是有关bfs和dfs的应用实例分析,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。图结构在解决许多网络相关的问题时直到了重要的作用。比如,用来确定在互联网中从一个结点到另一个结点(一个网络到其他网络的网关)的最佳路径。一种建模方法是采用无向图,其中顶点表示网络结点,边代表结点之间的联接。使用这种模型,可以采用广度优先搜索来帮助确定结点间的最小跳数。如图1所示,该图代表Internet中的6个网络结点。以node1作为起点,有不止1条可以通往node4的路径。都是可行的路径。广度优先搜索可以确定最短路径选择,即,一共只需要两跳。我们以bfs作为广度优先搜索的函数名(见示例1及示例2)。该函数用来确定互联网中两个结点之间的最小跳数。这个函数有3个参数:graph是一个图,在这个问题中就代表整个网络;start代表起始的顶点;hops是返回的跳数链表。函数bfs会修改图graph,因此,如果有必要的话在调用该函数前先对图创建拷贝。另外,hops中返回的是指向graph中实际顶点的指针,因此调用者必须保证只要访问hops,graph中的存储空间就必须保持有效。graph中的每一个顶点都是一个BfsVertex类型的结构体(见示例1),该结构体有3个成员:data是指向图中顶点的数据域指针,color在搜索过程中维护顶点的颜色,hops维护从起始顶点开始到目标顶点的跳数统计。match函数是由调用者在初始化graph时作为参数传递给graph_init的。match函数应该只对BfsVertex结构体中的data成员进行比较。bfs函数将按照前面介绍过的广度优先搜索的方式来计算。为了记录到达每个顶点的最小跳数,将每个顶点的hop计数设置为与该顶点邻接的顶点的hop计数加1。对于每个发现的顶点都这样处理,并将其涂成灰色。每个顶点的颜色和跳数信息都由邻接表结构链表中的BfsVertex来维护。最后,加载hops中所有跳数未被标记为-1的顶点。这些就是从起始顶点可达的顶点。bfs的时间复杂度为O(V+E),这里V代表图中的顶点个数,E是边的个数。这是因为初始化顶点的颜色属性以及确保起始顶点存在都需要O(V)的运行时间,广度优先搜索中的循环的复杂度是O(V+E),加载跳数统计链表的时间为O(V)。示例1:广度优先搜索的头文件示例2:广度优先搜索的实现有时候,我们必须根据各种事物间的依赖关系来确定一种可接受的执行顺序。比如,在大学里必须满足一些先决条件才能选的课程,或者一个复杂的项目,其中某个特定的阶段必须在其他阶段开始之前完成。要为这一类问题建模,可以采用优先级图,其采用的是有向图的思路在优先级图中,顶点代表任务,而边代表任务之间的依赖关系以必须先完成的任务为起点,以依赖于此任务的其他任务为终点,画一条边即可。如下图所示,它表示7门课程及其先决条件组成的一份课程表:S100没有先决条件,S200需要S100,S300需要S200和M100,M100没有先决条件,M200需要M100,M300需要S300和M200,并且S150没有先决条件同时也不是先决条件。通过对这些课程执行拓扑排序,深度优先搜索有助于确定出一中可接受的顺序。拓扑排序将顶点排列为有向无环图,因此所有的边都是从左到右的方向。正规来说,有向无环图G=(V,E)的拓扑排序是其顶点的一个线性排序,以便如果G中存在一条边(u,v),那么线性顺序中u出现在v的前面,在许多情况下,满足此条件的顺序有多个。下面的代码示例实现了函数dfs,即深度优先搜索。该函数在这里用来对任务做拓扑排序。dfs有两个参数:graph代表图,在这个问题中则代表需要排序的任务;而参数ordered是完成拓扑排序后返回的顶点链表。调用该函数会修改图graph,因此如果有必要需要在调用前先对graph创建一个副本。另外,函数返回后链表ordered中保存了指向图graph中顶点的指针,因此调用者必须保证,一旦访问ordered中的元素就必须保证graph中的存储空间保持有效。graph中的每一个顶点都是一个DfsVertex结构体,该结构体拥有两个成员:data是指向顶点数据域部分的指针;而color在搜索过程中负责维护顶点的颜色信息。match函数是由调用者在初始化graph时通过参数传递给graph_init的,该函数应该只对DfsVertex结构体中的data成员进行比较。dfs按照深度优先的方式进行搜索。dfs_main是实际执行搜索的函数。dfs中的最后一个循环保证对图中所有未相连的元素完成了检索。在dfs_main中逐个完成顶点的搜索并将其涂黑,然后插入链表ordered的头部。最开发云主机域名后,ordered就包含完整拓扑排序后的顶点。dfs的时间复杂度是O(V+E),V代表图中的顶点个数,而E代表边的个数。这是因为初始化顶点的颜色信息需要O(V)的时间,而dfs_main的时间复杂度为O(V+E)。示例3:深度优先搜索的头文件示例4:深度优先搜索的函数实现以上就是bfs和dfs的应用实例分析,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注开发云行业资讯频道。

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 05/16 13:16
下一篇 05/16 13:37

相关推荐