kosaraju算法

编辑:野禽网互动百科 时间:2020-04-05 14:52:58
编辑 锁定
在计算机科学中,Kosaraju的算法(也称为Kosaraju-Sharir算法)是线性时间的算法来找到一个有向图强连通分量
Aho, Hopcroft 和Ullman相信这个算法是由S. Rao Kosaraju在1978在一个未发表的论文上提出的。
相同的算法还从Micha Sharir 1981年自己出版的书上被单独的发现,这个算法利用了一个事实,即转置图(同图中的每边的方向相反)具有和原图完全一样的强连通分量。[1] 
中文名
Kosaraju算法
外文名
Kosaraju's algorithm
提出者
S. Rao Kosaraju
提出时间
1978
应用学科
计算机科学
适用领域范围
图论 ACM编程

kosaraju算法算法思想

编辑
Kosaraju算法的解释和实现都比较简单,为了找到强连通分支,首先对图G运行DFS,计算出各顶点完成搜索的时间f;然后计算图的逆图GT,对逆图也进行DFS搜索,但是这里搜索时顶点的访问次序不是按照顶点标号的大小,而是按照各顶点f值由大到小的顺序;逆图DFS所得到的森林即对应连通区域。具体流程如图(1~4)[2] 
上面我们提及原图G的逆图GT,其定义为GT=(V,ET),ET={(u,v):(v,u)∈E}}。也就是说GT是由G中的边反向所组成的,通常也称之为图G的转置。在这里值得一提的是,逆图GT和原图G有着完全相同的连通分支,也就说,如果顶点s和t在G中是互达的,当且仅当s和t在GT中也是互达的。
为了方便大家理解,附下引用博客中的例图:
原图 原图
原图进行dfs 原图进行dfs
上面是第一次dfs
逆图 逆图
逆图dfs,获得强连通分量 逆图dfs,获得强连通分量
这里对逆图进行dfs,就可以得到强连通分量了。

kosaraju算法伪代码

编辑
  1. 对原图G进行深度优先遍历,记录每个节点的离开时间num[i]
  2. 选择具有最晚离开时间的顶点,对反图GT进行遍历,删除能够遍历到的顶点,这些顶点构成一个强连通分量
  3. 如果还有顶点没有删除,继续步骤2,否则算法结束

kosaraju算法c++代码

编辑
#include <iostream> /* Kosaraju求强连通分量邻接矩阵 */
#include <stack>
#include <cstdio>
#include <cstring>

usingnamespacestd;

intmap[511][511];
intnmap[511][511];
intvist[501];
stack<int>S;
intN;
intDFS1( intv ) /* vistthevnode */
{
    vist[v] = 1;
    for ( inti = 1; i <= N; i++ )
    {
        if ( !vist[i] && map[v][i] )
            DFS1( i );
    }
    S.push( v );

    return0;
}
intDFS2( intv )
{
    vist[v] = 1;
    for ( inti = 1; i <= N; i++ )
    {
        if ( !vist[i] && nmap[v][i] )
            DFS2( i );
    }
    return0;
}
intkosaraju()
{
    while ( !S.empty() )
        S.pop();
    memset( vist, 0, sizeof(vist) );
    for ( inti = 1; i <= N; i++ )
    {
        if ( !vist[i] )         /* havebeennotvist,thenvisttheinode */
        {
            DFS1( i );      /* afterdfs,cangetindexoflatestleave */
        }
    }
    intt = 0;
    memset( vist, 0, sizeof(vist) );
    while ( !S.empty() )
    {
        intv = S.top();
        S.pop();
        printf( "|%d|", v );
        if ( !vist[v] )
        {
            t++;
            DFS2( v );
        }
    }
    returnt;
}
intmain()
{
    intM, i, s, e;
    scanf( "%d%d", &N, &M );
    memset( map, 0, sizeof(map) );
    memset( nmap, 0, sizeof(nmap) );
    for ( i = 0; i < M; i++ )
    {
        scanf( "%d%d", &s, &e );
        map[s][e]    = 1;
        nmap[e][s]    = 1;
    }
    printf( "%d\n", kosaraju() ); /* 输出连通分量个数 */
    return0;
}

样例输入:
55
12
21
23
34
41
样例输出:
2
词条图册 更多图册
参考资料
词条标签:
科技