3.3 图的连通性.doc

图的连通性
求一个图的连通分支
1设图G=（V，E）是一个无向图，G的一个连通分支是一个最大的连通子图，即一个连通分支是不包含在任何更大的连通子图中。
2对DFS稍作改变，就可用来求无向图的连通分支。从任意一点出发，作DFS，则就可找出在同一个分支中的其它顶点和边。
3算法3.4：DFS（深度优先搜索）
G=（V，E）是一个图或有向图，v∈V。从顶点v开始搜索，其中S是一个栈，初始为空，栈顶用top来表示。
算法：
访问，标志并让v进栈
whileS非空do
〖
while有一个邻接于top而未作标记的顶点wdo
【
访问，标记以及w进栈;
】
出栈S
〗
4“有一个邻接于top而未作标记的顶点w”可用链接表来实现，而且每次寻找邻接于top而未作标记的顶点w时，无必要从头开始寻找，只要记住上次寻找时的位置便可，故链表中每一个单元只被访问过一次。故算法在最坏情况下复杂性最多也只是θ(n+e)。

算法3.6CONNECTEDCOMPONETNTS（连通分支）
输入：G=（V，E）是一个用连接表表示的图。假设V为{1，2，…，n}。
输出：MARK个连通分支中的边表，而且对每个顶点加上编号来指明顶点是在哪一个分支中。
注：一个MARK数组用于对顶点编号，PTR是一个数组（有个项），使PTR指向的邻接表中下一个顶点，而搜索将从开始，下一次力图从分叉出去。
算法：
forv←1tondo
【
MARK(v)←0;PTR(v)←ADJLIST(v);
】
j←1[j用于对一个分支中顶点编号]
forv←1tondo
〖
ifMARK(v)=0thendo
【
output第j个分支的标题;
DFS(v,j);
j←j+1;
】
〗

DFS(v,j)算法：
MARK(v)←j;v进栈;
whileS非空do
〖
whilePTR(top)≠∧do
【
w←VTX(PTR(top));
OUTPUT(top,w);[]
PTR(top)←LINK(PTR(top));
IfMARK(w)=0thendo
〖
MARK(w)←j
w进栈；
〗
】
出栈S
〗
最坏情况下复杂性可能是θ(n+m)
深度优先生成森林
1概念
树边：对一个有向图进行深度优先搜索，在这个过程中，如果某条边所到达的顶点是未被访问过的，则称这条边为树边。
森林：所有树边组成一个森林,称为深度优先生成森林。
祖先：如果v是从根到w的路上的顶点，那么顶点v是顶点w的祖先；如果v≠w，那么v是w的一个真祖先。如果v是w的一个真祖先,那么w是v的一个真子孙。
向前边：除树边外，从一个顶点到森林中其真子孙的边称为向前边。
向后边：除树边外，从一个顶点到森林中该点的真祖先的边称为向后边。
交叉边：除树边外，既不是从祖先到子孙，又不是从子孙到祖先的边称为交叉边。
2性质
到达同一个顶点的边中，只能有一条是树边，其它的或是向前边、或是向后边、或是交叉边。
任一交叉边的起点都在右边。（否则与深度优先搜索过程矛盾）
无向图不存在交叉边
3深度优先编号----dfnumber数组
1）定义：按深度优先搜索过程中访问顶点的先后顺序，对有向图中所有的点进行编号，称为该点的深度优先编号。
2）结论：
w是v的真子孙dfnumber[v]dfnumber[w]dfnumber[v]+k，其中k是v的真子孙的个数。
向前边上顶点的编号是从小到大，向后边上顶点的编号是大到小；交叉边上顶点的编号是从大到小。

无向图的割点和双连通分支
1割点：v是无向图G中的一个顶点，若把它删除（同时也把和它相关联的边删除），使v所在的连通分支变成两个或两个以上的连通分支，则称v是G的一个割点。
2非割点：删去这一点之后，不改变这点所在连通分支的连通性。
3连通度：在图中任意删去k-1个顶点都不改变该图的连通状况，则称图G的连通性为k。k>=2图中没有割点。k>=2，任意删去一点，不改变G的连通性。
4双连通图：一个没有割点的图或说k不小于2的图。即移去任何一个顶点及其相关联的边后，仍是一个连通的子图。
5双连通图的实际意义：如果顶点是电话交换机，边是电话线。如果这个图是双连通的，那么在一个站发生故障时，系统仍是可以工作的。

6用DFS可求图中所有割点：
步骤1：对G用DFS，并计算出各点的深度优先编号dfnumber[]，得到一颗深度优先森林
步骤2：对森林中的每一颗树，按树的后序遍历的顺序，计算各点的Low[]值。
b=min{dfnumber[z]|(v,z)是向后边}
c=min{low[y]|y是树T中v的儿子}
low[v]=min{dfnumber[v],b,c}
步骤3：深度优先树中，
ifv是树根，则v是割点v的儿子数>1
else(v不是树根)，则v是割点存在v的一个儿子w