图的连通性.docx

图的连通性.docx

《图的连通性.docx》由会员分享，可在线阅读，更多相关《图的连通性.docx（9页珍藏版）》请在冰点文库上搜索。

图的连通性

图的连通性

一、求一个图的连通分支

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，使low[w]>=dfnumber[v].

证明（结合图示，有助讲解）：

a）

若v是树根,且儿子数>1，设在图G中有点w1，w2和相应的边（v,w1），（v,w2）.设v所在的连通分支仍为G.G中去除v及和其相关连的边后，看余图是否连通？

若w1到w2有路，则在深度优先算法中过程中，w2应是w1的子孙，而不应该是w1兄弟。

故w1到w2无路。

即两点分属于不同的分支。

若v是树根,且它是割点。

若它只有一个儿子，则删除v及与其相关联的边后，原图中联通的点和它们之间相关联的边仍在余图中，并且仍是连通的。

b）***注：

无向图不存在交叉边。

所以在无向图中，只有树边和向前边（到其真子孙）、向后边（到其真祖先）。

若v不是树根，且DFS树中，存在v的一个儿子w，使low[w]>=dfnumber[v]。

若（w，z）是向后边,则dfnumber[z]>=low[w]

又由假设知：

low[w]>=dfnumber[v]

综合两式，dfnumber[z]>=dfnumber[v]。

于是必有z=v，否则z在DFS树中出现在v之后，矛盾。

即没有由w出发任何向后边，只有（v,w）连结v和w。

若以w为根的子树中有结点含有到v的祖先的向后边，则因为双亲结点的low[]值不大于儿子结点的low[]值，同理可证必为v。

所以去除v后，树、图就被分成互不相连的两个部分。

若v不是树根,且是割点。

反证：

若结论不成立，即任意给定w是v的儿子,则low[w]

即任意v的儿子的w及以其为根的子树中必有结点，它有指向v的真祖先的向后边。

删除v及与其相关的边后，不影响v的真祖先所在的联通分支与其任一子树所在的联通分支之间的联通性。

算法的复杂性：

θ（n+m）

本书处理方法：

number（w）:

w的深度优先编号。

back（v）满足下列规则：

1、初始值取为number（v）

2、当查到有从v出发的一条向后边（v,w）时

back（v）←min{back（v）,number（w）}

3、从w返回到v时，

back（v）←min{back（v）,back（w）}

当从w返回到v时，测试back（w）≥number（v）,如果条件满足，则v就是一个割点

定理：

在一个深度优先搜索树中，不同于根的一个顶点v是一个割点⇔v不是叶子结点，且v的某子树没有关联于v的一个真祖先的向后边。

证明：

v是割点⇔存在顶点x和y,使v在每条从x到y的路上。

举书上的例子加以说明。

算法3.7BICONNECTEDCOMPONETNTS（双连通分支）

输入：

G=（V，E），用连接表表示的一个连通图。

输出：

在G的每一个双连通分支中的边表。

注：

SV是一个顶点栈，用于控制DFS，SE是一个边栈;初始为空。

SV的栈顶的顶点用top表示。

数组NUMBER和BACK意义同上。

算法：

令x是一个任意顶点。

NUMBER（x）←1;NUM←2;x进栈SV。

for在V-{x}中的v,NUMBER（v）←0.

FORWARD（向前）:

while有一条未处理的关联于top的边（top,w），do

〖

（top,w）进栈SE

ifNUMBER（w）>0

thenBACK（top）←min{BACK（top）,NUMBER（w）}

elsedo

【

NUMBER（w）←NUM;

NUM←NUM+1;

BACK（w）←NUMBER（w）

w进栈SV；

】

〗

BACKUP（向后更新）:

if在SV上有多于一个顶点thendo

〖

v←SV上（从top起）第二个顶点;

ifBACK（top）>=NUMBER（v）

thendo

【

输出一个新的双分支标题;

while关联于SE栈顶的边的所有顶点具有数>=NUMBER（v）do输出及退出边栈SE

】

elsedo

【

BACK（v）←min{BACK（v）,BACK（top）};

退出SV[v是现在的top];

gotoFORWARD

】

最坏情况下复杂性可能是θ（n+m）