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

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父父结点的另一个未搜索后代，直到不能搜索后再结点的另一个未搜索后代，直到不能搜索后再退回到上一级退回到上一级。 可用可用栈栈记录搜索过

2、程，现提出更加记录搜索过程，现提出更加详细详细的算的算法，并用来解决法，并用来解决有向图有向图的的分块分块问题。问题。 当从结点当从结点v选择一条未检查边选择一条未检查边时可能时可能: (1)w未访未访问问,则则为为树边树边; (2)w已访已访问问,则则: (2.1)DFS森林中森林中w是是v的的子孙子孙,是是向前边向前边; (2.2)DFS森林中森林中w是是v的的祖先祖先,是是回退边回退边; (2.3)DFS森林中森林中w与与v无关无关,且且dfn(w)dfn(v), 则则是是横跨边横跨边; 无关，且无关，且w先于先于v访问访问,只能只能dfn(w)dfn(v)123456789131110

3、12 当从结点当从结点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访问访问,则为则为回退边回退边或或横跨边横跨边12

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

5、访问点边)FORWARD。(7)回退边回退边(同树同树,指向早访问点的边指向早访问点的边) BACK。(8)横跨边横跨边(指向前棵中早已访问的边指向前棵中早已访问的边CROSS(9)边已访问边已访问EDGE1.Tree=Cross=Back=Forward= ,i=1,Father(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, 否则任选

6、否则任选未查边未查边(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晚晚) 则则Forward=Forward 若若DFN(w)DFN(v) (w早早)且且SCAN(w)=0 则则Back=Back 若若DFN(w)DFN(v)且且SCAN(w)=1 则则Cross

7、=Cross 5. 若若fahter(v)否则转否则转66.若所有结点若所有结点Mark(x)=1结束结束,否否i=i+1转转21.Tree=Cross=Back=Forward=1.Tree=Cross=Back=Forward= ,i=1,Father(v)=0,M,i=1,Father(v)=0,Mark(v)=0,Scan(v)=0,dfn(v)=0,edge(e)=0ark(v)=0,Scan(v)=0,dfn(v)=0,edge(e)=02.r=1 mark(1)=1 dfn(1)=1,v=12.r=1 mark(1)=1 dfn(1)=1,v=13.3.任选任选未查边未查边4.4

8、.标记标记已查已查edge()=1edge()=1 因因mark(2)=0,mark(2)=0,故故i=2,mark(2)=1, i=2,mark(2)=1, dfn(2)=2,father(2)=1,v=2,Tree= dfn(2)=2,father(2)=1,v=2,Tree= 回到回到3 33.3.任选未查边任选未查边4.4.标记标记已查已查edge()=1.edge()=1.123456789131110123.3.任选任选未查边未查边4.4.标记标记已查已查edge()=1edge()=1 因因mark(2)=0,mark(2)=0,故故i=2,Tree=,mark(2)=1, i=

9、2,Tree=,mark(2)=1, dfn(2)=2,father(2)=1,v=2 dfn(2)=2,father(2)=1,v=2 回到回到3 33.3.任选任选未查边未查边4.4.标记标记已查已查edge()=1.edge()=1. 因因mark(3)=0,mark(3)=0,故故i=3,mark(3)=1,i=3,mark(3)=1,Dfn(3)=3,father(3)=2,v=3,Tree=, Dfn(3)=3,father(3)=2,v=3,Tree=, 回到回到3 33.3.任选任选未查边未查边123456789131110123.3.任选任选未查边未查边4.4.标记标记已查已

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

11、 回到回到3 33.3.以以4 4为起点都已查为起点都已查,scan(4)=1,scan(4)=1，转，转5 5 123456789131110124.4.标记标记已查已查edge()=1.edge()=1. 因因mark(4)=0,mark(4)=0,故故i=4,Tree=,i=4,Tree=, mark(4)=1,dfn(4)=4,father(4)=3,v=4 mark(4)=1,dfn(4)=4,father(4)=3,v=4 回到回到3 33.3.以以4 4为起点都已查为起点都已查,scan(4)=1,scan(4)=1，转转5 55.father(4)=35.father(4)=3

12、 0,0,则则v=father(4)=3,v=father(4)=3,转转3 3。3.3.任选任选未查边未查边,转转4 4。4.4.标记边标记边已查已查edge()=1,edge()=1, 因因mark(5)=0,mark(5)=0,故故i=5,Tree=i=5,Tree=, , mark(5)=1,dfn(5)=5,father(5)=3,v=5 mark(5)=1,dfn(5)=5,father(5)=3,v=5 转转3 3. .123456789131110125.father(4)=35.father(4)=3 0,0,则则v=father(4)=3,v=father(4)=3,转转3

13、 3。3.3.任选任选未查边未查边,转转4 4。4.4.标记边标记边已查已查edge()=1,edge()=1, 因因mark(5)=0,mark(5)=0,故故i=5,Tree=i=5,Tree=, , mark(5)=1,dfn(5)=5,father(5)=3,v=5 mark(5)=1,dfn(5)=5,father(5)=3,v=5 转转3 3. .3.3.任选任选未查边未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1, 因因mark(2)=1,dfn(2)dfn(5),scan(2)=0,mark(2)=1,dfn(2)dfn(5),scan(2)=0,

14、 故故back=,back=,回到回到3 3. .123456789131110123.3.任选任选未查边未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1, 因因mark(2)=1,dfn(2)dfn(5),scan(2)=0,mark(2)=1,dfn(2)dfn(5),scan(2)=0, 故故back=,back=,回到回到3 3. .3.3.以以v=5v=5为始点的边都已查为始点的边都已查,scan(5)=1,scan(5)=1,转转5.5.5.father(5)=35.father(5)=3 0,0,则则v=father(5)=3,v=father(5)=

15、3,转转3.3.3.3.以以v=3v=3为始点的边都已查为始点的边都已查,scan(3)=1,scan(3)=1,转转5 55.father(3)=25.father(3)=2 0,0,则则v=father(3)=2,v=father(3)=2,转转3 33.3.任选任选未查边未查边,转转4.4.123456789131110125.father(3)=25.father(3)=2 0,0,则则v=father(3)=2,v=father(3)=2,转转3 33.3.任选任选未查边未查边,转转4.4.4.4.标记边标记边已查已查edge()=1.edge()=1.因因mark(6)=0mark

16、(6)=0则则i=6,mark(6)=1,dfn(6)=i=6, i=6,mark(6)=1,dfn(6)=i=6, father(6)=2father(6)=2, Tree=, Tree=,v=6 ,v=6 转转3 33.3.任选未查边任选未查边,转转4 44.4.标记边标记边已查已查edge()=1. edge()=1. 因因mark(7)=0,mark(7)=0,故故i=7,mark(7)=1,dfn(7)=7,father(7)=6,i=7,mark(7)=1,dfn(7)=7,father(7)=6,Tree=Tree=,v=7 ,v=7 转转3 312345678913111012

17、4.4.标记边标记边已查已查edge()=1. edge()=1. 因因mark(7)=0,mark(7)=0,故故i=7,mark(7)=1,dfn(7)=7,father(7)=6,i=7,mark(7)=1,dfn(7)=7,father(7)=6,Tree=Tree=,v=6 ,v=6 转转3 33.3.以以7 7为起点边都已查完为起点边都已查完, ,故故scan(7)=1,scan(7)=1,转转5.5.5.father(7)=65.father(7)=6 0,0,故故v=father(7)=6,v=father(7)=6,转转3 33.3.任选未查边任选未查边,转转4 44.4.标

18、记标记已查已查, ,因因mark(4)=1,dfn(4)dfn(6),scan(4)=1,mark(4)=1,dfn(4)dfn(6),scan(4)=1,故故Cross=,Cross=,转转3 3123456789131110124.4.标记标记已查已查, ,因因mark(4)=1,dfn(4)dfn(6),scan(4)=1,mark(4)=1,dfn(4)dfn(6),scan(4)=1,故故Cross=,Cross=,转转3 33.3.以以v=6v=6为起点的边都已查完为起点的边都已查完, ,故故scan(6)=1,scan(6)=1,转转5.5.5.father(6)=25.fath

19、er(6)=2 0,0,故故v=father(6)=2,v=father(6)=2,转转3 33.3.以以v=2v=2为起点的边都已查完为起点的边都已查完, ,故故scan(2)=1,scan(2)=1,转转5 55.father(2)=15.father(2)=1 0,0,故故v=father(2)=1,v=father(2)=1,转转3 3123456789131110125.father(2)=15.father(2)=1 0,0,故故v=father(2)=1,v=father(2)=1,转转3 33.3.任选任选未查边未查边,转转4 44.4.标记标记已查已查edge()=1, ed

20、ge()=1, 因因mark(4)=1, mark(4)=1, DFN(4)DFN(1),DFN(4)DFN(1),故故Forward=,Forward=,回到回到3.3.3.3.任选任选未查边未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(7)=1, mark(7)=1, DFN(7)DFN(1),DFN(7)DFN(1),故故Forward=,Forward=,回到回到3.3.3.3.因以因以1 1为起点的边都已查完为起点的边都已查完, ,故故scan(1)=1,scan(1)=1,转转5 55.5.因因father(1)=0father(1)=

21、0为根为根, ,转转6 6123456789131110125.5.因因father(1)=0father(1)=0为根为根, ,转转6 66.6.因为有些结点未访问因为有些结点未访问, ,故故i=8,i=8,转转2 22.2.选满足选满足mark(r)=0mark(r)=0的点的点r=8,mark(8)=1,dfn(8)=8,v=8r=8,mark(8)=1,dfn(8)=8,v=83.3.任选任选未查边未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(9)=0,mark(9)=0,故故i=9i=9mark(9)=1,dfn(9)=9,father(

22、9)=8, v=9mark(9)=1,dfn(9)=9,father(9)=8, v=9Tree=Tree=, , 转转3 33.3.任选任选未查边未查边,转转4.4.4.4.标记标记已查已查edge()=1,edge()=1,因因mark(10)=0,mark(10)=0,故故123456789131110124.4.标记标记已查已查edge()=1,edge()=1,因因mark(10)=0,mark(10)=0,故故 i=10,mark(10)=1,dfn(10)=10,father(10)=9, v=10i=10,mark(10)=1,dfn(10)=10,father(10)=9,

23、v=10Tree=Tree=, , 转转3 33.3.任选未查边任选未查边,转转4.4.4.4.标记标记已查已查edge()=1,edge()=1,因因mark(11)=0,mark(11)=0,故故i=11,mark(11)=1,dfn(11)=11,father(11)=10,v=11i=11,mark(11)=1,dfn(11)=11,father(11)=10,v=11Tree=Tree=, , 转转3 3123456789131110124.4.标记标记已查已查edge()=1,edge()=1,因因mark(11)=0,mark(11)=0,故故i=11,mark(11)=1,df

24、n(11)=11,father(11)=10,v=11i=11,mark(11)=1,dfn(11)=11,father(11)=10,v=11Tree=Tree=, , 转转3 33.3.任选任选未查边未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(6)=1, mark(6)=1, dfn(6)dfn(11),scan(6)=1,dfn(6)dfn(11),scan(6)=1,故故Cross=,Cross=,回到回到3.3.3.3.任选未查边任选未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(9)=1ma

25、rk(9)=1123456789131110123.3.任选未查边任选未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(9)=1, mark(9)=1, dfn(9)dfn(11),scan(9)=0,dfn(9)dfn(11),scan(9)=0,故故back=back=, 转转3 33.3.以以v=11v=11为起点的边都已查完为起点的边都已查完,scan(11)=1,scan(11)=1,转转5 55.father(11)=105.father(11)=10 0,0,故故v=father(11)=10,v=father(11)=10,转转3.3.

26、3.3.任选未查边任选未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(12)=0mark(12)=0故故i=12,mark(12)=1,dfn(12)=12,father(12)=10,v=12i=12,mark(12)=1,dfn(12)=12,father(12)=10,v=12Tree=Tree=,1,0,12, , 转转3 3123456789131110124.4.标记标记已查已查edge()=1,edge()=1,因因mark(12)=0mark(12)=0故故i=12,mark(12)=1,dfn(12)=12,father(12)=1

27、0,v=12i=12,mark(12)=1,dfn(12)=12,father(12)=10,v=12Tree=Tree=, , 转转3 33.3.以以v=12v=12为起点边都已查完为起点边都已查完,scan(12)=1,scan(12)=1,转转5 55.5.因因father(12)=10father(12)=10 0,0,故故v=father(12)=10,v=father(12)=10,转转3 33.3.因因v=10v=10为起点边都已查完为起点边都已查完,scan(10)=1,scan(10)=1,转转5 55.5.因因father(10)=9father(10)=9 0,0,故故v

28、=father(10)=9,v=father(10)=9,转转3 33.3.任选未查边任选未查边,转转4 4123456789131110123.3.任选未查边任选未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(12)=1,mark(12)=1,dfn(12)dfn(9),dfn(12)dfn(9),则则forward=,forward=,回回3 33.3.以以9 9为始点边都已查完为始点边都已查完,scan(9)=1,scan(9)=1,转转5 55.5.因因father(9)=8father(9)=8 0,0,故故v=father(9)=8,v=

29、father(9)=8,转转3.3.3.3.以以8 8为始点边都已查完为始点边都已查完,scan(8)=1,scan(8)=1,转转5 55.5.因因father(8)=0,father(8)=0,转转6 66.6.因为有点未访问因为有点未访问, ,故故i=i+1,i=i+1,转转2 22.2.选满足选满足mark(r)=0mark(r)=0的点的点v=13,mark(13)=1,dfn(13)=13v=13,mark(13)=1,dfn(13)=13123456789131110126.6.因为有点未访问因为有点未访问, ,故故i=i+1,i=i+1,转转2 22.2.选满足选满足mark(

30、r)=0mark(r)=0的点的点v=13,mark(13)=1,dfn(13)=13v=13,mark(13)=1,dfn(13)=133.3.任选未查边任选未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(8)=1, mark(8)=1, dfn(8)dfn(13),scan(8)=1,cross=,dfn(8)dfn(13),scan(8)=1,cross=,转转3 33.3.任选查边任选查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(9)=1, mark(9)=1, dfn(9)dfn(13),scan

31、(9)=1,crossdfn(9)dfn(13),scan(9)=1,cross=,13,9=,转转3 3123456789131110123.3.任选未查边任选未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(9)=1, mark(9)=1, dfn(9)dfn(13),scan(9)=1,crossdfn(9)dfn(13),scan(9)=1,cross=,=,转转3 33.3.任选未查边任选未查边,转转4 44.4.标记标记已查已查edge()=1,edge()=1,因因mark(12)=1, mark(12)=1, dfn(12)dfn(13

32、),scan(12)=1,crossdfn(12)dfn(13),scan(12)=1,cross=,13,1=,2转转3 33.3.因以因以1313为始边已查为始边已查,scan(13)=1,scan(13)=1,转转5 55.5.因因father(13)=0,father(13)=0,转转6 66.6.因所有点因所有点mark(v)=1,mark(v)=1,故结束故结束. . 3 3个根即个根即3 3棵树棵树, ,红实边为树红实边为树, ,粗虚为向前边粗虚为向前边, ,细虚为回退细虚为回退, ,黑线为横跨边黑线为横跨边12345678913111012 从如下的从如下的DFS过程可知过程可

33、知,原图是原图是弱连通弱连通(看成无向图时连看成无向图时连通通)时时,DFS是不连通的是不连通的. 定理定理6.6.1 强连通图的强连通图的DFS林是连通的林是连通的.证明证明:假设假设DFS林不连通林不连通,则至少有则至少有2棵子树棵子树T1,T2.设设r1,r2是其根是其根,r1 r2,T1先于先于T2得到得到. 由由深度优先算法深度优先算法的特点可知的特点可知,不存在不存在起点在起点在T1,终点在终点在T2的边的边. 故从故从r1不能到达不能到达T2的各结点的各结点,故不是强连通的故不是强连通的! 矛盾矛盾,故假设错故假设错.12345678910111213 从如下的从如下的DFS过程

34、可知过程可知,原图是原图是弱连通弱连通(看成无向看成无向图时连通图时连通)时时,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是是G的的DFS树，树，T1,T2,.,Tk是对应强连通块的是对应强连通块的子树。子树。 r1,

35、r2,rk是这些子树的根！是这些子树的根！ 确定强连通块确定强连通块Gi的根的根ri是算法的关键是算法的关键. 为此分析为此分析G中诸边间的关系中诸边间的关系. 确定确定强连通块强连通块Gi的根的根ri是算法的关键是算法的关键.。 (1)若若v Vi, w Vj,i j, 则边则边不可能是不可能是回退边回退边,由回退边的定义可知由回退边的定义可知,始点在始点在Vi的回退边，终点在同一个的回退边，终点在同一个强连通块强连通块Vi中。如下中中。如下中细虚线细虚线。 (2) 若若v Vi, w Vj,i j,rj是是ri的祖先，则边的祖先，则边不可能不可能是是横跨边横跨边, 不是直系才能同跨。只能是

36、：不是直系才能同跨。只能是： (2.1)rj在在ri的左边的左边.下图右边是下图右边是Vi,左边左边Vj ,右右 (2.2) v Vi, w Vi,同一个子树中，左同一个子树中，左， 无向图无向图分块是分块是low(v) dfn(father(v)成立成立,求求Low() 有向图分块是有向图分块是lowLink(v)=dfn(v)成立，求成立，求LowLink()1234567891011121312345678913111012 确定强连通块确定强连通块Gi的根的根ri是算法的关键是算法的关键.。 (1)没有没有类型的类型的回退边回退边,其中其中v Vi, w Vj,i j,始点在始点在Vi

37、的回边，终点同在的回边，终点同在Vi中。中。 (2)没有没有类型的类型的横跨边横跨边,其中其中v Vi, w Vj,i j,rj是是ri的祖先。只能是：的祖先。只能是： (2.1)rj在在ri的左边的左边.下图右边是下图右边是Vi,左边左边Vj , (2.2) v Vi, w Vi,同一个子树中，同一个子树中， 无向图分块是无向图分块是low(v) dfn(father(v)成立成立 有向图分块也需类似有向图分块也需类似lowLink()函数。函数。12345678913111012rjrivw 定义定义6.6.2 LowLink(v)=min(dfn(v),dfn(w)|v的子孙到的子孙到w

38、有有回退边回退边或或横跨边横跨边,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

39、的儿子的儿子s完全扫描后完全扫描后返回返回v时时 LowLink(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); LowLi

40、nk(4)=dfn(4)=4,LowLink(4)=min(LowLink(4),dfn(3)=min(4,3)=3;反向边反向边LowLink(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.若有横跨边若有横跨边

41、(v,w)且且v,w属同连通块属同连通块,公式如公式如(1); 4.当当v的儿子的儿子s完全扫描后完全扫描后返回返回v时时 为了为了判断横跨边属判断横跨边属同一块，需建立同一块，需建立stack数组数组,按按DFS的的访问次序将结点存入访问次序将结点存入,可确定可确定强连通块强连通块包含的结点包含的结点,可判断可判断v与与w是否同块。是否同块。 无向图无向图stack是边集是边集,有向图是点集有向图是点集 一旦得到一个块，则将该块的结点从一旦得到一个块，则将该块的结点从stack中移出。中移出。 添添point数组，若数组，若v在在stack中则中则point(v)=1,否则为否则为0。123

42、456789101112131.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,执行执行以下操作后回到以下操作后回到3 4.1若若 则则 i=i+1, DFN(w)=i, LowLink(w)=i, Mark(

43、w)=1, father(w)=v,stack+=w, point(w)=1,v=w 4.2 若若,DFN(w)DFN(v),point(w)=1(w与与v同块同块) 则则LowLink(v)=min(LowLink(v),dfn(w) 5. 若若则构成块则构成块,移去移去stack的栈顶到的栈顶到v的结的结点点,重新置其重新置其point(x)=0。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

44、=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(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,ma

45、rk(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)=1,dfn(3)dfn(4),point(3)=1LowLink(4)=min(LowLink(4),dfn(3)=3(回退边回退边),转转3 3.因因4为起点的边都已

46、查，转为起点的边都已查，转5 5.因因LowLink(4) dfn(4)故不构成块故不构成块, 又因又因father(4)=3 0,故故 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=5123456789101112134.标示标示已查已查,因因mark(5)=0,i=5,dfn(5)=5,mark(5)=1, Low

47、Link(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)=3 0,故故 lowLink(3)=min(LowLink(3),LowLink(5)=3 v=father(5)=3 转转33.因以因以3为起

48、点边已查为起点边已查,转转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)=2 0，故可回溯，故可回溯 lowLink(2)=min(LowLink(2),LowLink(3)=2, v=father(3)=2,转转33.任选未查边任选未查边，转，转44.标示标示已查已查,因因mark(6)=0

49、,故故i=6,dfn(6)=6,mark(6)=1,Father(6)=2,lowLink(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

50、=1,2,6,7,v=73.任选未查边任选未查边,转转44.标示标示已查已查,因因mark(6)=1,dfn(6)dfn(7),point(6)=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,f