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

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)DFS森林中w是v的祖先,是回退边;(2.3)DFS森林中w与v无关,且dfn(w)是横跨边;无关，且w先于v访问,只能dfn(w)dfn(v),当从结点v选择一条未检查边时可能:(1)w未访问,则为树边;(2)w已访问,则:(2.1)在DFS森林中w是v的子孙,是向前边;(2.2)在DFS森林中w是v的祖先,是回退边;(2.3)在DFS森林中w与v无关且dfn(w)是横跨边;只有4种边。若dfn(w)dfn(v)即w晚于v访问,则为树边/向前边 若dfn(w)dfn(v)即w早于v访问,则为回退边或横跨边,编程实现时，需要的数组为：(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)边已访问EDGE,1.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,否则任选未查边(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(w)5.若fahter(v)0(不是根)则v=fahter(v)转3，否则转66.若所有结点Mark(x)=1结束,否i=i+1转2,1.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,故i=2,mark(2)=1,dfn(2)=2,father(2)=1,v=2,Tree=回到33.任选未查边4.标记已查edge()=1.,3.任选未查边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.任选未查边,3.任选未查边4.标记已查edge()=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,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，转55.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.,5.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),回到3.,3.任选未查边,转44.标记已查edge()=1,因mark(2)=1,dfn(2),回到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.,5.father(3)=20,则v=father(3)=2,转33.任选未查边,转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 转3,4.标记边已查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,故v=father(7)=6,转33.任选未查边,转44.标记已查,因mark(4)=1,dfn(4),转3,4.标记已查,因mark(4)=1,dfn(4),转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,转3,5.father(2)=10,故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为根,转6,5.因father(1)=0为根,转66.因为有些结点未访问,故i=8,转22.选满足mark(r)=0的点r=8,mark(8)=1,dfn(8)=8,v=83.任选未查边,转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,故,4.标记已查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=11Tree=,转3,4.标记已查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),回到3.3.任选未查边,转44.标记已查edge()=1,因mark(9)=1,3.任选未查边,转44.标记已查edge()=1,因mark(9)=1,dfn(9),转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=,转3,4.标记已查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)=100,故v=father(12)=10,转33.因v=10为起点边都已查完,scan(10)=1,转55.因father(10)=90,故v=father(10)=9,转33.任选未查边,转4,3.任选未查边,转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.选满足mark(r)=0的点v=13,mark(13)=1,dfn(13)=13,6.因为有点未访问,故i=i+1,转22.选满足mark(r)=0的点v=13,mark(13)=1,dfn(13)=133.任选未查边,转44.标记已查edge()=1,因mark(8)=1,dfn(8),转33.任选查边,转44.标记已查edge()=1,因mark(9)=1,dfn(9),转3,3.任选未查边,转44.标记已查edge()=1,因mark(9)=1,dfn(9),转33.任选未查边,转44.标记已查edge()=1,因mark(12)=1,dfn(12),转33.因以13为始边已查,scan(13)=1,转55.因father(13)=0,转66.因所有点mark(v)=1,故结束.3个根即3棵树,红实边为树,粗虚为向前边,细虚为回退,黑线为横跨边,从如下的DFS过程可知,原图是弱连通(看成无向图时连通)时,DFS是不连通的.定理6.6.1 强连通图的DFS林是连通的.证明:假设DFS林不连通,则至少有2棵子树T1,T2.设r1,r2是其根,r1r2,T1先于T2得到.由深度优先算法的特点可知,不存在起点在T1,终点在T2的边.故从r1不能到达T2的各结点,故不是强连通的!矛盾,故假设错.,从如下的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是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(v)成立,求Low()有向图分块是lowLink(v)=dfn(v)成立，求LowLink(),确定强连通块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()函数。,rj,ri,v,w,定义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时 LowLink(v)=min(LowLink(v),lowLink(s);,LowLink(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(3)=min(lowlink(3),linklow(4)=3LowLink(5)=dfn(5)=5LowLink(5)=min(lowLink(5),dfn(4)=4 横跨边,LowLink(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与w是否同块。无向图stack是边集,有向图是点集 一旦得到一个块，则将该块的结点从stack中移出。添point数组，若v在stack中则point(v)=1,否则为0。,1.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若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),LowLink(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(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,转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,转3 3.任选，转4 4.标示已查,因mark(3)=1,dfn(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=5,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 转33.因以3为起点边已查,转55.因lowLink(3)=dfn(3)=3故为块！栈顶到3所有点3,4,5,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,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=7,4.标示已查,因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),转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.任选未查边,转4,4.标示已查,因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.任选未查边,转44.标示已查,因mark(7)=1,dfn(7),转44.标示已查,因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.,4.标示已查,因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(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为起点边全查完,转5,3.因以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是块point(2)=0,又因father(2)=10,不是根,可回溯.lowLink(1)=min(LowLink(1),lowLink(2)=1 v=1转3,3.任选未查边,转44.标示已查.因mark(11)=0,故i=11,dfn(11)=11,mark(11)=1,fath(11)=1,lowLink(11)=11,point(11)=1,stack=1,11,v=11,转3.3.任选未查边,转44.标示已查.因mark(12)=0,故i=12,dfn(12)=12,mark(12)=1,fath(12)=11,lowLink(12)=12,point(12)=1,stack=1,11,12,v=12,转3.3.任选未查边,转44.标示已查因mark(1)=1,dfn(1)dfn(12),point(1)=1,故lowLink(12)=min(LowLink(12),dfn(1)=1(反向边),转33.因以12为始点边已查完,转5,3.因以12为始点边已查完,转55因lowLink(12)dfn(12)故不是块.又因father(12)=11 0,不是根,可回溯.lowLink(11)=min(LowLink(11),lowLink(12)=1 v=11转33.任选未查边,转44.标示已查.因mark(13)=0,故i=13,dfn(13)=13,mark(13)=1,fath(13)=11,lowLink(13)=13,point(13)=1,stack=1,11,12,13,v=12,转3.3.任选未查边,转44.标示已查因mark(12)=1,dfn(12)dfn(13),point(12)=1,故lowLink(13)=min(LowLink(13),dfn(12)=12(横跨边),转33.因以13为始点边已查完,转5,3.因以13为始点边已查完,转55.因lowLink(13)dfn(13)故不是块.又因father(13)=11 0,不是根,可回溯.lowLink(11)=min(LowLink(11),lowLink(13)=1 v=11转33.因以11为始点边已查完,转55.因lowLink(11)dfn(11)故不是块.又因father(11)=1 0,不是根,可回溯.lowLink(1)=min(LowLink(1),lowLink(11)=1 v=1转33.因以1为始点边已查完,转55.因lowLink(1)=dfn(1)故是块.栈顶到1的1,11,12,13是块Point(1)=point(11)point(10)=0,stack=又因father(1)=0,是根,转66.因所有点mark(x)=1故结束!,