前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >5.3.3 图的遍历与图的连通性

5.3.3 图的遍历与图的连通性

作者头像
week
发布2018-08-24 15:33:41
7200
发布2018-08-24 15:33:41
举报
文章被收录于专栏:用户画像

图的遍历算法可以用来判断图的连通性。

对于无向图来说,如果无向图是连通的,则从任一结点出发,仅需一次遍历就能够访问图中所有顶点;

如果无向图是非连通的,则从某一个顶点出发,一次遍历只能访问到该顶点所在连通分量的所有顶点,而对于图中其他连通分量的顶点无法通过这次遍历访问。

对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问图中的所有顶点,否则不能访问到所有顶点。

故而在BFSTraverse()和DFSTraverse()中添加了第二个for循环,再选取初始点,继续进行遍历,以防止一次无法遍历图中所有顶点。

对于无向图,上述两个函数调用BFS(G,i)或DFS(G,i)的次数等于图中的连通分量树;

而对于有向图,则不是这样没因为一个连通的有向图分为强连通的和非强连通的,它的连通子图也分为强连通分量和非强连通分量,非强连通分量一次调用BFS(G,i)或DFS(G,i)无法访问到该连通分量的所有顶点。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016年09月14日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档