6.6-有向图的DFS与分块汇总课件

1、6.6有向图的DFS算法与图的块划分 DFS(depth first search深度优先搜索)在2.2中判断二点之间是否连续时使用过: 从某一点出发v0, 找v0一个直接下代v1, father(v1)=v0, 找v1未搜索的直接后继v2, father(v2)=v1, 当vj没有未搜索后代时,回到father(vj),找vj父结点的另一个未搜索后代，直到不能搜索后再退回到上一级。 可用栈记录搜索过程，现提出更加详细的算法，并用来解决有向图的分块问题。 当从结点v选择一条未检查边时可能: (1)w未访问,则为树边; (2)w已访问,则: (2.1)DFS森林中w是v的子孙,是向前边; (2.

2、2)DFS森林中w是v的祖先,是回退边; (2.3)DFS森林中w与v无关,且dfn(w)dfn(v), 则是横跨边; 无关，且w先于v访问,只能dfn(w)dfn(v)12345678913111012 当从结点v选择一条未检查边时可能: (1)w未访问,则为树边; (2)w已访问,则: (2.1)在DFS森林中w是v的子孙,是向前边; (2.2)在DFS森林中w是v的祖先,是回退边; (2.3)在DFS森林中w与v无关且dfn(w)dfn(v), 则是横跨边; 只有4种边。 若dfn(w)dfn(v)即w晚于v访问,则为树边/向前边 若dfn(w)dfn(v)即w早于v访问,则为回退边或横

3、跨边12345678913111012编程实现时，需要的数组为：(1)已访问结点的数组MARK(2)已访问点的父结点的数组FATHER(3)深度优先指标数组DFN。 仅在结点x第一次被访问时给DFN(x) 赋值。 如果x是第i个被赋值的结点，则DFN(x)=I(4)点的边是否全扫描SCAN,区分回退边与横跨 (5)树边(同棵树中结点首次访问所用边)TREE。(6)向前边(同树,指向晚访问点边)FORWARD。(7)回退边(同树,指向早访问点的边) BACK。(8)横跨边(指向前棵中早已访问的边CROSS(9)边已访问EDGE1.Tree=Cross=Back=Forward=,i=1,Fath

4、er(v)=0,Mark(v)=0,Scan(v)=0,dfn(v)=0,edge(e)=02. 任选满足Mark(r)=0的结点r(确定新根),置其 DFN(r)=i,Mark(r)=1,v=r(当前结点)3.若以v起点的边都已查,scan(v)=1转5, 否则任选未查边(v,w)转44.边(v,w)标为已查Edge(v,w)=1,执行以下操作后回到3 4.1若Mark(w)=0(未访),则 i=i+1, DFN(w)=i, Tree=Tree Mark(w)=1, father(w)=v, v=w(修改新当前结点) 4.2 若Mark(w)=1(已访), 若DFN(w)DFN(v)(w晚)

5、 则Forward=Forward 若DFN(w)DFN(v) (w早)且SCAN(w)=0 则Back=Back 若DFN(w)DFN(v)且SCAN(w)=1 则Cross=Cross5. 若fahter(v)0(不是根)则v=fahter(v)转3，否则转66.若所有结点Mark(x)=1结束,否i=i+1转21.Tree=Cross=Back=Forward=,i=1,Father(v)=0,Mark(v)=0,Scan(v)=0,dfn(v)=0,edge(e)=02.r=1 mark(1)=1 dfn(1)=1,v=13.任选未查边4.标记已查edge()=1 因mark(2)=0

6、,故i=2,mark(2)=1, dfn(2)=2,father(2)=1,v=2,Tree= 回到33.任选未查边4.标记已查edge()=1.123456789131110123.任选未查边4.标记已查edge()=1 因mark(2)=0,故i=2,Tree=,mark(2)=1, dfn(2)=2,father(2)=1,v=2 回到33.任选未查边4.标记已查edge()=1. 因mark(3)=0,故i=3,mark(3)=1,Dfn(3)=3,father(3)=2,v=3,Tree=, 回到33.任选未查边123456789131110123.任选未查边4.标记已查edge()

7、=1. 因mark(3)=0,故i=3,Tree=,mark(3)=1,Dfn(3)=3,father(3)=2,v=3 回到33.任选未查边4.标记已查edge()=1. 因mark(4)=0,故i=4,Tree=, mark(4)=1,dfn(4)=4,father(4)=3,v=4 回到33.以4为起点都已查,scan(4)=1，转5 123456789131110124.标记已查edge()=1. 因mark(4)=0,故i=4,Tree=, mark(4)=1,dfn(4)=4,father(4)=3,v=4 回到33.以4为起点都已查,scan(4)=1，转55.father(4)

8、=30,则v=father(4)=3,转3。3.任选未查边,转4。4.标记边已查edge()=1, 因mark(5)=0,故i=5,Tree=, mark(5)=1,dfn(5)=5,father(5)=3,v=5 转3.123456789131110125.father(4)=30,则v=father(4)=3,转3。3.任选未查边,转4。4.标记边已查edge()=1, 因mark(5)=0,故i=5,Tree=, mark(5)=1,dfn(5)=5,father(5)=3,v=5 转3.3.任选未查边,转44.标记已查edge()=1, 因mark(2)=1,dfn(2)dfn(5),

9、scan(2)=0, 故back=,回到3.123456789131110123.任选未查边,转44.标记已查edge()=1, 因mark(2)=1,dfn(2)dfn(5),scan(2)=0, 故back=,回到3.3.以v=5为始点的边都已查,scan(5)=1,转5.5.father(5)=30,则v=father(5)=3,转3.3.以v=3为始点的边都已查,scan(3)=1,转55.father(3)=20,则v=father(3)=2,转33.任选未查边,转4.123456789131110125.father(3)=20,则v=father(3)=2,转33.任选未查边,转

10、4.4.标记边已查edge()=1.因mark(6)=0则i=6,mark(6)=1,dfn(6)=i=6, father(6)=2, Tree=,v=6 转33.任选未查边,转44.标记边已查edge()=1. 因mark(7)=0,故i=7,mark(7)=1,dfn(7)=7,father(7)=6,Tree=,v=7 转3123456789131110124.标记边已查edge()=1. 因mark(7)=0,故i=7,mark(7)=1,dfn(7)=7,father(7)=6,Tree=,v=6 转33.以7为起点边都已查完,故scan(7)=1,转5.5.father(7)=60

11、,故v=father(7)=6,转33.任选未查边,转44.标记已查,因mark(4)=1,dfn(4)dfn(6),scan(4)=1,故Cross=,转3123456789131110124.标记已查,因mark(4)=1,dfn(4)dfn(6),scan(4)=1,故Cross=,转33.以v=6为起点的边都已查完,故scan(6)=1,转5.5.father(6)=20,故v=father(6)=2,转33.以v=2为起点的边都已查完,故scan(2)=1,转55.father(2)=10,故v=father(2)=1,转3123456789131110125.father(2)=1

12、0,故v=father(2)=1,转33.任选未查边,转44.标记已查edge()=1, 因mark(4)=1, DFN(4)DFN(1),故Forward=,回到3.3.任选未查边,转44.标记已查edge()=1,因mark(7)=1, DFN(7)DFN(1),故Forward=,回到3.3.因以1为起点的边都已查完,故scan(1)=1,转55.因father(1)=0为根,转6123456789131110125.因father(1)=0为根,转66.因为有些结点未访问,故i=8,转22.选满足mark(r)=0的点r=8,mark(8)=1,dfn(8)=8,v=83.任选未查边,

13、转44.标记已查edge()=1,因mark(9)=0,故i=9mark(9)=1,dfn(9)=9,father(9)=8, v=9Tree=, 转33.任选未查边,转4.4.标记已查edge()=1,因mark(10)=0,故123456789131110124.标记已查edge()=1,因mark(10)=0,故 i=10,mark(10)=1,dfn(10)=10,father(10)=9, v=10Tree=, 转33.任选未查边,转4.4.标记已查edge()=1,因mark(11)=0,故i=11,mark(11)=1,dfn(11)=11,father(11)=10,v=11T

14、ree=, 转3123456789131110124.标记已查edge()=1,因mark(11)=0,故i=11,mark(11)=1,dfn(11)=11,father(11)=10,v=11Tree=, 转33.任选未查边,转44.标记已查edge()=1,因mark(6)=1, dfn(6)dfn(11),scan(6)=1,故Cross=,回到3.3.任选未查边,转44.标记已查edge()=1,因mark(9)=1123456789131110123.任选未查边,转44.标记已查edge()=1,因mark(9)=1, dfn(9)dfn(11),scan(9)=0,故back=,

15、转33.以v=11为起点的边都已查完,scan(11)=1,转55.father(11)=100,故v=father(11)=10,转3.3.任选未查边,转44.标记已查edge()=1,因mark(12)=0故i=12,mark(12)=1,dfn(12)=12,father(12)=10,v=12Tree=, 转3123456789131110124.标记已查edge()=1,因mark(12)=0故i=12,mark(12)=1,dfn(12)=12,father(12)=10,v=12Tree=, 转33.以v=12为起点边都已查完,scan(12)=1,转55.因father(12)

16、=100,故v=father(12)=10,转33.因v=10为起点边都已查完,scan(10)=1,转55.因father(10)=90,故v=father(10)=9,转33.任选未查边,转4123456789131110123.任选未查边,转44.标记已查edge()=1,因mark(12)=1,dfn(12)dfn(9),则forward=,回33.以9为始点边都已查完,scan(9)=1,转55.因father(9)=80,故v=father(9)=8,转3.3.以8为始点边都已查完,scan(8)=1,转55.因father(8)=0,转66.因为有点未访问,故i=i+1,转22.

17、选满足mark(r)=0的点v=13,mark(13)=1,dfn(13)=13123456789131110126.因为有点未访问,故i=i+1,转22.选满足mark(r)=0的点v=13,mark(13)=1,dfn(13)=133.任选未查边,转44.标记已查edge()=1,因mark(8)=1, dfn(8)dfn(13),scan(8)=1,cross=,转33.任选查边,转44.标记已查edge()=1,因mark(9)=1, dfn(9)dfn(13),scan(9)=1,cross=,转3123456789131110123.任选未查边,转44.标记已查edge()=1,因

18、mark(9)=1, dfn(9)dfn(13),scan(9)=1,cross=,转33.任选未查边,转44.标记已查edge()=1,因mark(12)=1, dfn(12)dfn(13),scan(12)=1,cross=,转33.因以13为始边已查,scan(13)=1,转55.因father(13)=0,转66.因所有点mark(v)=1,故结束. 3个根即3棵树,红实边为树,粗虚为向前边,细虚为回退,黑线为横跨边12345678913111012 从如下的DFS过程可知,原图是弱连通(看成无向图时连通)时,DFS是不连通的. 定理6.6.1 强连通图的DFS林是连通的.证明:假设D

19、FS林不连通,则至少有2棵子树T1,T2.设r1,r2是其根,r1r2,T1先于T2得到. 由深度优先算法的特点可知,不存在起点在T1,终点在T2的边. 故从r1不能到达T2的各结点,故不是强连通的! 矛盾,故假设错.12345678910111213 从如下的DFS过程可知,原图是弱连通(看成无向图时连通)时,DFS是不连通的. 定理6.6.1 强连通图的DFS林是连通的. 定义6.6.1 有向图G极大的强连通子图称为它的强连通分量,或强连通块. 推论6.6.1 对于G的强连通分量的DFS子树是连通的. 设G1=(V1,E1),G2=(V2,E2).,Gk=(Vk,Ek)是G的强连通块。 T

20、是G的DFS树，T1,T2,.,Tk是对应强连通块的子树。 r1,r2,rk是这些子树的根！ 确定强连通块Gi的根ri是算法的关键. 为此分析G中诸边间的关系. 确定强连通块Gi的根ri是算法的关键.。 (1)若vVi, wVj,ij, 则边不可能是回退边,由回退边的定义可知,始点在Vi的回退边，终点在同一个强连通块Vi中。如下中细虚线。 (2) 若vVi, wVj,ij,rj是ri的祖先，则边不可能是横跨边, 不是直系才能同跨。只能是： (2.1)rj在ri的左边.下图右边是Vi,左边Vj ,右 (2.2) vVi, wVi,同一个子树中，左， 无向图分块是low(v)dfn(father(

21、v)成立,求Low() 有向图分块是lowLink(v)=dfn(v)成立，求LowLink()1234567891011121312345678913111012 确定强连通块Gi的根ri是算法的关键.。 (1)没有类型的回退边,其中vVi, wVj,ij,始点在Vi的回边，终点同在Vi中。 (2)没有类型的横跨边,其中vVi, wVj,ij,rj是ri的祖先。只能是： (2.1)rj在ri的左边.下图右边是Vi,左边Vj , (2.2) vVi, wVi,同一个子树中， 无向图分块是low(v)dfn(father(v)成立 有向图分块也需类似lowLink()函数。12345678913

22、111012rjrivw 定义6.6.2 LowLink(v)=min(dfn(v),dfn(w)|v的子孙到w有回退边或横跨边,v与w属同一个强连通块 ) v=5时w=3,5(v)的子孙4到3(w)有回退边! 定理6.6.2:v是有向图G的强连通分支的根 LowLink(v)=dfn(v) LowLink(v)的算法： 1.首次访问v时,LowLink(v)=dfn(v); 2.若有回退边被查, 如v=4,w=3时 LowLink(v)=min(LowLink(v),dfn(w); (1) 3.若有横跨边且v,w同块,公式见(1),如v=5,w=4时 4.当v的儿子s完全扫描后返回v时 Lo

23、wLink(v)=min(LowLink(v),lowLink(s); 12345678910111213LowLink(v)的算法： 1.首次访问v时,LowLink(v)=dfn(v); 2.若有回退边被查, LowLink(v)=min(LowLink(v),dfn(w); (1) 3.若有横跨边且v,w属同连通块,公式如(1); 4.当v的儿子s完全扫描后返回v时 LowLink(v)=min(LowLink(v),lowLink(s); LowLink(4)=dfn(4)=4,LowLink(4)=min(LowLink(4),dfn(3)=min(4,3)=3;反向边LowLink

24、(3)=min(lowlink(3),linklow(4)=3LowLink(5)=dfn(5)=5LowLink(5)=min(lowLink(5),dfn(4)=4 横跨边12345678910111213LowLink(v)的算法： 1.首次访问v时,LowLink(v)=dfn(v); 2.若有回退边被查, LowLink(v)=min(LowLink(v),dfn(w); (1) 3.若有横跨边(v,w)且v,w属同连通块,公式如(1); 4.当v的儿子s完全扫描后返回v时 为了判断横跨边属同一块，需建立stack数组,按DFS的访问次序将结点存入,可确定强连通块包含的结点,可判断v

25、与w是否同块。 无向图stack是边集,有向图是点集 一旦得到一个块，则将该块的结点从stack中移出。 添point数组，若v在stack中则point(v)=1,否则为0。123456789101112131.stack=,i=1,Father(v)=0,Mark(v)=0,point(v)=0,edge(e)=02.任选满足Mark(r)=0的结点r,置其 DFN(r)=i, Mark(r)=1, LowLink(r)=1,stack1=r,point(r)=1,v=r3.若以v起点的边都已查转5,否则任选未查边(v,w)转44.边(v,w)标为已查Edge(v,w)=1,执行以下操作后

26、回到3 4.1若Mark(w)=0 则 i=i+1, DFN(w)=i, LowLink(w)=i, Mark(w)=1, father(w)=v,stack+=w, point(w)=1,v=w 4.2 若Mark(w)=1,DFN(w)DFN(v),point(w)=1(w与v同块) 则LowLink(v)=min(LowLink(v),dfn(w) 5. 若LowLink(v)=dfn(v)则构成块,移去stack的栈顶到v的结点,重新置其point(x)=0。 若father(v)=0转6，否则LowLink(father(v)=min(LowLink(father(v),LowLin

27、k(v),v=fahter(v)转3 6.若所有结点Mark(x)=1结束,否则转2 1.stack=,i=1,Father(v)=0,Mark(v)=0,point(v)=0 2.DFN(1)=1, Mark(1)=1, LowLink(1)=1, stack=1, point(1)=1,v=r 3.任选未查边,转4 4.标示已查,因mark(2)=0,i=2,dfn(2)=2, mark(2)=1, LowLink(2)=2,stack=1,2,point(2)=1,father(2)=1,v=2,转3 3.任选，转4 4.标示已查,因mark(3)=0,i=3,dfn(3)=3,mark

28、(3)=1,LowLink(3)=3,stack=1,2,3,point(3)=1,fath(3)=2,v=3,转3 3. 任选,转4 4.标示已查,因mark(4)=0,i=4,dfn(4)=4,mark(4)=1,LowLink(4)=4,stack=1,2,3,4,point(4)=1,fath(4)=3,v=4,转412345678910111213 4.标示已查,因mark(4)=0,i=4,dfn(4)=4,mark(4)=1,LowLink(4)=4,stack=1,2,3,4,point(4)=1,fath(4)=3,v=4,转3 3.任选，转4 4.标示已查,因mark(3)

29、=1,dfn(3)dfn(4),point(3)=1LowLink(4)=min(LowLink(4),dfn(3)=3(回退边),转3 3.因4为起点的边都已查，转5 5.因LowLink(4)dfn(4)故不构成块, 又因father(4)=30,故 lowLink(father(4)=min(lowLink(3),lowLink(4)=3,v=3转3 3.任选,转4 4.标示已查,因mark(5)=0,i=5,dfn(5)=5,mark(5)=1, LowLink(5)=5,stack=1,2,3,4,5,point(5)=1,fath(5)=3,v=512345678910111213

30、4.标示已查,因mark(5)=0,i=5,dfn(5)=5,mark(5)=1, LowLink(5)=5,stack=1,2,3,4,5,point(5)=1,fath(5)=3,v=53.任选未查边,转44.标示已查,因mark(4)=1,dfn(4)dfn(5),point(4)=1,lowLink(5)=min(lowLink(5), dfn(4)=4(横跨边),转33.因以5为起点边已查，转54.因lowLink(5)dfn(5)故不是块 又因father(5)=30,故 lowLink(3)=min(LowLink(3),LowLink(5)=3 v=father(5)=3 转3

31、3.因以3为起点边已查,转55.因lowLink(3)=dfn(3)=3故为块！栈顶到3所有点3,4,512345678910111213 stack=1,2,3,4,55.因lowLink(3)=dfn(3)=3故为块！栈顶到3所有点3,4,5,Point(3)=point(4)=point(5)=0. 又因father(3)=20，故可回溯 lowLink(2)=min(LowLink(2),LowLink(3)=2, v=father(3)=2,转33.任选未查边，转44.标示已查,因mark(6)=0,故i=6,dfn(6)=6,mark(6)=1,Father(6)=2,lowLin

32、k(6)=6,point(6)=1,stack=1,2,6,v=63.任选未查边,转44.标示已查,因mark(7)=0,故i=7,dfn(7)=7,mark(7)=1,Father(7)=6,lowLink(7)=7,point(7)=1,stack=1,2,6,7,v=7123456789101112134.标示已查,因mark(7)=0,故i=7,dfn(7)=7,mark(7)=1,Father(7)=6,lowLink(7)=7,point(7)=1,stack=1,2,6,7,v=73.任选未查边,转44.标示已查,因mark(6)=1,dfn(6)dfn(7),point(6)=

33、1,lowLink(7)=min(LowLink(7),dfn(6)=6(回退边) 3.任选示查边,转44.标示已查,因mark(8)=0,故i=8,dfn(8)=8,mark(8)=1,fath(8)=6,lowLink(8)=8,point(8)=1,stack=1,2,6,7,8,v=83.任选未查边,转44.标示已查,因mark(9)=0,故i=9,dfn(9)=9,mark(9)=1,fath(9)=8,lowLink(9)=9,point(9)=1,stack=1,2,6,7,8,9,v=93.任选未查边,转4123456789101112134.标示已查,因mark(9)=0,故

34、i=9,dfn(9)=9,mark(9)=1,fath(9)=8,lowLink(9)=9,point(9)=1,stack=1,2,6,7,8,9,v=93.任选未查边,转44.标示已查,因mark(7)=1,dfn(7)dfn(9),point(7)=1故lowLink(9)=min(lowLink(9),dfn(7)=7,转33.因以9为起点边全查完,转55.lowLink(9)dfn(9),故不是块 又因father(9)=8 0不是根,故 lowLink(8)=min(LowLink(8),LowLink(9)=7,v=8 转33.任选未查边,转44.标示已查,因mark(10)=0

35、,故i=10,dfn(10)=10, mark(10)=1,fath(10)=8, lowLink(10)=10, point(10)=1, stack=1,2,6,7,8,9,10,v=10,转3.123456789101112134.标示已查,因mark(10)=0,故i=10,dfn(10)=10, mark(10)=1,fath(10)=8, lowLink(10)=10, point(10)=1, stack=1,2,6,7,8,9,10,v=10,转3.3.任选转44.标示已查,因mark(9)=1,dfn(9)dfn(10),point(9)=1,故lowLink(10)=min

36、(LowLink(10),dfn(9)=9(横跨边),转33.因以10为起点边全查完,转55.因lowLink(10)dfn(10)故不是块.又因father(10)=8 0,不是根,可回溯.lowLink(8)=min(LowLink(8),lowLink(10)=7 v=83.因以8为起点边全查完,转5123456789101112133.因以8为起点边全查完,转55.因lowLink(8)dfn(8)故不是块.又因father(8)=6 0,不是根,可回溯.lowLink(6)=min(LowLink(6),lowLink(8)=6 v=6转33.因以6为起点边全查完,转5 stack=1,2,6,7,8,9,105.因lowLink(6)=dfn(6)故是块.栈顶到6的6,7,8,9,10是块Point(6)point(10)=0, stack=1,2又因father(6)=2 0,不是根,可回溯.lowLink(2)=min(LowLink(2),lowLink(2)=2 v=2转33.因以2为起点边全查完,转5 5.因lowLink(2)=dfn(2)故是块.栈顶到22是块poin