有向图的强连通分支以及最小点基

时间：2010-10-25 来源：kaiserhui

最近一直在研究图论的一些算法，前几天主要做了割点，桥，有向图的强连通分支，无向图的重连通分支，重连通图的构造等等。这些算法都有一个相同的特点，就是都运用基于强大的DFS的Tarjan算法来实现的。核心就是围绕计算以及比较dfn和low两个向量，各自只有些细微的差别而已。
    今天下午在做有向图的最小点基的时候才发现自己之前的有向图的强连通分支的算法有问题，Debug之后才发现了问题的所在。
    首先是无向图的割点问题（在前一篇文章已经讨论过）：

while(p){
        if(!visited[p->adjvex]){
            if(i == ROOT){
                if(++rootson > 1)
                    ArtPoint[i] = true;
            }
            Tarjan_cut_bridge(visited, p->adjvex, i);
            low[i] = Min(low[i], low[p->adjvex]);
            if(i!=ROOT&&low[p->adjvex]>=dfn[i])
                ArtPoint[i] = true;
            if(low[p->adjvex]>dfn[i])
                Bridge[i] = p->adjvex;
        }else if(p->adjvex!=father){
            low[i] = Min(low[i], dfn[p->adjvex]);
        }
        p = p->next;
    }

    之后是有向图的强连通分支的问题，其核心思想是：基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个栈，当遇到dfn[i]=low[i]的时候，释放栈顶元素，直到将i释放出为止。
    伪代码表示为：

tarjan(u)
{
    DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值
    Stack.push(u) // 将节点u压入栈中
    for each (u, v) in E // 枚举每一条边
        if (v is not visted) // 如果节点v未被访问过
            tarjan(v) // 继续向下找
            Low[u] = min(Low[u], Low[v])
        else if (v in S) // 如果节点v还在栈内
            Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根
        repeat
            v = S.pop // 将v退栈，为该强连通分量中一个顶点
            print v
        until (u== v)
}

    可见二者有细微的差别（注意红色加粗部分），求割点时，当下一个点是已访问点时，low的赋值条件是:下一个点不是当前点的father，即代码中p->adjvex!=father；而在求强连通分支中条件变为下一个点是否在栈中，即代码中v in S。二者的差别可就大了，我在当初写强连通分支的代码时判断的条件依然用是否为父亲节点判断，所以当然就错了！反思，反思！
   究其原因，无向图可以遍历回父亲，但这是由于边的无向性造成；而有向图遍历回父节点是由于真实存在通往父节点的回路，所以当然不同。即，二者的不同是由于无向图与有向图之间的差别引起的，不是由于二者所求的问题引起的。

============================================================================

    之后再说说最小点基的问题，貌似网上这方面的资料不是很多，以至于我连最小点基的英文表示都没找到，只能用minist point base代替了，纯chiglish了。
    首先，最小点基与强连通分支是有很大联系的。吴文虎先生的图论书上有介绍的，摘抄过来。
    在说点基之前再提一个定义：设[Si]是有向图G的一个强连通分支，如果在G中，不存在终点属于[Si]而起点不属于[Si]的弧，就称[Si]为最高强连通分支。说白了，最高强连通分支就是入度为0的强连通分支。
    设G=(V,E)是一个有向图，B是若干个顶点组成的V的子集。如果对于任意的Vj属于V，都存在一个Vi属于B，使得Vi是Vj的前代，则称B是一个点基。包含元素个数最小的B称为最小点基。
    综上，求最小点基的步骤：
    1，找出图G=(V,E)的所有强连通分支；
    2，从强连通分支中找出所有最高强连通分支；
    3，在每个最高强连通分支中任取一点，组成的集合即为最小点基。
    以下是我自己写的一部分代码，应用了并查集来最为强连通分支的标识。

///求图的最小点基
///步骤： 1，求图的强连通分量，2，求图的最高强连通分量，
/// 3，从每一个最高强连通分支中取一个顶点，组成的顶点集B就是一个G的最小点基
void AdjList::MPB_dfs(int set[], int i)
{
    ArcNode *p = V[i].firstarc;
    static int predfn = 1;
    dfn[i] = low[i] = predfn++;
    static stack<int> s;
    static bool instack[ROOT+MAX_VEXTEX_NUM] = {false};

    s.push(i);
    instack[i] = true;
    ///求强连通分量

    while(p)
    {
        if(!dfn[p->adjvex])
        {
            MPB_dfs(set, p->adjvex);
            low[i] = Min(low[i], low[p->adjvex]);
        }
        else if(instack[p->adjvex])///无p->adjvex!=fa

        {
            low[i] = Min(low[i], dfn[p->adjvex]);
        }
        p = p->next;
    }
    if(low[i]==dfn[i])
    {
        while(s.top()!=i)
        {
            merge(s.top(), i, set);
            instack[s.top()]=false;
            //cout<<s.top()<<" ";

            s.pop();
        }
        //cout<<s.top();

        //cout<<endl;

        instack[s.top()]=false;
        s.pop();
    }
}
bool AdjList::MPB()
{
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    int set[ROOT+vexnum], indegree[ROOT+vexnum];
    int i, s1, s2;
    int mpb_cnt=0;
    ArcNode *p;

    for(i=ROOT; i<vexnum+ROOT; i++)
        set[i]=i;
    memset(indegree, -1, sizeof(indegree));
    for(i=ROOT; i<vexnum+ROOT; i++)
    {
        if(!dfn[i])
          MPB_dfs(set, i);
    }

    for(i=ROOT; i<vexnum+ROOT; i++)
    {
        s1=find(i ,set);
        if(indegree[s1]==-1)
            indegree[s1]=0;
        for(p=V[i].firstarc; p; p=p->next)
        {
            s2=find(p->adjvex, set);
            if(s1!=s2)
            {
                if(indegree[s2]==-1)
                    indegree[s2]=1;
                else
                    indegree[s2]++;
            }
        }
    }
    cout<<"[+]MPB:";
    for(i=ROOT; i<vexnum+ROOT; i++)
        if(indegree[i]==0)
        {
            mpb_cnt++;
            cout<<i<<" ";
        }
    cout<<"\tTotally:"<<mpb_cnt<<endl;

    return true;
}

参考文章：
PKU 1236 Network of Schools - 最小点基
http://blog.csdn.net/tiaotiaoyly/archive/2008/11/12/3281677.aspx
有向图强连通分量的Tarjan算法
http://www.byvoid.com/blog/scc-tarjan/
《图论》吴文虎