• 欢迎访问废江网站,承蒙遇见 QQ群
  • 本站将致力于推送优质的java知识以及算法,开源代码!

图的遍历及应用

算法笔记 站点默认 4年前 (2019-11-10) 1282次浏览 已收录 1个评论 扫描二维码
文章目录[隐藏]

图的遍历

图的两种遍历方法:DFS和BFS

dfs遍历代码(教材上的)

bfs遍历代码

图的遍历的应用

基于深度优先遍历的应用

假设图采用邻接表存储,设计一个算法,判断无向图g是否连通。若连通返回true,否则返回false

只需要设计一个函数,将visited数组初始化为0,然后调用dfs函数,从任何一个顶点开始遍历,只会遍历一遍visited数组,当我们发现有值为0的元素就说明该图是不连通的,因为有顶点没有被访问到

设计一个算法判断从顶点u到v是否存在简单路径

稍微改动一下dfs函数,增加两个形参,v和has,其中has表示判断,v则表示终点,dfs起点从u开始,中间添加条件判断语句,当u等于v时候,则找到了。参数中,u不断变换,就是dfs的带入顶点,v则一直不变

设计一个算法,输出从顶点u到v的一条简单路径(假设从顶点u到v至少有一条简单路径)

和上面的一样,稍微修改一下dfs函数,增加一个path数组类型的形参,和d形参(表示路径长度),和v形参(终点)

设计一个算法,输出从顶点u到v的所有条简单路径(假设从顶点u到v至少有一条简单路径

采用回溯法

设计一个算法,输出图g中从顶点u到v的长度为l的所有简单路径

增加一个形参l,在判断语句中增加d==l即可,形参l为指定长度

教材还有两个应用,太难这里不写了,看看以后刷题要是遇到该类问题,后面再补

基于广度优先遍历的应用


废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:图的遍历及应用
喜欢 (2)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(1)个小伙伴在吐槽