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

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

    [复制链接]

    883

    主题

    941

    帖子

    3575

    积分

    管理员

    Rank: 9Rank: 9Rank: 9

    积分
    3575
    基情
    1843
    发表于 2016-9-9 23:28:29 | 显示全部楼层 |阅读模式
    有向图的连通性不同于无向图的连通性,可分为弱连通、单侧连通和强连通。这里仅就有向图的强连通性以及强连通分量的判定进行介绍。

    深度优先搜索是求有向图的强连通分量的一个有效方法。假设以十字链表作有向图的存储结构,则求强连通分量的步骤如下:

    (1)在有向图G 上,从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历,并按其所有邻接点的搜索都完成(即退出DFS 函数)的顺序将顶点排列起来。此时需对8.3.1中的算法作如下两点修改:(a)在进入DFSTraverseAL 函数时首先进行计数变量的初始化,即在入口处加上count=0 的语句;(b)在退出函数之前将完成搜索的顶点号记录在另一个辅助数组finished[vexnum] 中,即在函数DFSAL 结束之前加上finished[++count]=v 的语句。

    (2)在有向图G 上,从最后完成搜索的顶点(即finished[vexnum-1]中的顶点)出发,沿着以该顶点为头的弧作逆向的深度搜索遍历,若此次遍历不能访问到有向图中所有顶点,则从余下的顶点中最后完成搜索的那个顶点出发,继续作逆向的深度优先搜索遍历,依次类推,直至有向图中所有顶点都被访问到为止。此时调用DFSTraverseAL 时需作如下修改:
    函数中第二个循环语句的边界条件应改为v 从finished[vexnum-1]至finished[0]。

    由此,每一次调用DFSAL 作逆向深度优先遍历所访问到的顶点集便是有向图G 中一个强连通分量的顶点集。

    例如图8.14 (a) 所示的有向图,假设从顶点v1 出发作深度优先搜索遍历,得到finished数组中的顶点号为(1,3,2,0) ;则再从顶点v1 出发作逆向的深度优先搜索遍历,得到两个顶点集{ v1, v3, v4}和{ v2},这就是该有向图的两个强连通分量的顶点集。

    上述求强连通分量的第二步,其实质为:
    (1)构造一个有向图Gr,设G=(V,{A}),则Gr=(Vr,{Ar})对于所有< vi,,vj>∈A,必有< vj, vi >∈Ar。即Gr 中拥有和G 方向相反的弧;
    (2)在有向图Gr 上,从顶点finished[vexnum-1] 出发作深度优先遍历。可以证明,在Gr 上所得深度优先生成森林中每一棵树的顶点集即为G 的强连通分量的顶点集。


    显然,利用遍历求强连通分量的时间复杂度亦和遍历相同。


    上一篇:8.4 图的连通性—无向图的连通性
    下一篇:8.4 图的连通性—生成树和生成森林
    回复

    使用道具 举报

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

    本版积分规则

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

    GMT+8, 2017-5-27 14:19 , Processed in 0.652390 second(s), 47 queries .

    Powered by 深嵌论坛 X3.2

    © 2001-2013 Comsenz Inc.

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