O(1) 的小乐

Job Hunting

公告

记录我的生活和工作。。。
<2010年9月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

统计

  • 随笔 - 182
  • 文章 - 1
  • 评论 - 41
  • 引用 - 0

留言簿(10)

随笔分类(70)

随笔档案(182)

文章档案(1)

如影随形

搜索

  •  

最新随笔

最新评论

阅读排行榜

评论排行榜

双连通图 割点与桥 算法代码篇

   割点与桥的求解都有一个前提:所求的图是连通图,不连通的图没有割点

 

    给每个顶点定义一个Low值, Low(u)表示从u出发, 经过一条其后代组成的路径和后向边, 所能到达的最小深度的顶点的编号(如果这个编号大于等于u的编号, 就说明它的后代无法到达比u深度更浅的顶点, 即无法到达u的祖先, 那么u就是个关节点, 具体做法是在DFS每次回溯后拿刚才扩展节点的Low与当前节点的DFN比较, 若low>=dfn则当前节点是割点).

Low(u)=min{DFN(u), min{Low(w)|w是u的儿子}, min{DFN(w)|(u,w) 是一条后向边}}  DFN(u)是深搜过程中对顶点的编号值.

   在求割点的同时就可以通过一个全局的栈求出点的双连通分量, 具体做法是在DFS每次由当前顶点u深入下一顶点v时, 就将边uv进栈, 若在函数返回后判断出v是割点, 则出栈, 直到uv出栈,刚才出栈的这些边就属于同一个点双连通分量.

 

在求割点的同时就可以通过一个全局的栈求出点的双连通分量, 具体做法是在DFS每次由当前顶点u深入下一顶点v时, 就将边uv进栈, 若在函数返回后判断出v是割点, 则出栈, 直到uv出栈,刚才出栈的这些边就属于同一个点双连通分量.

 

来看一下几个定义吧:

对dfs的搜索树的定义,这是必须首先明确的,搜索树是这样一棵树,他的顶点是图中的顶点,他的边(A,B)可以说是从图中的对应点A到对应点B的访问,也可以说,树的边(A,B)对应了图中的边(A,B),并且说明了B是从A经过这条边到达的
之后定义搜索顺序的方式:
像(A)这样,从U扩展W,W为一个未扩展到的顶点,那么边(U,V)叫树枝弧
像(B)这样从U扩展一条路,扩展到了V,后来返回到了U,结果有一条(U,V),这时候V已经扩展,边(U,V)叫作前向弧
像 (C)这样,从U扩展到了V,然后再扩展V的,扩展V的时候发现有一条边(V,U),那么边(V,U),也就是说有一条指向祖先的边,叫作反向弧
   (D)指向非祖先的访问过的点,叫作横向弧
在无向图中,没有可能dfs出前向弧或者横向弧,只有a、c

 

树T的根是图G的割点,当且仅当其在T中至少有两个儿子(程序中,我们使用的是son来记录)

代码:(Sosi coded)这个代码求出了图的割点 桥与二连通分量图

#include "cstdlib"
#include "cctype"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "algorithm"
#include "vector"
#include "string"
#include "iostream"
#include "sstream"
#include "set"
#include "queue"
#include "stack"
#include "fstream"
#include "strstream"
using namespace std;
/*
此问题是获得图的割,桥,与点连通分量图
*/

#define  M 5000           //题目中可能的最大点数      
int DFN[M];                  //深度优先搜索访问次序
int Low[M];                  //能追溯到的最早的次序

vector <int> Edge[M];        //邻接表表示

int Belong[M];
int Index=0;               
int CutVertexNum=0,CutVertexList[M];         //保存个点数目与割点         1-indexed
int BridgeNum=0,Bridgeu[M],Bridgev[M];       //保存割边数量与割边起始点   1-indexed
int BlockNum=0;vector <int> Block[M];        //保存块数目和块
int len,que[M];
int color=0;                                 //color 用来记录连通分量个数

void DFS(int u,int parent)
{
    int v,son=0, beVertexCut=0;             //son记录的是点u的儿子数目
    Belong[u]=-color; que[++len]=u;
    DFN[u]=Low[u]=Index++;
    for (int e=0;e<Edge[u].size();e++)
    {
        v=Edge[u][e];
        if(v!=parent)
        {
            if(Belong[v]==0)                     //树枝边
            {
                DFS(v,u);son++;
                Low[u]=min(Low[v],Low[u]);
                if(Low[v]>=DFN[u])
                {
                    beVertexCut=1;           //求割点
                    BlockNum++;
                    while(que[len]!=v){ Block[BlockNum].push_back(que[len]);cout<<que[len--]<<" ";}
                    Block[BlockNum].push_back(que[len]);Block[BlockNum].push_back(u);
                    cout<<que[len--]<<" "<<u<<endl;

                }
                if(Low[v]==DFN[v]) Bridgeu[++BridgeNum]=u,Bridgev[BridgeNum]=v;       //求割边
            }
            else Low[u]=min(Low[u],DFN[v]);      //后向边
        }
    }
    //非根节点且是割点 或者  根节点且儿子至少有两个
    if((parent&& beVertexCut)||(!parent&&son>1)) CutVertexList[++CutVertexNum]=u;
    Belong[u]=color;
}
void dfs(int N)
{
    memset(DFN,-1,sizeof(DFN));
    memset(Low,-1,sizeof(Low));
    memset(CutVertexList,-1,sizeof(CutVertexList));
    memset(Bridgeu,-1,sizeof(Bridgeu));
    memset(Bridgev,-1,sizeof(Bridgev));
    memset(Belong,0,sizeof(Belong));     //所有的块号都大于等于1
    for(int i=0;i<N;i++)
    {
        if(!Belong[i])
        {
            ++color,len=0,DFSCUT(i,0);
            if(len>1||DFN[i]==Index)
            {
                BlockNum++;
                while(len>1){ Block[BlockNum].push_back(que[len]);cout<<que[len--]<<" ";}
                Block[BlockNum].push_back(i);
                cout<<i<<endl;
            }
        }
    }

}

void reshape(int N)     //缩点形成新图,N为图中的点数
{
    if(color==1)
    {
    cout<<"CutVertexNum    "<<CutVertexNum<<endl;
    for(int i=1;i<=CutVertexNum;i++)
    {
        cout<<CutVertexList[i]<<" ";
    }
    cout<<endl;

    cout<<"BridgeNum    "<<BridgeNum<<endl;
    for(int i=1;i<=BridgeNum;i++)
    {
        cout<<Bridgeu[i]<<"   to     "<<Bridgev[i]<<endl;
    }
    cout<<endl;
    cout<<"Color"<<color<<endl;
    for(int i=0;i<N;i++)
        cout<<Belong[i]<<"    ";
    cout<<endl;

    cout<<"Block"<<BlockNum<<endl;
    for(int i=1;i<=BlockNum;i++)
    {
        for(int j=0;j<Block[i].size();j++)
        {
            cout<<Block[i][j]<<" ";
        }
        cout<<endl;
    }
    }
    else
        cout<<"It`s not a connected graph"<<endl;
}
/*
此算法正常工作的基础是图是0-indexed的。
*/
int main()
{
    Edge[0].push_back(1),Edge[0].push_back(2);
    Edge[1].push_back(0),Edge[1].push_back(2);
    Edge[2].push_back(0),Edge[2].push_back(1),Edge[2].push_back(3);
    Edge[3].push_back(2),Edge[3].push_back(4);
    Edge[4].push_back(5);
    Edge[5].push_back(4);
    int N=6;
    dfs(N);
    reshape(N);

    return 0;
}

 

 

 

 

[图的双连通性问题例题]

备用交换机
求图的割点,直接输出。

pku 3177(3352) Redundant Paths
求桥,收缩边双连通子图,构造边双连通图。

POI 1999 仓库管理员 Store-keeper
求点双连通子图。

一些题目:

http://www.cppblog.com/Uriel/articles/121169.html

http://www.chenyajun.com/tag/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F

http://www.cnblogs.com/zhjjla/archive/2010/05/21/1741180.html

http://www.robin47.com/archives/423

 

Reference:

http://www.byvoid.com/blog/biconnect/         byvoid的NX文章

posted on 2010-09-28 21:45 Sosi 阅读(1402) 评论(1)  编辑 收藏 引用

评论

# re: 双连通图 割点与桥 算法代码篇 2012-07-09 17:46 Ramirez26Candace

Some specialists say that <a href="http://goodfinance-blog.com">loans</a> help people to live their own way, because they can feel free to buy necessary goods. Furthermore, different banks present student loan for all people.
  回复  更多评论    

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


统计系统