首页 > 代码库 > 《大话数据结构》笔记(7-3)--图:图的遍历
《大话数据结构》笔记(7-3)--图:图的遍历
第七章 图
图的遍历
从图中某一个顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)。
深度优先遍历(Depth First Search, DFS)
深度优先遍历(类似树的前序遍历)从图中某个顶点 v 出发,访问此顶点,然后从 v 的未被访问的邻接点出发深度优先遍历图,直至图中所有和 v 有路径相通的顶点都被访问到。若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起点,重复上述过程,直至图中所有顶点都被访问为止。
如果我们用的是邻接矩阵的方式,则代码如下:(时间复杂度为O(n2))
如果图结构是邻接表结构,则代码如下:(时间复杂度为O(n+e))
广度优先遍历(Breadth_First_Search, BFS)
《大话数据结构》笔记(7-3)--图:图的遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。