7.4 图的连通性问题

举报
C语言入门到精通 发表于 2021/02/18 00:34:49 2021/02/18
【摘要】 01无向图的连通分量和生成树1、在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。2、对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。02有向图的强连通分量1、深度优先搜索是求有向图的强连通分量的一个新的有效方法。2、在有向图G上,从...

01无向图的连通分量和生成树


1、在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。

2、对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。


02有向图的强连通分量


1、深度优先搜索是求有向图的强连通分量的一个新的有效方法。

2、在有向图G上,从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历,并按其所有邻接点的搜索都完成的顺序将顶点排列起来。

3、在有向图G中,从最后完成搜索的顶点出发,沿着以该顶点为头的弧作逆向的深度优先搜索遍历,若此次遍历不能访问到有向图中所有顶点,则从余下的顶点中最后完成搜索的的那个顶点出发,继续作逆向的深度优先搜索遍历,一次类推,直至有向图中所有顶点都被访问到为止。


03最小生成树


1、构造最小生成树可以有多种算法,其中多数算法利用了最小生成树的一种称为MST的性质。

2、普利姆算法和克鲁斯卡尔算法是两个利用MST性质构造最小生成树的算法。


04关节点和重连通分量


1、假若在删除顶点以及顶点相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,称顶点为该图的一个关节点。

2、一个没有关节点的连通图称为是重连通图。

C语言 | 大写字母A转换为小写a mp.weixin.qq.com图标

文章来源: zhuanlan.zhihu.com,作者:小林C语言,版权归原作者所有,如需转载,请联系作者。

原文链接:zhuanlan.zhihu.com/p/338749765

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。