请选择 进入手机版 | 继续访问电脑版
    查看: 337|回复: 0

    8.4 图的连通性—无向图的连通性

    [复制链接]

    883

    主题

    941

    帖子

    3575

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    3575
    基情
    1843
    发表于 2016-9-9 23:28:25 | 显示全部楼层 |阅读模式
    判定一个图的连通性是图的一个应用问题,我们可以利用图的遍历算法来求解这一问题。本节将重点讨论无向图的连通性、有向图的连通性、由图得到其生成树或生成森林以及连通图中是否有关节点等几个有关图的连通性的问题。

    在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。例如,图8.5 (a)是一个非连通图G3,按照图8.18 所示G3 的邻接表进行深度优先搜索遍历,需由算法8.5 调用两次DFS(即分别从顶点A 和D 出发),得到的顶点访问序列分别为:
    A B F E C E
    这两个顶点集分别加上所有依附于这些顶点的边,便构成了非连通图G3 的两个连通分量,如图8.5(b) 所示。

    因此,要想判定一个无向图是否为连通图,或有几个连通分量,就可设一个计数变量count,初始时取值为0,在算法8.5 的第二个for 循环中,每调用一次DFS,就给count 增1。这样,当整个算法结束时,依据count 的值,就可确定图的连通性了。

    8.4 图的连通性—无向图的连通性

    8.4 图的连通性—无向图的连通性
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|小黑屋|网站地图|DZ商业模板|VR福利资源|嵌入式Linux论坛 ( 粤ICP备15085165号-2 )

    GMT+8, 2017-10-21 07:50 , Processed in 0.077649 second(s), 26 queries .

    Powered by 深嵌论坛 X3.4

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表