图论-图的连通性
图论算法
三、图的连通性算法
求图的连通性之零:遍历欧拉路
求图的连通性之一:判断两点是否连通
1. Floyed 算法
时间复杂度:O(N
3
)
算法实现:不再赘述。
2. 遍历算法
时间复杂度:O(N算法实现:
从任意一个顶点出发,进行一次遍历,就可以求出此顶点和其它各个顶点的连通状况。所以只要把每个顶点作为出发点都进行一次遍历,就能知道任意两个顶点之间是否有路存在。
2
)
可以使用DFS 实现。
3. 并查集算法
时间复杂度:O(N*小常数)
算法实现:只适用于无向图,即判断两点是否有相同的父亲。
例题:寻找满足条件的连通分支。
求图的连通性之二:求无向图的连通分量个数。
只要使用并查集即可,如果两个点的祖先相同,显然属
于同一连通分量。一遍循环,统计一共有多少个祖先即可。
求图的连通性之三:求有向图的强连通分量个数与收缩强连通分量。
主要采用Kosaraju 算法,复杂度O(N)。
一个有向图的强连通分量,能够收缩为一个点,统计最后点的个数,即是强连通分量的个数。
(a )
(b )
Kosaraju 算法的思想讲解:
1) 对原图进行深搜(DFS ),得到一个深搜出栈的顺
序。
假设出栈顺序 3→5→2→4→1
将原图每条边进行反向。 2)
逆序 ,对反图进行搜3)
索。
出栈顺序 3→5→2→4→1 逆序 1→4→2→5→3
color:=0;
for i:= p downto 1 do {得到的出栈顺序的逆序就是拓扑顺序}
if col[a [i ]]=0 then {没染色过的点,就是没被搜索到的点} begin inc(color ) ;
DFS2(a [i ]); {按照1中生成顺序再进行DFS 染色染成同色的是一个强连通块} end ;
并且在每轮搜索中对搜到的点进行染色。
显然,每条边都进行反向后,在反图中按出栈的逆序也能搜到的连通块一定是强连通块。
因为如果是强连通子图,那么反向没有任何影响,依然是强连通子图。但如果是单向的边连通,反向后再按原序就无法访问了(因此反向处理是对非强
连通块的过滤)。
基本框架:order 数组用来存顺序,col 数组进行染色。
Procedure DFS1(v)
Begin
Vis[v]:=true;
For i:=1 to 所有在正图连接的点 If not vis then DFS1(); Inc(p);
Order[p]:=v; End;
Procedure DFS2(V) Begin
Col[v]:=color;
For i:=1 to 所有在反图中连接的点 If col[]=0 then DFS2() End;
Begin 读入
Fillchar(vis,FALSE); P=0;
For i:=1 to n do If not vis then DFS1(i)
对每条边反向。 Fillchar(col,0) Color:=0;
For i:=p downto 1 do //注意p 不一定等于n ,一个点可能出栈多次! If col[ order[i] ]=0 then Begin
Color+1;
DFS2( order[ i ] ) End; End.
Color 的值就是强连通块个数,col 相同的点就相当于收缩成了一个点