求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq.docx
- 文档编号:13262520
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:19
- 大小:62.11KB
求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq.docx
《求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq.docx》由会员分享,可在线阅读,更多相关《求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq.docx(19页珍藏版)》请在冰点文库上搜索。
求强连通分量的Kosaraju算法和Tarjan算法的比较byljq
求强连通分量的Kosaraju算法和Tarjan算法的比较
一、定义
在有向图中,如果两个顶点vi,vj间有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(stronglyconnected)。
如果有向图的每两个顶点都强连通,则称该有向图是一个强连通图。
非强连通的有向图的极大强连通子图,称为强连通分量(stronglyconnectedcomponents)。
而对于一个无向图,讨论强连通没有意义,因为在无向图中连通就相当于强连通。
由一个强连通分量内的所有点所组成的集合称为缩点。
在有向图中的所有缩点和所有缩点之间的边所组成的集合称为该有向图的缩图。
例子:
原图:
缩图:
上面的缩图中的
缩点1包含:
1、2,;缩点2包含:
3;
缩点3包含:
4;缩点4包含:
5、6、7。
二、求强连通分量的作用
把有向图中具有相同性质的点找出来,形成一个集合(缩点),建立缩图,能够方便地进行其它操作,而且时间效率会大大地提高,原先对多个点的操作可以简化为对它们所属的缩点的操作。
求强连通分量常常用于求拓扑排序之前,因为原图往往有环,无法进行拓扑排序,而求强连通分量后所建立的缩图则是有向无环图,方便进行拓扑排序。
三、Kosaraju算法
时间复杂度:
O(M+N)注:
M代表边数,N代表顶点数。
所需的数据结构:
原图、反向图(若在原图中存在vi到vj的有向边,在反向图中就变成为vj到vi的有向边)、标记数组(标记是否遍历过)、一个栈(或记录顶点离开时间的数组)。
算法描叙:
步骤1:
对原图进行深度优先遍历,记录每个顶点的离开时间。
步骤2:
选择具有最晚离开时间的顶点,对反向图进行深度优先遍历,并标记能够遍历到的顶点,这些顶点构成一个强连通分量。
步骤3:
如果还有顶点没有遍历过,则继续进行步骤2,否则算法结束。
hdu1269(Kosaraju算法)代码:
#include
#include
constintM=10005;
structnode
{
intvex;
node*next;
};
node*edge1[M],*edge2[M];
boolmark1[M],mark2[M];
intT[M],Tcnt,Bcnt;
voidDFS1(intx)
{
mark1[x]=true;
node*i;
for(i=edge1[x];i!
=NULL;i=i->next)
{
if(!
mark1[i->vex])
{
DFS1(i->vex);
}
}
T[Tcnt]=x;
Tcnt++;
}
voidDFS2(intx)
{
mark2[x]=true;
node*i;
for(i=edge2[x];i!
=NULL;i=i->next)
{
if(!
mark2[i->vex])
{
DFS2(i->vex);
}
}
}
intmain()
{
intn,m;
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0)
{
break;
}
inti,a,b;
for(i=1;i<=n;i++)
{
mark1[i]=mark2[i]=false;
edge1[i]=NULL;
edge2[i]=NULL;
}
node*t;
while(m--)
{
scanf("%d%d",&a,&b);
t=(node*)malloc(sizeof(node));
t->vex=b;
t->next=edge1[a];
edge1[a]=t;
t=(node*)malloc(sizeof(node));
t->vex=a;
t->next=edge2[b];
edge2[b]=t;
}
Tcnt=0;
for(i=1;i<=n;i++)
{
if(!
mark1[i])
{
DFS1(i);
}
}
Bcnt=0;//Bcnt用于记录强连通分量的个数
for(i=Tcnt-1;i>=0;i--)
{
if(!
mark2[T[i]])
{
DFS2(T[i]);
Bcnt++;
}
}
if(Bcnt==1)//如果强连通分量的个数为1则说明该图是强连通图
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
return0;
}
四、Tarjan算法
时间复杂度:
O(M+N)注:
M代表边数,N代表顶点数。
所需的数据结构:
原图、标记数组(与Kosaraju算法的标记不同,这里的标记数组是标记顶点是否在栈内)、一个栈、dfn数组(记录顶点被遍历的时间)、low数组(记录顶点或顶点的子树能够追溯到的最早的栈中顶点的遍历时间)。
算法描叙:
步骤1:
找一个没有被遍历过的顶点v,进行步骤2(v)(遍历时间由1开始累加,若是非连通图,则须重复进行步骤1)。
否则,算法结束。
步骤2(v):
初始化dfn[v]和low[v]的值为当前的遍历时间,并且v进栈;
对于v所有的邻接顶点u:
(1)如果u没有被遍历过,则进行步骤2(u),同时维护low[v]。
(2)如果u已经被遍历过,但还在栈中(即还不属于任一强连通分量),则维护low[v],否则不做任何操作。
如果有dfn[v]==low[v],则把栈中的顶点弹出(直到把v都弹出为止),这些顶点组成一个强连通分量。
hdu1269(Tarjan算法)代码:
#include
#include
#include
constintMAX=10005;
structnode
{
intvex;
node*next;
};
node*g[MAX];
boolins[MAX];
intdfn[MAX],low[MAX],s[MAX],sn,belong[MAX],out[MAX];
intcnt,time;
voiddfs(inti)
{
time++;
dfn[i]=low[i]=time;
s[sn]=i;
sn++;
ins[i]=true;
intj;
node*t;
for(t=g[i];t!
=NULL;t=t->next)
{
j=t->vex;
if(dfn[j]==0)//处理树枝边
{
dfs(j);
if(low[j] { low[i]=low[j]; } } elseif(ins[j]&&dfn[j] { low[i]=dfn[j]; } } if(dfn[i]==low[i]) { cnt++; do { j=s[sn-1]; sn--; ins[j]=false; }while(j! =i); } } voidtarjan(intn) { inti; for(i=1;i<=n;i++) { if(dfn[i]==0) { dfs(i); } } } intmain() { intn,m; while(scanf("%d%d",&n,&m)) { if(n==0&&m==0) { break; } memset(g+1,NULL,n*sizeof(node*)); inta,b; node*t; while(m--) { scanf("%d%d",&a,&b); t=(node*)malloc(sizeof(node)); t->vex=b; t->next=g[a]; g[a]=t; } cnt=0;//cnt用于记录强连通分量的个数 time=0; sn=0; memset(ins+1,false,n*sizeof(bool)); memset(dfn+1,0,n*sizeof(int)); tarjan(n); if(cnt==1)//如果强连通分量的个数为1则说明该图是强连通图 { printf("Yes\n"); } else { printf("No\n"); } } return0; } 五、Kosaraju算法和Tarjan算法比较 举例子比较两个算法: Kosaraju算法: 原图: 建立反向图: 对原图进行深度优先遍历后,顶点的离开时间分别为: 1离开时间为7,2离开时间为5, 3离开时间为4,4离开时间为6, 5离开时间为3,6离开时间为2, 7离开时间为1。 则按顶点按离开时间从大到小排列的序列为: 1、4、2、3、5、6、7, 按上述序列对反向图进行深度优先遍历,属于同一次深度优先遍历的顶点则属于同一个强连通分量(即缩点), 结果: 1、2属于同一个强连通分量,3自己为一个强连通分量,4自己为一个一个强连通分量,5、6、7属于同一个强连通分量。 Tarjan算法: 原图: 对原图进行深度优先遍历(无须回溯): 下面分析整个dfs过程中的ins数组、dfn数组和low数组的变化情况(遍历前先清0): 遍历顶点1: 数组 顶点 ins dfn low 1 true 1 1 2 false 0 0 3 false 0 0 4 false 0 0 5 false 0 0 6 false 0 0 7 false 0 0 遍历顶点2: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 false 0 0 4 false 0 0 5 false 0 0 6 false 0 0 7 false 0 0 遍历顶点3: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 true 3 3 4 false 0 0 5 false 0 0 6 false 0 0 7 false 0 0 遍历顶点5: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 true 3 3 4 false 0 0 5 true 4 4 6 false 0 0 7 false 0 0 遍历顶点6: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 true 3 3 4 false 0 0 5 true 4 4 6 true 5 5 7 false 0 0 遍历顶点7: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 true 3 3 4 false 0 0 5 true 4 4 6 true 5 5 7 true 6 6 离开顶点7: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 true 3 3 4 false 0 0 5 true 4 4 6 true 5 5 7 true 6 4 离开顶点6: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 true 3 3 4 false 0 0 5 true 4 4 6 true 5 4 7 true 6 4 离开顶点5时有dfn[5]==low[5],所以5、6、7组成一个强连通分量: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 true 3 3 4 false 0 0 5 false 4 4 6 false 5 4 7 false 6 4 离开顶点3时有dfn[3]==low[3],所以3自己为一个强连通分量: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 2 3 false 3 3 4 false 0 0 5 false 4 4 6 false 5 4 7 false 6 4 离开顶点2: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 1 3 false 3 3 4 false 0 0 5 false 4 4 6 false 5 4 7 false 6 4 返回顶点1再遍历顶点4: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 1 3 false 3 3 4 true 7 7 5 false 4 4 6 false 5 4 7 false 6 4 离开顶点4时有dfn[4]==low[4],所以4自己为一个强连通分量: 数组 顶点 ins dfn low 1 true 1 1 2 true 2 1 3 false 3 3 4 false 7 7 5 false 4 4 6 false 5 4 7 false 6 4 离开顶点1时有dfn[1]==low[1],所以1、2组成一个强连通分量: 数组 顶点 ins dfn low 1 false 1 1 2 false 2 1 3 false 3 3 4 false 7 7 5 false 4 4 6 false 5 4 7 false 6 4 结果: 1、2属于同一个强连通分量,3自己为一个强连通分量,4自己为一个一个强连通分量,5、6、7属于同一个强连通分量。 两个算法的执行步骤不同,但得出的结果都是一致正确的。 时间复杂度比较: 两个算法的时间复杂度都是O(M+N)(M代表边数,N代表顶点数),但是Kosaraju算法须要进行两次dfs,并且要建立反向图,而Tarjan算法只须就进行一次dfs,在实际的应用中Tarjan算法的时间效率的确比Kosaraju算法要高(网上资料统计出Tarjan算法的时间效率要比Kosaraju算法要高30%左右)。 空间复杂度比较: Tarjan算法虽然比Kosaraju算法多用两个一维数组,但虽然Kosaraju算法比Tarjan算法多浪费建立一个反向图的空间,所以总体来说在空间复杂度上还是Tarjan算法比Kosaraju算法要占优势。 理解难易程度比较: Kosaraju算法单纯的两次深搜的做法显然比Tarjan算法要容易理解。 代码量比较: 两个算法的代码量差距不大。 Kosaraju算法的优势: 该算法依次求出的强连通分量已经符合拓扑排序了。 Tarjan算法的优势: 该算法相比Kosaraju算法拥有时间和空间上的优势。 使用范围: 在稀疏图中差别不明显,而在稠密图中Kosaraju算法建立反向图和两次dfs的操作显然比Tarjan算法的一次dfs要慢的多,所以在稠密图中尽量使用Tarjan算法;而涉及求图的拓扑性质时则选用Kosaraju算法较优。 其它求强连通分量的算法: Gabow算法 (欢迎其他队员讨论与指正)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 求强连通分量的Kosaraju算法和Tarjan算法的比较 by ljq 连通 分量 Kosaraju 算法 Tarjan 比较