精华内容
下载资源
问答
  • 计算有向图的连通分支个数,文件读入,输出到控制台窗口。-Computing connected components of a directed graph the number of documents read, output to the console window.
  • 有向图连通分支

    千次阅读 2016-07-18 02:26:27
    ACM模版有向图连通分支/* * 有向图连通分支(dfs/bfs邻接阵)O(n^2) * 返回分支数,id返回1..分支数的值 * 传入图的大小n和邻接阵mat,不相邻点边权0 */ #define MAXN 100 int find_components(int n, int mat[]...

    ACM模版

    有向图强连通分支

    /*
     *  有向图强连通分支(dfs/bfs邻接阵)O(n^2)
     *  返回分支数,id返回1..分支数的值
     *  传入图的大小n和邻接阵mat,不相邻点边权0
     */
    #define MAXN 100
    int find_components(int n, int mat[][MAXN], int* id)
    {
        int ret = 0, a[MAXN], b[MAXN], c[MAXN], d[MAXN], i, j, k, t;
        for (k = 0; k < n; id[k++] = 0);
        for (k = 0; k < n; k++)
        {
            if (!id[k])
            {
                for (i = 0; i < n; i++)
                {
                    a[i] = b[i] = c[i] = d[i] = 0;
                }
                a[k] = b[k] = 1;
                for (t = 1; t;)
                {
                    for (t = i = 0; i < n; i++)
                    {
                        if (a[i] && !c[i])
                        {
                            for (c[i] = t = 1, j = 0; j < n; j++)
                            {
                                if (mat[i][j] && !a[j])
                                {
                                    a[j] = 1;
                                }
                            }
                        }
                        if (b[i] && !d[i])
                        {
                            for (d[i] = t = 1, j = 0; j < n; j++)
                            {
                                if (mat[j][i] && !b[j])
                                {
                                    b[j] = 1;
                                }
                            }
                        }
                    }
                }
                for (ret++, i = 0; i < n; i++)
                {
                    if (a[i] & b[i])
                    {
                        id[i] = ret;
                    }
                }
            }
        }
        return ret;
    }
    展开全文
  • 有向图的连通分支

    2019-09-27 17:49:22
    下面介绍如何使用两个深度优先搜索过程来进行这种分解,很多有关有向图的算法都从分解步骤开始,这种分解可把原始的问题分成数个子问题,其中每个子子问题对应一个强连通分支。构造强连通分支之间的联系也就把子问题...

    在有向图G中,如果任意两个不同的顶点相互可达,则称该有向图是强连通的。有向图G的极大强连通子图称为G强连通分支

    把有向图分解为强连通分支是深度优先搜索的一个经典应用实例。下面介绍如何使用两个深度优先搜索过程来进行这种分解,很多有关有向图的算法都从分解步骤开始,这种分解可把原始的问题分成数个子问题,其中每个子子问题对应一个强连通分支。构造强连通分支之间的联系也就把子问题的解决方法联系在一起,我们可以用一种称之为分支图的图来表示这种构造。

    定义有向图G=(V,E)的分支图为GSCC=(VSCC,ESCC),其中VSCC包含的每一个结点对应于G的每个强连通分支。如果图G的对应于节点u的强连通分支中,某个结点和对应于v的强连通分支中的某个结点之间存在一条有向边,则边(u,v)ESCC。图1给出了一个实例。显而易见对于分支图有以下定理:

    定理1

    有向图G的分支图GSCC是一个有向无回路图。

    1展示了一个有向图的强连通分支的实例。(a)为有向图G,其中的阴影部分是G的强连通分支,对每个顶点都标出了其发现时刻与完成时刻,黑色边为树枝;(b)G转置图GT。图中说明了算法Strongly_Connected_Components3行计算出的深度优先树,其中黑色边是树枝。每个强连通子图对应于一棵深度优先树。图中黑色顶点b,c,gh是强连通子图中每个顶点的祖先,这些顶点也是对GT进行深度优先搜索所产生的深度优先树的树根。(c)G的每个强连通子图缩减为单个顶点后所得到的有向无回路子图(即G的分支图)。

    寻找图G=(V,E)的强连通分支的算法中使用了G的转置,其定义为:GT=(V,ET),其中ET={(v,u)V×V:(u,v)E},即ETG中的边改变方向后组成。若已知图G的邻接表,则建立GT所需时间为O(V+E)。注意到下面的结论是很有趣的:GGT有着完全相同的强连通支,即在Guv互为可达当且仅当在GT中它们互为可达。图1(b)即为图1(a)所示图的转置,其强连通支上涂了阴影。

    1强连通子图的实例

    下列运行时间为θ(V+E)的算法可得出有向图G=(V,E)的强连通分支,该算法使用了两次深度优先搜索,一次在图G上进行,另一次在图GT上进行。

    procedure Strongly_Connected_Components(G);
    begin
     1.调用DFS(G)以计算出每个结点u的完成时刻f[u];
     2.计算出GT;
     3.调用DFS(GT),但在DFS的主循环里按针f[u]递减的顺序考虑各结点(和第一行中一样计算);
     4.输出第3步中产生的深度优先森林中每棵树的结点,作为各自独立的强连通支。
    end;

    这一貌似简单的算法似乎和强连通支无关。下面我们将揭开这一设计思想的秘密并证明算法的证确性。我们将从两个有用的观察资料入手。

    引理1

    如果两个结点处于同一强连通支中,那么在它们之间不存在离开该连通支的通路。

    证明:

    uv是处于同一强连通支的两个结点,根据强连通支的定义,从uv和从vu皆有通路,设结点w在某一通路u→w→v上,所以从u可达w、又因为存在通路 v→u,所以可知从w通过路径w→v→u可达u,因此uw在同一强连通支中。因为w是任意选定的,所以引理得证。

    (证毕)

    定理2

    在任何深度优先搜索中,同一强连通支内的所有顶点均在同一棵深度优先树中。

    证明:

    在强连通支内的所有结点中,设r第一个被发现。因为r是第一个被发现,所以发现r时强连通支内的其他结点都为白色。在强连通支内从r到每一其他结点均有通路,因为这些通路都没有离开该强连通支(据引理1),所以其上所有结点均为白色。因此根据白色路径定理,在深度优先树中,强连通支内的每一个结点都是结点r的后裔。

    (证毕)

    在下文中,记号d[u]f[u]分别指由算法Strongly_Connected_Components1行的深度优先搜索计算出的发现和完成时刻。类似地,符号u→v是指G中而不是GT中存在的一条通路。

    为了证明算法Strongly_Connected_Components的正确性,我们引进符号Φ(u)表示结点u的祖宗w,它是根据算法第1行的深度优先搜索中最后完成的从u可达的结点(注意,与深度优先树中祖先的概念不同)。换句话说,Φ(u)是满足u→wf[w]有最大值的结点w

    注意有可能Φ(u)=u,因为u对其自身当然可达,所以有

    f[u]≤f[Φ[u]]                      (1)

    我们同样可以通过以下推理证明Φ(Φ(u))=Φ(u),对任意结点u,vV

    u→v说明f[Φ(v)]≤f[Φ(u)]          (2)

    因为{w|v→w}包含于{w|u→w},且祖宗结点是所有可达结点中具有最大完成时刻的结点。又因为从u可达结点Φ(u),所以(2)式表明订f[Φ(Φ(u))]≤f[Φ(u)],用Φ(u)代入(1)式中的u同样有f[Φ(u)]≤f[Φ(Φ(u))],这样f[Φ(Φ(u))]=f[Φ(u)]成立。所以有Φ(Φ(u))=Φ(u),因为若两结点有同样的完成时刻,则实际上两结点为同一结点。

    我们将发现每个强连通分支中都有一结点是其中每一结点的祖宗,该结点称为相应强连通分支的代表性结点。在对图G进行的深度优先搜索中,它是强连通支中最先发现且最后完成的结点。在对GT的深度优先搜索中,它是深度优先树的树根,我们现在来证明这一性质。

    第一个定理中称Φ(u)u的祖先结点。

    定理3

    已知有向图G=(V,E),在对G的深度优先搜索中,对任意结点uV,其祖宗Φ(u)u的祖先。

    证明:

    如果Φ(u)=u,定理自然成立。如果Φ(u)≠u,我们来考虑在时刻d[u]各结点的颜色,若Φ(u)是黑色,则f[Φ(u)]<f[u],这与不等式(1)矛盾;若Φ(u)为灰色,则它是结点u的祖先,从而定理可以得证。

    现在只要证明Φ(u)不是白色即可,在从uΦ(u)的通路中若存在中间结点,则根据其颜色可分两种情况:

    1. 若每一中间结点均为白色,那么由白色路径定理Φ(u)u的后裔,则有f[Φ(u)]<f[u],这与不等式(1)相矛盾。
    2. 若有某个中间结点不是白色,设t是从uΦ(u)的通路上最后一个非非白节点,则由于不可能有从黑色结点到白色结点的边存在,所以t必是灰色。这样就存在一条从tΦ(u)且由白色结点组成的通路,因此根据白色路径定理可推知Φ(u)t的后裔,这表明f[t]>f[Φ(u)]成立,但从ut有通路,这巧我们对Φ(u)的选择相矛盾。

    (证毕)

    推论1

    在对有向图G=(V,E)的任何深度优先搜索中,对所有uV,结点uΦ(u)处于同一个强连通分支内。

    证明:

    由对祖宗的定义有u→Φ(u),同时因为Φ(u)u的祖先,所以又有Φ(u)→u

    (证毕)

    下面的定理给出了一个关于祖宗和强连通分支之间联系的更强有力的结论。

    定理4

    在有向图G=(V,E)中,两个结点u,vV处于同一强连通分支当且仅当对G进行深度优先搜索时两结点具有同一祖宗。

    证明:

    :假设uv处于同一强连通分支内,从u可达的每个结点也满足从v可达,反之亦然。这是由于在 u v之间存在双向通路,由祖宗的定义我们可以推知Φ(u)=Φ(v)

    :假设Φ(u)=Φ(v)成立,根据推论1uΦ(u)在同一强连通分支内且vΦ(v)也处于同一强连通分支内,因此uv也在同一强连通支中。

    (证毕)

    有了定理4算法Strongly_Connected_Components的结构就容易掌握了。强连通分支就是有着同一组总的节点的集合。再根据定理3括号定理可知,在算法1行所述的深度优先搜索中,祖宗是其所在强连通分支中第一个发现最后一个完成的结点。

    为了弄清楚为什么在算法Strongly_Connected_Components的第3行要对GT进行深度优先搜索,我们考察算法的第1行的深度优先搜索所计算出的具有最大完成时刻的结点r。根据祖宗的定义可知结点r必为一祖宗结点,这是因为它是自身的祖宗:它可以到达自身且图中其他结点的完成时刻均小于它。在r的强连通分支中还有其他哪些节点?它们是那些以F为祖宗的结点——指可达r但不可达任何完成时刻大于f[r]的结点的那些结点。但由于在Gr是完成时刻最大的结点,所以r的强连通分支仅由那些可达r的结点组成。换句话说,r的强连通支由那些在GT中从r可达的顶点组成。在算法第3行的深度优先搜索识别出所有属于r强连通支的结点,并把它们置为黑色(宽度优先搜索或任何对可达结点的搜索可以同样容易地做到这一点)

    在执行完第3行的深度优先搜索并识别出r的强连通分支以后,算法又从不属于r强连通分支且有着最大完成时刻的任何结点r'重新开始搜索。结点,r'必为其自身的祖宗,因为由它不可能达到任何完成时刻大于它的其他结点(否则r'将包含于r的强连通分支中)。根据类似的推理,可达r'且不为黑色的任何结点必属于r'的强连通分支,因而在第3行的深度优先搜索继续进行时,通过在GT中从r'开始搜索可以识别出属于r'的强连通分支的每个结点并将其置为黑色。

    因此通过第3行的深度优先搜索可以对图层层剥皮,逐个取得图的强连通分支。把每个强连通分支的祖宗作为自变量调用DFS_Visit过程,我们就可在过程DFS的第7行识别出每一支。DFS_Visit过程中的递归调用最终使支内每个结点都成为黑色。当DFS_Visit返回到DFS中时,整个支的结点都变成黑色且被剥离,接着DFS在那些非黑色结点中寻找具有最大完成时刻的结点并把该结点作为另一支的祖宗继续上述过程。

    下面的定理形式化了以上的论证。

    定理5

    过程Strongly_Connected_Components(G)可正确计算出有向图G的强连通分支。

    证明:

    通过对在GT上进行深度优先搜索中发现的深度优先树的数目进行归纳,可以证明每棵树中的结点都形成一强连通分支。归纳论证的每一步骤都证明对GT进行深度优先搜索形成的树是一强连通分支,假定所有在先生成的树都是强连通分支。归纳的基础是显而易见的,这是因为产生第一棵树之前无其他树,因而假设自然成立。

    考察对GT进行深度优先搜索所产生的根为r的一棵深度优先树T,设C(r)表示r为祖宗的所有结点的集合:

    C(r)={vV|Φ(v)=r}

    现往我们来证明结点u被放在树T中当且仅当uC(r)

    :由定理2可知C(r)中的每一个结点都终止于同一棵深度优先树。因为rC(r)rT的根,所以C(r)中的每个元素皆终止于T

    :通过对两种情形f[Φ(w)]>f[r]f[Φ(w)]<f[r]分别考虑,我们来证明这样的结点w不在树T中。通过对已发现树的数目进行归纳可知满足f[Φ(w)]>f[r]的任何结点w不在树T中,这是由于在选择到r时,w已经被放在根为Φ(w)的树中。满足f[Φ(w)]<f[r]的任意结点w也不可能在树T中,这是因为若w被放入T中,则有w→r:因此根据(2)和性质r=Φ(r),可得f[Φ(w)]≥f[Φ(r)]=f[r],这和f[Φ(w)]<f[r]相矛盾。

    这样树T仅包含那些满足Φ(u)=r的结点u,即T实际上就是强连通支C(r),这样就完成了归纳证明。

    一、 Kosaraju算法

    1.算法思路

    基本思路:

    这个算法可以说是最容易理解,最通用的算法,其比较关键的部分是同时应用了原图G和反图GT。步骤1:先用对原图G进行深搜形成森林(),步骤2:然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT),能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林,继续步骤2直到没有顶点为止。

    改进思路:

    当然,基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时,可能深搜到其他树上去,这是不允许的,强连通分量只能存在单棵树中(由开篇第一句话可知)),我们当然不这么做,我们可以巧妙的选择第二深搜选择的树的顺序,使其不可能深搜到其他树上去。想象一下,如果步骤2是从森林里选择树,那么哪个树是不连通(对于GT来说)到其他树上的呢?就是最后遍历出来的树,它的根节点在步骤1的遍历中离开时间最晚,而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择,在第一次深搜遍历时,记录时间i离开的顶点j,即numb[i]=j。那么,我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。

    隐藏性质:

    分析到这里,我们已经知道怎么求强连通分量了。但是,大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢?如果在看上述思路的时候,你的脑子在思考,相信你已经知道了!!!它就是:如果我们把求出来的每个强连通分量收缩成一个点,并且用求出每个强连通分量的顺序来标记收缩后的节点,那么这个顺序其实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢?首先,应该明确搜索后的图一定是有向无环图呢?废话,如果还有环,那么环上的顶点对应的所有原来图上的顶点构成一个强连通分量,而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列,我们在改进分析的时候,不是先选的树不会连通到其他树上(对于反图GT来说),也就是后选的树没有连通到先选的树,也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗?这就是Kosaraju算法的一个隐藏性质。

    2.伪代码

    Kosaraju_Algorithm:

    step1:对原图G进行深度优先遍历,记录每个节点的离开时间。

    step2:选择具有最晚离开时间的顶点,对反图GT进行遍历,删除能够遍历到的顶点,这些顶点构成一个强连通分量。

    step3:如果还有顶点没有删除,继续step2,否则算法结束。

    3.实现代码

    #include <iostream>

    using namespace std;

    const int MAXN = 110;

    typedef int AdjTable[MAXN]; //邻接表类型

    int n;

    bool flag[MAXN]; //访问标志数组

    int belg[MAXN]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

    int numb[MAXN]; //结束时间标记,其中numb[i]表示离开时间为i的顶点

    AdjTable adj[MAXN], radj[MAXN]; //邻接表,逆邻接表

    //用于第一次深搜,求得numb[1..n]的值

    void VisitOne(int cur, int &sig)

    {

    flag[cur] = true;

    for ( int i=1; i<=adj[cur][0]; ++i )

    {

    if ( false==flag[adj[cur][i]] )

    {

    VisitOne(adj[cur][i],sig);

    }

    }

    numb[++sig] = cur;

    }

    //用于第二次深搜,求得belg[1..n]的值

    void VisitTwo(int cur, int sig)

    {

    flag[cur] = true;

    belg[cur] = sig;

    for ( int i=1; i<=radj[cur][0]; ++i )

    {

    if ( false==flag[radj[cur][i]] )

    {

    VisitTwo(radj[cur][i],sig);

    }

    }

    }

    //Kosaraju算法,返回为强连通分量个数

    int Kosaraju_StronglyConnectedComponent()

    {

    int i, sig;

    //第一次深搜

    memset(flag+1,0,sizeof(bool)*n);

    for ( sig=0,i=1; i<=n; ++i )

    {

    if ( false==flag[i] )

    {

    VisitOne(i,sig);

    }

    }

    //第二次深搜

    memset(flag+1,0,sizeof(bool)*n);

    for ( sig=0,i=n; i>0; --i )

    {

    if ( false==flag[numb[i]] )

    {

    VisitTwo(numb[i],++sig);

    }

    }

    return sig;

    }

    Pascal

    procedure tarjan(r:longint);

    var x,i,j:longint;

    begin

    inc(timez); time[r]:=timez; low[r]:=timez;

    inc(top); zh[top]:=r;

    for i:=p1[r] to p2[r] do

    begin

    j:=e[i].y;

    if time[j]=0 then tarjan(j);

    if low[j]<low[r] then low[r]:=low[j];

    end;

    if time[r]=low[r] then

    repeat

    x:=zh[top];

    num[x]:=r; low[x]:=n+1; //这句话千万别忘了

    dec(top);

    until x=r;

    end;

    二、 Tarjan算法

    1.算法思路

    这个算法思路不难理解,由开篇第一句话可知,任何一个强连通分量,必定是对原图的深度优先搜索树的子树。那么其实,我们只要确定每个强连通分量的子树的根,然后根据这些根从树的最低层开始,一个一个的拿出强连通分量即可。那么剩下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。

    那么如何确定强连通分量的根,在这里我们维护两个数组,一个是indx[1..n],一个是mlik[1..n],其中indx[i]表示顶点i开始访问时间,mlik[i]为与顶点i邻接的顶点未删除顶点jmlik[j]mlik[i]的最小值(mlik[i]初始化为indx[i])。这样,在一次深搜的回溯过程中,如果发现mlik[i]==indx[i]那么,当前顶点就是一个强连通分量的根,为什么呢?因为如果它不是强连通分量的根,那么它一定是属于另一个强连通分量,而且它的根是当前顶点的祖宗,那么存在包含当前顶点的到其祖宗的回路,可知mlik[i]一定被更改为一个比indx[i]更小的值。

    至于如何拿出强连通分量,这个其实很简单,如果当前节点为一个强连通分量的根,那么它的强连通分量一定是以该根为根节点的(剩下节点)子树。在深度优先遍历的时候维护一个堆栈,每次访问一个新节点,就压入堆栈。现在知道如何拿出了强连通分量了吧?是的,因为当前节点是这个强连通分量中最先被压入堆栈的,那么在当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗?假设一个节点在当前节点压入堆栈以后压入并且还存在,同时它不属于该强连通分量,那么它一定属于另一个强连通分量,但当前节点是它的根的祖宗,那么这个强连通分量应该在此之前已经被拿出。现在没有疑问了吧,那么算法介绍就完了。

    2.伪代码

    Tarjan_Algorithm:

    步骤1:

    找一个没有被访问过的节点vgoto step2(v)。否则,算法结束。

    步骤2(v):

    初始化indx[v]mlik[v]

    对于v所有的邻接顶点u

    1)如果没有访问过,则step2(u),同时维护mlik[v]

    2)如果访问过,但没有删除,维护mlik[v]

    如果indx[v]==mlik[v],那么输出相应的强连通分量

    3.实现代码

    c++代码:

    #include <iostream>

    using namespace std;

    const int MAXN = 110;

    const char NOTVIS = 0x00; //顶点没有访问过的状态

    const char VIS = 0x01; //顶点访问过,但没有删除的状态

    const char OVER = 0x02; //顶点删除的状态

    typedef int AdjTable[MAXN]; //邻接表类型

    int n;

    char flag[MAXN]; //用于标记顶点状态,状态有NOTVIS,VIS,OVER

    int belg[MAXN]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

    int stck[MAXN]; //堆栈,辅助作用

    int mlik[MAXN]; //很关键,与其邻接但未删除顶点地最小访问时间

    int indx[MAXN]; //顶点访问时间

    AdjTable adj[MAXN]; //邻接表

    //深搜过程,该算法的主体都在这里

    void Visit(int cur, int &sig, int &scc_num)

    {

    int i;

    stck[++stck[0]] = cur; flag[cur] = VIS;

    mlik[cur] = indx[cur] = ++sig;

    for ( i=1; i<=adj[cur][0]; ++i )

    {

    if ( NOTVIS==flag[adj[cur][i]] )

    {

    Visit(adj[cur][i],sig,scc_num);

    if ( mlik[cur]>mlik[adj[cur][i]] )

    {

    mlik[cur] = mlik[adj[cur][i]];

    }

    }

    else if ( VIS==flag[adj[cur][i]] )

    {

    if ( mlik[cur]>indx[adj[cur][i]] ) //该部分的indx应该是mlik,但是根据算法的属性,使用indx也可以,且时间更少

    {

    mlik[cur] = indx[adj[cur][i]];

    }

    }

    }

    if ( mlik[cur]==indx[cur] )

    {

    ++ scc_num;

    do

    {

    belg[stck[stck[0]]] = scc_num;

    flag[stck[stck[0]]] = OVER;

    }

    while ( stck[stck[0]--]!=cur );

    }

    }

    //Tarjan算法,求解belg[1..n],且返回强连通分量个数,

    int Tarjan_StronglyConnectedComponent()

    {

    int i, sig, scc_num;

    memset(flag+1,NOTVIS,sizeof(char)*n);

    sig = 0; scc_num = 0; stck[0] = 0;

    for ( i=1; i<=n; ++i )

    {

    if ( NOTVIS==flag[i] )

    {

    Visit(i,sig,scc_num);

    }

    }

    return scc_num;

    }

    PASCAL代码:

    Procedure Tarjan(o:longint);

    var i:longint;

    begin

    inc(h);

    dfn[o]:=h;low[o]:=h;

    inc(t);dl[t]:=o;

    s[o]:=true;ss[o]:=true;

    for i:=1 to n do

    if a[o,i]>0 then

    if not s[i] then

    begin

    Tarjan(i);

    low[o]:=min(low[i],low[o]);

    end else

    if ss[i] then

    low[o]:=min(low[o],dfn[i]);

    if dfn[o]=low[o] then

    begin

    inc(ans);

    while dl[t]<>o do

    begin

    ss[dl[t]]:=false;

    dec(t);

    end;

    end;

    end;

    三、 Gabow算法

    1.思路分析

    这个算法其实就是Tarjan算法的变异体,我们观察一下,只是它用第二个堆栈来辅助求出强连通分量的根,而不是Tarjan算法里面的indx[]mlik[]数组。那么,我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。

    我们使用类比方法,在Tarjan算法中,每次mlik[i]的修改都是由于环的出现(不然,mlik[i]的值不可能变小),每次出现环,在这个环里面只剩下一个mlik[i]没有被改变(深度最低的那个),或者全部被改变,因为那个深度最低的节点在另一个环内。那么Gabow算法中的第二堆栈变化就是删除构成环的节点,只剩深度最低的节点,或者全部删除,这个过程是通过出栈来实现,因为深度最低的那个顶点一定比前面的先访问,那么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问:为什么弹出的都是同一个强连通分量?因为在这个节点访问之前,能够构成强连通分量的那些节点已经被弹出了,这个对Tarjan算法有了解的都应该清楚,那么Tarjan算法中的判断根我们用什么来代替呢?想想,其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。

    现在,你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现,但是,Gabow算法更精妙,时间更少(不用频繁更新mlik[])

    2.伪代码

    Gabow_Algorithm:

    步骤1:

    找一个没有被访问过的节点vgoto step2(v)。否则,算法结束。

    步骤2(v):

    v压入堆栈stk1[]stk2[]

    对于v所有的邻接顶点u

    1)如果没有访问过,则step2(u)

    2)如果访问过,但没有删除,维护stk2[](处理环的过程)

    如果stk2[]的顶元素==v,那么输出相应的强连通分量

    3.实现代码

    #include <iostream>

    using namespace std;

    const int MAXN = 110;

    typedef int AdjTable[MAXN]; //邻接表类型

    int n;

    int intm[MAXN]; //标记进入顶点时间

    int belg[MAXN]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

    int stk1[MAXN]; //辅助堆栈

    int stk2[MAXN]; //辅助堆栈

    AdjTable adj[MAXN]; //邻接表

    //深搜过程,该算法的主体都在这里

    void Visit(int cur, int &sig, int &scc_num)

    {

    int i;

    intm[cur] = ++sig;

    stk1[++stk1[0]] = cur;

    stk2[++stk2[0]] = cur;

    for ( i=1; i<=adj[cur][0]; ++i )

    {

    if ( 0==intm[adj[cur][i]] )

    {

    Visit(adj[cur][i],sig,scc_num);

    }

    else if ( 0==belg[adj[cur][i]] )

    {

    while ( intm[stk2[stk2[0]]]>intm[adj[cur][i]] )

    {

    -- stk2[0];

    }

    }

    }

    if ( stk2[stk2[0]]==cur )

    {

    -- stk2[0]; ++ scc_num;

    do

    {

    belg[stk1[stk1[0]]] = scc_num;

    }

    while ( stk1[stk1[0]--]!=cur );

    }

    }

    //Gabow算法,求解belg[1..n],且返回强连通分量个数,

    int Gabow_StronglyConnectedComponent()

    {

    int i, sig, scc_num;

    memset(belg+1,0,sizeof(int)*n);

    memset(intm+1,0,sizeof(int)*n);

    sig = 0; scc_num = 0; stk1[0] = 0; stk2[0] = 0;

    for ( i=1; i<=n; ++i )

    {

    if ( 0==intm[i] )

    {

    Visit(i,sig,scc_num);

    }

    }

    return scc_num;

    }

    四、总结

    Kosaraju算法

    Kosaraju算法的解释和实现都比较简单,为了找到强连通分支,首先对图G运行DFS,计算出各顶点完成搜索的时间f;然后计算图的逆图GT,对逆图也进行DFS搜索,但是这里搜索时顶点的访问次序不是按照顶点标号的大小,而是按照各顶点f值由大到小的顺序;逆图DFS所得到的森林即对应连通区域。具体流程如图(1~4)

    上面我们提及原图G的逆图GT,其定义为GT=(V, ET)ET={(u, v):(v, u)E}}。也就是说GT是由G中的边反向所组成的,通常也称之为图G的转置。在这里值得一提的是,逆图GT和原图G有着完全相同的连通分支,也就说,如果顶点stG中是互达的,当且仅当stGT中也是互达的。

     

     

     

    根据上面对Kosaraju算法的讨论,其实现如下:

     

        /**
         * 
    算法1Kosaraju,算法步骤:

         * 1. 
    对原始图G进行DFS,获得各节点的遍历次序ord[]
         * 2. 
    创建原始图的反向图GT
         * 3. 
    按照ord[]相反的顺序访问GT中每个节点;
         * 
    @param G    原图
         * 
    @return    函数最终返回一个二维单链表slk,单链表
         * 
    每个节点又是一个单链表, 每个节点处的单链表表示
         * 
    一个联通区域;slk的长度代表了图中联通区域的个数。
         */

        
    public static SingleLink2 Kosaraju(GraphLnk G){
            SingleLink2 slk = 
    new
     SingleLink2();
            
    int ord[] = new int
    [G.get_nv()];
            
    // 对原图进行深度优先搜索

            GraphSearch.DFS(G);
            
    // 拷贝图G的深度优先遍历时每个节点的离开时间

            for(int i = 0; i < GraphSearch.f.length; i++){
                ord[i] = GraphSearch.f[i];
                System.out.print(GraphSearch.parent[i] + " || ");
            }
            System.out.println();
            
    // 构造G的反向图
    GT
            GraphLnk GT = Utilities.reverseGraph(G);
            
    /* 用针对Kosaraju算法而设计DFS算法KosarajuDFS函数

             * 
    该函数按照ord的逆向顺序访问每个节点,
             * 
    并向slk中添加新的链表元素;*/
            GraphSearch.KosarajuDFS(GT, ord, slk);
            
    //打印所有的联通区域
            for(slk.goFirst(); slk.getCurrVal()!= null; slk.next()){
                
    //获取一个链表元素项,即一个联通区域

                GNodeSingleLink comp_i = 
                        (GNodeSingleLink)(slk.getCurrVal().elem);
                
    //打印这个联通区域的每个图节点

                for(comp_i.goFirst(); 
                    comp_i.getCurrVal() != 
    null
    ; comp_i.next()){
                    System.out.print(comp_i.getCurrVal().elem + "\t");
                }
                System.out.println();
            }
            
    //返回联通区域链表

            return slk;
        }

     

    算法首先对原图进行DFS搜索,并记录每个顶点的搜索离开时间ord;然后调用Utilities类中的求逆图函数reverseGraph,求得原图的逆图GT;最后调用GraphSearch类的递归函数KosarajuDFS,该函数按照各顶点的ord时间对图进行深度优先搜索。函数最终返回一个二维单链表slk,单链表每个节点的元素项也是一个单链表,每个节点处的单链表表示一个联通区域,如图,slk的长度代表了图中联通区域的个数。之所以使用这样的数据结构作为函数的结果,其原因是在函数返回之前无法知道图中共有多少个强连通分支,也不知道每个分支的顶点的个数,二维链表自然成为最优的选择。其余两个算法的返回结果也采用这种形式的链表输出结果。

     

     

     

     

     

     Kosaraju算法返回的二维链表形式结果

    reverseGraph函数返回的逆图是新创建的图,其每条边都与原图边的方向相反。原图中一个顶点对应的链表中的相邻顶点是按照标号由小到大的顺序排列的,这样做能提高相关算法的效率(例如isEdge(int, int)函数)。这里在计算逆图时这个条件也必须满足。该静态函数的实现如下:

     

        /**
             * 
    创建一个与入参G每条边方向相反的图,即逆图。

             * 
    @param G    原始图
             * 
    @return 逆图
             */

            
    public static GraphLnk reverseGraph(GraphLnk G){
                GraphLnk GT = 
    new
     GraphLnk(G.get_nv());
                
    for(int
     i = 0; i < G.get_nv(); i++){
                    
    //GT每条边的方向与G的方向相反

                    for(Edge w = G.firstEdge(i); G.isEdge(w); 
                        w = G.nextEdge(w)) {
                         GT.setEdgeWt(w.get_v2(), w.get_v1(),
                                     G.getEdgeWt(w));
                    }
                }
                
    return
     GT;
            }

     

    函数中对顶点按照标号由小到大进行遍历,对顶点i,再遍历其对应链表中的顶点i0, in,并向逆图中添加边(i0, i), , (in, i),最终得到原图的逆图GT。可以发现,函数中调用setEdgeWt函数来向GT中添加边。细心的读者可能还记得,若待修改权值的边不存在时,函数setEdgeWt充当添加边的功能,并且能保证相邻的所有顶点的标号在链表中按由小到大的顺序排列。

    Kosaraju实现中关键的一步是调KosarajuDFS函数对逆图GT进行递归深度优先搜索。函数的另外两个形参为原图DFS所得的各顶点搜索结束时间ord,和保存连通分支结果的链表slkKosarajuDFS的实现如下:

        /**
         * 
    将根据逆图GT和每个节点在原图G深度遍历时的离开时间数组,
         * 
    生成链表slk表示的连通分支
         * 
    本函数不改变图的连接关系,只是节点的访问次序有所调整.
         * 
    @param GT    逆图
         * 
    @param ord    原图DFS各顶点遍历离开时间数组
         * 
    @param slk    连通分支存放在链表中
         */

        
    public static void KosarajuDFS(GraphLnk GT, int ord[], 
                                        SingleLink2 slk){
            
    /* 根据ord数组计算new_order数组,新的访问顺序为:
             * 
    i次访问的节点为原图上的第new_order[i]个节点 */
            
    int new_order[] = new int[ord.length];
            
    //调用函数newordermap改变数组的次序
            newordermap(ord, new_order);
            
    int n = GT.get_nv();
            
    // 这里只需要记录颜色,其它信息不重要了
            color  = new COLOR[n];
            
    // 颜色初始化为白色
            for(int i = 0; i < n; i++) 
                color[i] = COLOR.WHITE;
            
    // 为找到图中所有的联通区域,循环迭代:
            for(int i = 0; i < new_order.length; i++){
                
    // i次访问的节点为原图上的第new_order[i]个节点
                int  j= new_order[i];
                
    if(color[j] != COLOR.WHITE) 
                    
    continue;
                
    // 创建一个图节点链表,表示一个联通区域
                GNodeSingleLink gnsk = new GNodeSingleLink();
                
    //调用递归函数,以j为起点深度搜索该图
                KosarajuDFSVISIT(GT, ord, j, gnsk);
                
    /* 将联通区的节点形成的链表添加到联通区域链表中,
                 * 
    这里使用的实际上是二维链表*/
                slk.append(
    new ElemItem<GNodeSingleLink>(gnsk));
            }
        }

     

    函数首先根据ord数组确定GT中各顶点的访问次序,方法是创建大小与ord相等的数组new_ord,并调用newordermap函数给new_ord各元素赋值。new_ord[i]的意义是:原图上第i个节点在逆图的访问次序为new_ord[i]

    例如顶点在原图中DFS遍历离开时间ord为:

    11

    0)16

    1)10

    2)15

    3)9

    4)14

    5)8

    6)13

    7)7

    8)20

    9)19

    则各顶点在逆图中访问先后次序为:

    8, 9, 0, 2, 4, 6, 1, 3, 5, 7,

    newordermap函数实现如下:

     

     

     

        /**
         * 
    根据原图各顶点DFS得到的遍历结束时间,获取节点新

         * 
    的访问次序.在函数返回时,new_ord[i]的意义是:
         * 
    原图上第i个节点在逆图的访问次序为new_ord[i]
         * 
    其效果是:后访问的节点在新的访问次序中先访问.
         * 
    @param ord        原图各顶点DFS遍历结束时间

         * 
    @param new_ord    节点在逆图的访问次序
         */

        
    public static void newordermap(int[] ord, int[] new_ord){
            
    // 为防止原ord数组被破坏,对其深拷贝

            int ord_temp[] = new int[ord.length];
            
    for(int
     i = 0; i < ord.length; i++) 
                ord_temp[i] = ord[i];
            
    int
     max, max_idx;
            
    // ord_temp中寻找n次最大的值,并将其数组下标放

            // 
    置到new_ord中;然后将最大值赋值为-1
            for(int
     i = 0; i < ord.length; i++){
                max_idx = 0; 
                max = ord_temp[max_idx];
                
    for(int
     j = 0; j < ord.length; j++){
                    
    if
    (ord_temp[j] == -1) 
                        
    continue
    ;
                    
    if
    (ord_temp[j] > max){
                        max = ord_temp[j];
                        max_idx = j;
                    }
                }
                new_ord[i] = max_idx;
                ord_temp[max_idx] = -1;
            }
        }

     

    确定各顶点的访问次序后,按照new_ord中顶点的顺序调用递归函数KosarajuDFSVISIT对逆图进行深度优先搜索。每次调用前都创建一个新的链表作为slk链表的节点,对应一个新的强连通分支。

     

     

        /**
         * 
    递归函数,起点为u深度搜索图G,节点递归地调用该函数时,节点的访问顺序

         * 
    ord决定,对节点u与之相连且标记为白色的的节点v1,v2,...
         * 
    先访问ord[vi]最大的节点vi.当没有与节点u相连的节点或者与u相连的所有

         * 
    节点都不是白色的了,此时获得一个联通区域,函数返回
        */

        
    public static void KosarajuDFSVISIT(GraphLnk G, int ord[], 
                             
    int
     u, GNodeSingleLink slk){
            
    //访问该节点,将其颜色标记为灰色

            color[u] = COLOR.GRAY;
            
    //将该节点u添加到当前的联通区域中

            slk.append(new ElemItem<Integer>(u));
            
    //首先统计与该节点相连的、颜色为白色的节点的个数

            int cnt = 0;
            
    for
    (Edge w = G.firstEdge(u); 
                    G.isEdge(w); w = G.nextEdge(w)){
                
    if
    (color[w.get_v2()] == COLOR.WHITE)
                    cnt++;
            }
            
    //如果此时没有与该节点相连并且颜色为白色的节点,函数返回

            if(cnt == 0) 
                
    return
    ;
            
    //否则,将与该节点相连的、白色节点暂存至数组e

            Edge e[] = new Edge[cnt];
            cnt = 0;
            
    for
    (Edge w = G.firstEdge(u); G.isEdge(w); w = G.nextEdge(w)){
                
    if
    (color[w.get_v2()] == COLOR.WHITE)
                    e[cnt++] = w;
            }
            
    /*对数组e按照边的终点的访问次序ord[..]进行排序

             * 
    这里采用选择排序来完成这一过程 */
            
    int max_idx;
            
    for(int
     i = 0; i < e.length - 1; i++){
                
    //i轮找第i大的元素

                max_idx = i;
                
    for(int
     j = i + 1; j < e.length; j++){
                    
    if
    (ord[e[j].get_v2()] > ord[e[max_idx].get_v2()]){
                        max_idx = j;
                    }
                }
                
    //如果原先第i位置上不是最大的,则交换操作

                if(max_idx != i){
                    Edge t = e[i];
                    e[i] = e[max_idx];
                    e[max_idx] = t;
                }
            }
            
    //对排序后的边逐个进行递归调用

            for(int i = 0; i < e.length; i++)
                KosarajuDFSVISIT(G, ord, e[i].get_v2(), slk);
        }

     

    函数中递归搜索顶点u的相邻顶点时,首相将u的所有尚未访问的相邻顶点()保存至一个边数组e中。然后再对这个数组中的边进行重排序,排序的规则依然是在原图中顶点DFS搜索离开时间。图(a)的运行结果如图所示。

    Tarjan算法

    Kosaraju算法的流程简单,但是需要对图(和逆图)进行两次DFS搜索,而且读逆图的DFS搜索中顶点的访问顺序有特定的限制。下面将介绍的两个算法的过程比Kosaraju算法更为简洁,只需要执行一次DFS,并且不需要计算逆图。

    Tarjan基于递归实现的深度优先搜索,在搜索过程中将顶点不断压入堆栈中,并在回溯时判断堆栈中顶点是否在同一联通分支。函数借助两个辅助数组prelow,其中pre[u]为顶点u搜索的次序编号,low[u]为顶点u能回溯到的最早的顶点的次序编号。当pre[u]=low[u]时,则弹出栈中顶点并构成一个连通分支。以一个简单的例子来解释这一过程,如图所示,

     

     

     

     

    递归

     

    回溯

    0

    2

    1

     

     

     

     

    顶点

    0

    2

    1

    0

    1

    2

    0

    pre

    0

    1

    2

     

    2

    1

    0

    low

    0

    1

    2

     

    0

    0

    0

    寻找图中连通分支的过程

     

    对图中的简单联通图,首先递归地对图进行深度优先搜索,并记录每个顶点的搜索次序pre。搜索起点为0,当对顶点1进行递归时将再次达到顶点0;在回溯过程中依次将顶点1和顶点2low值修改为low[0]。当回溯到顶点0时将栈中low值为low[0]的顶点弹出并组成一个连通分支。

     

    Tarjan算法实现如下:

    /*
     * Trajan 
    算法实现图的强连通区域求解;
     * 
    算法步骤:
     * @param G    
    待求解的图
     * @return 
     * 
    一个二维单链表slk,单链表每个节点也是一个单链表,
     * 
    每个节点处的单链表表示一个联通区域;
     * slk
    的长度代表了图中联通区域的个数。
     */

    public static SingleLink2 Tarjan(GraphLnk G){
        SingleLink2 slk = 
    new SingleLink2();
        
    // 算法需借助于栈结构
        LinkStack ls = new LinkStack();
        
    int pre[] = new int[G.get_nv()];
        
    int low[] = new int[G.get_nv()];
        
    int cnt[] = new int[1];
        
    // 初始化
        for(int i = 0; i < G.get_nv(); i++){
            pre[i] = -1;
            low[i] = -1;
        }
        
    // 对顶点运行递归函数TrajanDFS
        for(int i = 0; i < G.get_nv(); i++){
            
    if(pre[i] == -1) {
                GraphSearch.TarjanDFS(G, 
                            i, pre, low, cnt, 
                            ls, slk);
            }
        }
        
        
    // 打印所有的联通区域
        for(slk.goFirst(); slk.getCurrVal() != null; slk.next()){
            
    // 获取一个链表元素项,即一个联通区域
            GNodeSingleLink comp_i = 
                    (GNodeSingleLink)(slk.getCurrVal().elem);
            
    // 打印这个联通区域的每个图节点
            for(comp_i.goFirst(); 
                comp_i.getCurrVal() != 
    null; comp_i.next()){
                System.out.print(comp_i.getCurrVal().elem + "\t");
            }
            System.out.println();
        }
        
    return slk;
    }

     

    函数首先申明数组变量pre, lowcnt,并对初始化。pre low的意义前面已经解释过,cnt是长度为1的数组。因为在函数TarjanDFScnt的值需要不断变化,如果直接用变量作为形参,函数并不会改变cnt的值,所以需要使用数组。除了数组变量之外,还有一个栈ls,其作用是在对图进行深度优先搜索时记录遍历顶点,并在回溯时弹出部分顶点形成连通分支。

    函数关键的步骤是对图中各顶点调用递归函数TarjanDFS,该函数以深度优先搜索算法为基础,在递归和回溯时不断对pre, low以及栈ls进行操作。实现如下:

     

    /**
     * Tarjan
    算法的递归DFS函数
     */

    public static void TarjanDFS(GraphLnk G, int w, 
                
    int pre[], int low[], int cnt[], 
                LinkStack ls, SingleLink2 slk){
        
    int t , min = low[w] = pre[w] = cnt[0]++;
        
    // 将当前顶点号压栈
        ls.push(new ElemItem<Integer>(w));
        
    // 对当前顶点的每个邻点循环
        for(Edge e = G.firstEdge(w); 
                G.isEdge(e); 
                e = G.nextEdge(e)){
            
    // 如果邻点没有遍历过,则对其递归调用
            if(pre[e.get_v2()] == -1){
                TarjanDFS(G, e.get_v2(), 
                          pre, low, cnt, 
                          ls, slk);
            }
            
    /* 如果邻点已经被遍历过了,比较其编号与min,
             * 
    如果编号较小,则更新min的大小*/
            
    if(low[e.get_v2()] < min) 
                min = low[e.get_v2()];
        }
        
    // 如果此时min小于low[w],则返回
        if(min < low[w]){
            low[w] = min;
            
    return;
        }
        
    // 否则,弹出栈中元素,并将元素添加到链表中
        GNodeSingleLink gnslk = new GNodeSingleLink();
        
    do{
            
    //弹出栈顶元素
            t = ((Integer)(ls.pop().elem)).intValue();
            low[t] = G.get_nv();
            
    //添加到链表中
            gnslk.append(new ElemItem<Integer>(t));
        }
    while(t != w);
        
    // 将该链表添加到slk链表中
        slk.append(new ElemItem<GNodeSingleLink>(gnslk));
    }

     

    下面以图中有向图为例,分析Tarjan算法求解较为复杂的有向图的过程。各顶点的搜索访问次序以及low值的变化如图。

    顶点

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    次序

    0

    2

    1

    3

    6

    4

    7

    5

    8

    9

    low

    0

    2/0

    1/0

    3

    6

    4/3

    7/6

    5

    8

    9/8

    min

    0

    2/0

    1/0

    3

    6

    4/3

    7/6

    5

    8

    9/8

     

          深度优先搜索各顶点的访问次序以及堆栈中顶点的变化过程如图。其中框出来的步骤表示遍历到达已访问过的顶点,此时需要对low做修改,堆栈中黑体加粗的顶点表示弹出的顶点。

     

     

     

     

     

     Tarjan算法详细过程图

    算法详细过程分析如下:

    搜索起点为顶点0,递归搜索顶点2、顶点1,这三个顶点被压入栈中。在顶点1处首先递归搜索顶点0,由于顶点0已经访问过,所以不再递归搜索顶点0,而是作如下处理:

    如果low[0] < 顶点1min(记为min1),则min1 ← low[0]

    此时(0=low[0])<(min1=1),所以min1←0

    接着到达顶点3,顶点3尚未被访问,则递归搜索顶点3,并继续搜索顶点5。此时,顶点5第一个相邻点为顶点3,则不再递归搜索顶点3,更新min5值,min5←3

    接着递归搜索顶点7,顶点7只有一个相邻顶点,即为顶点自身,则顶点7的递归结束。回溯到顶点7,此时min7=low[7]=5,弹出栈中顶点7,并作为第一个联通分支。

    函数继续回溯到顶点5,此时顶点5的相邻顶点的递归搜索已经全部结束,由于(3=min5)<(low[5]=5),则low[5]←(min5=3),并返回;函数回溯到顶点3,此时与顶点3相邻的顶点的递归搜索也已全部完成,由于min3=low[3]=3,所以弹出栈中顶点5和顶点3,作为第二个连通分支。

    函数回溯至顶点1,此时与顶点1相邻的顶点的递归调用已结束,此时(0=min1)<(low[1]=2),则low[1]←(min1=0),并返回;函数回溯顶点2,更新min2←(low[1]=0);此时顶点2还有两个相邻顶点,即顶点3和顶点4,顶点3已经判定属于第二个连通分支,所以对顶点4递归搜索。

    首先将顶点4压入栈中,对相邻顶点5递归搜索,顶点5已经判定属于第二个连通分支,所以转而对顶点6递归搜索。顶点6的第一个相邻顶点为4,则不再递归搜索顶点4,更新顶点6min6←(low[4]=6)。顶点6的第二个相邻顶点为7,但顶点7已经判定属于第一个连通分支。此时顶点6的所有相邻顶点递归搜索结束,此时(6=min6)<(low[6]=7),则low[6]←(min6=6),并返回;函数回溯到顶点4,与顶点4相邻的顶点的递归搜索也已全部完成,由于min4=low[4]=6,所以弹出栈中顶点6和顶点4,作为第三个连通分支。

    函数回溯至顶点2,此时顶点2的所有相邻顶点递归搜索结束,此时(0=min2)<(low[2]=1),则low[2]←(min2=0),并返回;

    函数回溯至顶点0,此时顶点0的所有相邻顶点递归搜索结束,并且顶点min0=low[0],则将栈中顶点1,2,0依次弹出,作为第四个连通分支。

    最后函数继续递归搜索顶点8和顶点9()

    从算法的流程可以清楚的发现Tarjan算法可以在线性时间内找出一个有向图的强分量,并且对原图进行一次DFS即可。

    Gabow算法

    Gabow算法是Tarjan算法的提升版本,该算法类似于Tarjan算法。算法维护了一个顶点栈,但是还是用了第二个栈来确定何时从第一个栈中弹出各个强分支中的顶点,它的功能类似于Tarjan算法中的数组low。从起始顶点w处开始进行DFS过程中,当一条回路显示这组顶点都属于同一个强连通分支时,就会弹出栈二中顶点,只留下回边的目的顶点,也即搜索的起点w

    当回溯到递归起始顶点w时,如果此时该顶点在栈二顶部,则说明该顶点是一个强联通分量的起始顶点,那么在该顶点之后搜索的顶点都属于同一个强连通分支。于是,从第一个栈中弹出这些点,形成一个强连通分支。

    根据上面对算法的描述,实现如下:

     

     

        /* Gabow 算法实现图的强连通区域查找;
         * @param G    
    输入为图结构
         * @return:
         * 
    函数最终返回一个二维单链表slk,单链表每个节点又是一个单链表,
         * 
    每个节点处的单链表表示一个联通区域;
         * slk
    的长度代表了图中联通区域的个数。
         */

        
    public static SingleLink2 Gabow(GraphLnk G){
            SingleLink2 slk = 
    new SingleLink2();
            
    // 函数使用两个堆栈
            LinkStack ls = new LinkStack();
            LinkStack P = 
    new LinkStack();
            
    int pre[] = new int[G.get_nv()];
            
    int cnt[] = new int[1];
            
    // 标注各个顶点所在的连通分支的名称
            int id[]  = new int[G.get_nv()];
            
    // 初始化
            for(int i = 0; i < G.get_nv(); i++){
                pre[i] = -1;
                id[i] = -1;
            }
            
    for(int i = 0; i < G.get_nv(); i++){
                
    if(pre[i] == -1) {
                    GraphSearch.GabowDFS(G, 
                            i, pre, id, cnt, 
                            ls, P, slk);
                }
            }
            
            
    //打印所有的联通区域
            for(slk.goFirst(); slk.getCurrVal() != null; slk.next()){
                
    //获取一个链表元素项,即一个联通区域
                GNodeSingleLink comp_i = 
                        (GNodeSingleLink)(slk.getCurrVal().elem);
                
    //打印这个联通区域的每个图节点
                for(comp_i.goFirst(); 
                    comp_i.getCurrVal() != 
    null; comp_i.next()){
                    System.out.print(comp_i.getCurrVal().elem + "\t");
                }
                System.out.println();
            }
            
    return slk;
        }
        
        
    函数调用递归实现的深度优先搜索GabowDFS,实现如下:
        
        
    /**
         * GabowDFS
    算法的递归DFS函数
         * 
    @param ls    1,
         * 
    @param P    2,决定何时弹出栈1中顶点
         */

        
    public static void GabowDFS(GraphLnk G, int w, 
                    
    int pre[],  int[] id, int cnt[], 
                    LinkStack ls, LinkStack P, 
                    SingleLink2 slk){
            
    int v;
            pre[w] = cnt[0]++;
            
    //将当前顶点号压栈
            ls.push(new ElemItem<Integer>(w));
            System.out.print("+0 stack1 ");ls.printStack();
            P.push(
    new ElemItem<Integer>(w));
            System.out.print("+0 stack2 ");P.printStack();
            
            
    // 对当前顶点的每个邻点循环
            for(Edge e = G.firstEdge(w); G.isEdge(e); e = G.nextEdge(e)){
                
    //如果邻点没有遍历过,则对其递归调用
                if(pre[e.get_v2()] == -1){
                    GabowDFS(G, e.get_v2(), pre, id, cnt, ls, P, slk);
                }
                
    // 否则,如果邻点被遍历过但又没有被之前的连通域包含,则循环弹出
                else if(id[e.get_v2()] == -1){
                    
    int ptop = ((Integer)(P.getTop().elem)).intValue();
                    
    // 循环弹出,直到栈顶顶点的序号不小于邻点的序号
                    while(pre[ptop] > pre[e.get_v2()]) {
                        P.pop();
                        System.out.print("-1 stack2 ");P.printStack();
                        ptop = ((Integer)(P.getTop().elem)).intValue();
                    }
                }
            }
            
    // 遍历完顶点的所有相邻顶点后,如果栈2顶部顶点与w相同则弹出;
            if(P.getTop() != null 
               && ((Integer)(P.getTop().elem)).intValue() == w){
                P.pop();
                System.out.print("-2 stack2 ");P.printStack();
            }
            
    // 否则函数返回
            else return;
            
            
    // 如果栈2顶部顶点与w相同,则弹出栈1中顶点,形成连通分支
            GNodeSingleLink gnslk = new GNodeSingleLink();
            
    do{
                v = ((Integer)(ls.pop().elem)).intValue();
                id[v] = 1;
                gnslk.append(
    new ElemItem<Integer>(v));
            }
    while(v != w);
            System.out.print("-3 stack1 ");ls.printStack();
            slk.append(
    new ElemItem<GNodeSingleLink>(gnslk));
            
        }

    转载于:https://www.cnblogs.com/MisdomTianYa/p/6581855.html

    展开全文
  • 题目很简单就拿着这道题简单说说有向图连通分支的Tarjan算法 有向图连通分支的Tarjan算法伪代码如下:void Tarjan(u) {dfn[u]=low[u]=++index//进行DFS,每发现一个新点就对这个点打上时间戳,所以先找到点...

    题目很简单就拿着这道题简单说说 有向图强连通分支的Tarjan算法

    有向图强连通分支的Tarjan算法伪代码如下:
    void Tarjan(u) {
    dfn[u]=low[u]=++index//进行DFS,每发现一个新的点就对这个点打上时间戳,所以先找到的点时间戳越早,dfn[U]表示最早发现u的时间,low[u]表示u能到达的最早的时间戳。
    stack.push(u)//将U压入栈中
    for each (u, v) in E {
    if (v is not visted)//如果V点没有经历过DFS,则对V点进行搜索

    {
    tarjan(v)
    low[u] = min(low[u], low[v]) //因为U和V连接,所以V能到达的最早的时间戳,U一定可以到达,比较后取小值。
    }
    else if (v in stack)//如果V点已经在栈中了,那么比较dfn[V]和low[u]后取小值

    {
    low[u] = min(low[u], dfn[v])
    }
    }
    if (dfn[u] == low[u]) { //u是一个强连通分量的根
    repeat
    v = stack.pop
    print v
    until (u== v)
    } //退栈,把整个强连通分量都弹出来
    } //复杂度是O(E+V)的

     

    下面贴出HDU1269的代码,这是道很基础的模板题。

    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<queue>
    #define INF 0xfffffff
    #define MAX 101000
    
    using namespace std;
    
    int n,m,k,Time,vis[MAX],low[MAX],dfn[MAX],black,e,Stack[MAX];
    
    vector<vector<int> >G;
    
    void Tarjan(int u)
    {
        vis[u]=1;
        Stack[++k]=u;
        low[u]=dfn[u]=Time++;
    
        int v,len=G[u].size(),i;
    
        for(i=0;i<len;i++)
        {
            v=G[u][i];
    
            if(!dfn[v])
            {
                Tarjan(v);
                low[u]=min(low[u],low[v]);
            }
    
            else if(vis[v])
            {
                low[u]=min(low[u],dfn[v]);
            }
        }
    
        if(dfn[u]==low[u])
        {
            do
            {
                v=Stack[k--];
                e++;
                vis[v]=0;
            }while(u!=v);
            black++;
        }
    }
    
    int main()
    {
        int i,j,a,b;
    
        while(scanf("%d%d",&n,&m),n+m)
        {
            Time=1;
            k=e=black=0;
            memset(vis,0,sizeof(vis));
            memset(low,0,sizeof(low));
            memset(dfn,0,sizeof(dfn));
            memset(Stack,0,sizeof(Stack));
    
            G.clear();
            G.resize(n+1);
    
            for(i=1;i<=m;i++)
            {
                scanf("%d%d",&a,&b);
                G[a].push_back(b);
            }
    
            Tarjan(1);
    
            if(e==n && black==1)
                printf("Yes\n");
            else
                printf("No\n");
        }
        return 0;
    }
    View Code

     

    转载于:https://www.cnblogs.com/alan-W/p/5672040.html

    展开全文
  • 1. 对矩阵表示的有向图,求出其所有的强连通分支,并指出最大强连通分支。最大连通分支定义为包含结点数最多的连通分支
  • 做一遍DFS,用dfn[i]表示编号为i节点在DFS过程中 访问序号(也可以叫做开始时间)。在DFS过程中会形成 一搜索树。在搜索树上越先遍历到节点,显然dfn值就 越小。dfn值越小节点,就称为越“早” 。 ◦ 用low...

    做一遍DFS,用dfn[i]表示编号为i的节点在DFS过程中 的访问序号(也可以叫做开始时间)。在DFS过程中会形成 一搜索树。在搜索树上越先遍历到的节点,显然dfn的值就 越小。dfn值越小的节点,就称为越“早” 。 ◦ 用low[i]表示从i节点出发DFS过程中i下方节点(开始时 间大于dfn[i],且由i可达的节点)所能到达的最早的节点的 开始时间。初始时low[i]=dfn[i]
    ◦ DFS过程中,碰到哪个节点,就将哪个节点入栈。栈中节 点只有在其所属的强连通分量已经全部求出时,才会出栈。
    ◦ 如果发现某节点u有边连到栈里的节点v,则更新u的low 值 为min(low[u],dfn[v]) ,若low[u]被更新为dfn[v],则表明目前 发现u可达的最早的节点是v.

    有向图强连通分支的Tarjan算法

    ◦对于u的子节点v,从v出发进行的DFS结束回到u 时,使得 low[u] = min(low[u],low[v])。因为u可达v, 所以v可达的最早的节点,也是u可达的。
    ◦ 如果一个节点u,从其出发进行的DFS已经全部完 成并回到u,而且此时其low值等于dfn值,则说明 u可达的所有节点,都不能到达任何比u早的节点 — 那么该节点u就是一个强连通分量在DFS搜索树 中的根。
    ◦ 此时,显然栈中u上方的节点,都是不能到达比u 早的节点的。将栈中节点弹出,一直弹到u(包括u), 弹出的节点就构成了一个强连通分量.

    伪码:

    void Tarjan(u)
    {
        dfn[u]=low[u]=++index
        stack.push(u);
        for each(u,v) in E
        {
            if (v is not visited)
            {
                tarjan(v)
                low[u]=min(low[u],low[v])
            }
            else if (v in stack)
            {
                low[u]=min(low[u],dfn[v])
            }
        }
        if (dfn[u]==low[u])
        {
            //u是一个强连通分量的根
            repeat
               v=stack.pop
               print v
            until (u==v)
        } //退栈 把整个强连通分量都push出来
    } //O(E+V)

    附kuangbin模板源码:

    #include"kuangbin.h"
    #include<iostream>
    using namespace std;
    //复杂度O(N+M)的Tarjan算法
    const int MAXN=20010; //点数
    const int MAXM=50010; //边数
    struct Edge
    {
        int to,next;
    }edge[MAXM];
    int head[MAXN],tot;
    int low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN]; //Belong数组的值是1~scc(强连通分量的个数)
    int Index,top;
    int scc; //强连通分量的个数
    bool Instack[MAXN];
    int num[MAXN]; //各个强连通分量包含点的个数 数组编号即为1~scc
    //这个num数组不一定需要
    void addedge(int u,int v)
    {
       edge[tot].to = v;
       edge[tot].next = head[u];
       head[u] = tot++;
    }
    void Tarjan(int u)
    {
        int v;
        low[u]=DFN[u]=++Index;
        Stack[top++]=u; //入栈
        Instack[u]=true;
        for (int i=head[u];i!=-1;i=edge[i].next)
        {
            v=edge[i].to;
            if (!DFN[v])
            {
                Tarjan(v);
                if (low[u]>low[v])
                    low[u]=low[v];
            }
            else if (Instack[v]&&low[u]>DFN[v])
                low[u]=DFN[v];
        }
        if (low[u]==DFN[u])
        {
            scc++;
            do
            {
                v=Stack[--top];
                Instack[v]=false;
                Belong[v]=scc;
                num[scc]++;
            }while (v!=u);
    
        }
    }
    void solve(int N)
    {
        memset(DFN,0,sizeof(DFN));
        memset(Instack,0,sizeof(Instack));
        memset(num,0,sizeof(num));
        Index=scc=top=0;
        for (int i=1;i<=N;i++)
        {
            if (!DFN[i])
                Tarjan(i);
        }
    }
    void init()
    {
        tot=0;
        memset(head,-1,sizeof(head));
    }
    int main()
    {
        …………
    }
    
    展开全文
  • 有向图的连通分支及DAG

    千次阅读 2014-08-06 09:00:50
    有向图的连通分支:在有向图G中
  • 求无向图的连通分支

    千次阅读 2018-12-09 23:29:56
    从键盘接收图的顶点集,关系集,创建无向图。 第一行依次输入图的顶点个数n,关系个数k,以空格隔开。顶点个数&lt;=20 第二行依次输入顶点值,类型为字符。 接下去k行,每行为两个字符 u 和 v,表示节点u 和 v...
  • 该说都在代码里了,老师给模板不符合本菜鸡要求啊只能手动扩充了,用是邻接矩阵存储,可以换成邻接表啥可能快点 #include <iostream> #include<stack> #include<string.h> using ...
  • 最近一直在研究图论的一些算法,前几天主要做了 割点,桥,有向图的连通分支,无向图的重连通分支,重连通图的构造等等。这些算法都有一个相同的特点,就是都运用基于强大的DFS的Tarjan算法来实现的。核心就是围绕...
  • 有向图G连通分支可以通过下面步骤进行: (1)对G执行深度优先搜索,求出每个顶点后序遍历顺序号postOrder。 (2)反转有向图G中边,构造一个新的有向图G*。 (3)由最高postOrder编号开始,对G*执行深度...
  • ACM图论__有向图的连通分支算法

    千次阅读 2018-02-21 19:25:41
    有向图的连通分支,主要有两种算法tarjan算法和kosaraju算法,这里介绍tarjan算法先来看几个定义:(1)连通:两个点可以相互到达(2)强连通(strongly connected): 在一个有向图G里,设两个点 a b 发现,由a有...
  • HDU1269 迷宫城堡  http://acm.hdu.edu.cn/showproblem.php?pid=1269     题意 为了训练小希方向感,Gardon建立了一座大城堡,里面N个房间(N&lt;=10000)和M条通...
  • 非强连通有向图的极大强连通子图,称为强连通分量(strongly connected components)。Tarjan算法Tarjan算法是用来求有向图的连通分量的。求有向图的连通分量的Tarjan算法是以其发明者Robert Tarjan命
  • Kosaraju算法查找有向图的连通分支

    千次阅读 2016-01-11 14:29:11
    给定一个有向图 G = (V, E),对于任意一对顶点 u 和 v,有 u --> v 和 v --> u,亦即,顶点 u 和 v 是互相可达,则说明该图 G 是强连通的(Strongly Connected)。如下图中,任意两个顶点都是互相可达。 对于...
  • 用两种算法实现求有向图的连通分支,其中一种是分两次进行深度优先搜索,另一种是用堆栈来代替第二次深度优先搜索
  • 在有向图G中,如果两个顶点vi,vj间有一条从vi到vj的...有向图的极大强连通子图(即:一个图的(强)连通子图,并且加入任何一个不在它的点集中的点都会导致它不再(强)连通。),称为强连通分量(strongly connected c
  • 有向图的连通分支: 算法思想: 1对图G进行深度优先搜索,求出每个顶点的后续遍历序号postn 2反转图G中的边,构造一个新的有向图G* 3第2步中产生的森林中的每一颗数,对应一个强连通分支 真正算法实现: 1对逆图G...
  • 图论,求有向图的连通分支

    千次阅读 2010-08-05 21:47:00
    有向图的强联通分支十一个典型的图论题目。 本来想把他写成一个通用的算法,但是发现有很多不太好处理的地方,比如选用邻接链表还是选用邻接矩阵来表示图,有的情况是不一样的,再者很难把强联通分支缩...
  • 基本介绍网上看了很多关于求解一个有向图的连通分支个数的算法,其中最著名的莫过于: Kosaraju 算法看的比较晕!过程如下: 1。 创建一个空的栈 S,并做一次 DFS 遍历。在 DFS 遍历中,当在递归调用 DSF 访问...
  • 最大连通分支定义为包含结点数最多的连通分支。 二、题目分析与设计 1. 题目的需求。 设计出一个基于界面的求强连通分支的软件,能根据相应的按键构建邻接矩阵,并绘画出相应的有向图,同时快速计算出其所有的...
  • // 强连通分支(邻接表存储).cpp : Defines the entry point for the console application. //通过二次利用深度优先搜索访问节点,每次深度优先搜索操作不同 #include "stdafx.h" #include #define MAX 100 ...
  • 本题求的是无向图的连通分支数,用Python代码实现如下: """ 无向或有向图的连通分治数可以用并查集求出来。 并查集的本质是将图分成多棵树,每棵树是每个连通分支的树形表示,因此树的总数等于连通分支的总数 并查...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 336
精华内容 134
关键字:

有向图的连通分支