用两种算法实现求有向图的强连通分支
需积分: 9 65 浏览量
2008-12-29
14:26:25
上传
评论
收藏 385KB PDF 举报
题目：
Strong Connectivity
算法设计思想：
（冒泡法等方法）
（一）第一种算法
用邻接表表示的有向图
G
（邻接点表示表头结点所能够直接到达的结点），对其中的
所有结点进行两次深度优先搜索访问。对所有结点赋予三种颜色值：白、灰、黑；并且所有结
点的初始颜色均标记为白色，访问到的结点标记为灰色，访问完成后将结点标记为黑色。在
进行深度优先搜索时，另赋一个数组
f
记录所有结点访问完成的时间。第一遍深度优先搜索
找出从结点
u
出发所有能够到达的结点
v
的集合，并记录所有结点完成的时间
f[u]
。然后求
出
G
的转置
GT
（邻接点表示能够直接到达表头结点的结点），对
GT
按照访问结点的完成
时间顺序的相反顺序，进行第二遍深度优先搜索，从结点
u
能够到达的结点的集合中找出
所有能够到达结点
u
的结点集，该结点集就是一个强联通分支。
（二）第二种算法
为确定每一个强连通分支的根结点，定义一个数组
LOWLINK
：
LOWLINK[v]=MIN
（
{v}
U
|
从
v
的子孙结点出发存在到结点
w
的回边或交叉边，并且包含
结点
w
的强连通分支的根结点示
v
的一个祖先）；
当且仅当
LOWLINK[v]=v
时，结点
v
是一个强连通分支的根结点。
而为求
LOWLINK
的值，定义方法
SEARCHC(v)
。
首先将所有结点标记为未访问（
NEW
），定义
COUNT
来记录深度优先搜索值，定义
数组
DFNUMBER
存储结点的深度优先搜索值，定义堆栈
STACK
以结点深度优先搜索中
被访问的顺序放置结点。
对于执行过
SEARCHC(v)
的结点标记为已访问（
OLD
）并将
v
压栈；访问结点
v
的邻
接表中的所有结点，若结点
w
标记为
NEW
就对其进行
SEARCHC(w)
，得其
LOWLINK
值
和
DFNUMBER
值，将
LOWLINK[v]
与
LOWLINK[w]
中的较小者赋值给
LOWLINK[v]
，否
则 ， 如 果
DFNUMBER[w]< DFNUMBER[v]
并 且 结 点
w
在 栈 中 ， 将
LOWLINK[v]
与
DFNUMBER [w]
中的较小者赋值给
LOWLINK[v]
；如果
LOWLINK[v]=DFNUMBER [v]
，
将结点
x
从栈中取出并打印，重复此操作直至
x=v
，打印强连通分支结束提示。
当图中只要还存在标记为
NEW
的结点时，就对该结点进行
SEARCH(v)
方法，这样就
将所有的强连通分支找到并将其所有结点打印出来。
算法分析：
（时间分析）
（
1
） 第一种算法
对于第一种算法，由于对每个接点都要访问一次，故而
DFS()
的时间复杂度为
T(v)
（
v
为结
点个数），其中并未包括
DFS_VISIT()
方法耗用的时间；由于没条边都要访问一次，故而
对于
DFS_VISIT()
方法的时间复杂度为
T(E)
（
E
为图中的边数）。综上深度优先搜索的时间
复杂度为
T(V+E)
。由于要进行两次深度优先搜索故时间复杂度为
2T(V+E)
。
（
2
） 第二种算法
对于一次调用
SEARCH(v)
，要对结点
v
的所有未访问过的邻接点
w
进行
SEARCH(w)
运算，
即需要遍访所有的结点和边一次，故算法时间复杂度为
T(V+E)
。
源代码：
（一）第一种算法
#ifndef GRAPH
剩余13页未读，继续阅读
资源评论
明之森
- 粉丝: 9
- 资源: 6
