本文共 1786 字,大约阅读时间需要 5 分钟。
首先明白几个定理:
1. 判断无向图的连通性。
用bfs或者dfs,遍历,如果能遍历完所有结点,则是连通图。
比如,要求无向图的割点的集合,最容易想到的方法就是依次测试每个结点判断其对图连通性的影响。
有更简单的方法。
2. 有向图的单连通性。对于任意的两个点,i,j,存在i到j或者j到i的路径
1. 最容易想到的算法是floyd算法。
floyd算法本来用以求图中任意两点间的最短路径,大体思路是:
依次以每个点k作为i--->j的中间节点,求d(i,j) = min(d(i,j),d(i,k)+d(k,j))
如果用floyd算法判断任意两个点的连通性?
可以直接用上面的算法,但是可以将加法和min操作转为位运算。
d(i,j) = d(i,j) | (d(i,k) & d(k,j))
2. 上面的算法时间复杂度是O(n^3)
思路:判断一个有向图是不是强连通的可以直接用tarjan算法。
但是判断是不是单向联通的就麻烦了。
开始我想用floyd,后来又想到了一条路一条路的找,但是这两种方法的复杂度太高。
正解:对于一个DAG图,若是单向联通的我们可以有这么一个性质,就是存在一条路,这条路可以经过图中的每一个点。下面证明一下。
我们从图中选择一个入度为0的点a,和一个出度为0的点b,则剩下的点肯定都满足在a,b之间。
不妨找一点k ,则a~k~b,剩下的点也肯定在两个~之间的一个,以此类推。
我们先让这张图变成DAG,我们用tarjan算法缩点,这张图就变成了一个DAG图。
#include也可以用上面的算法求出有向图的单连通分支, 对入度为0点,递归搜寻各向前通路至每一不可再前行点时,可对应得出一单项连通分支#include #include #include using namespace std;stack s;struct hh { int u,v,next; }tp[6005],map[6006]; int head[1050],mhead[1050],num,mnum,low[1050],lp[1050],now,f[1050]; bool in[1050]; int n,m,step,total; void add(int a,int b) { tp[num].u=a;tp[num].v=b; tp[num].next=head[a]; head[a]=num++; } void madd(int a,int b) { map[mnum].u=a; map[mnum].v=b; map[mnum].next=mhead[a]; mhead[a]=mnum++; } void init() { int a,b; num=0; mnum=0; step=total=1; while(!s.empty()) s.pop(); for(int i=1;i<=n;i++) { in[i]=0; low[i]=lp[i]=f[i]=0; } memset(head,-1,sizeof(head)); memset(mhead,-1,sizeof(mhead)); scanf("%d%d",&n,&m); for(int i=0;i
转载地址:http://cpeti.baihongyu.com/