第二讲 图的分解.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二讲 图的分解,图,图是由节点和边来说明的,节点,=,国家,边,=,相邻国家,图染色,问题,：用尽可能少的颜色染节点，使得相同颜色节点间不存在边。,考试安排问题,期末考试安排：,-,用尽可能少的时间空档；,-,如果有学生考二门课，则不能安排它们在同一时间空档。,这也是个图着色问题,!,节点,=,考试,边,=,某个学生有节点表示的二门考试,颜色,=,时间空档,图的定义,图是,G=(V,E),，其中,V:,节点集,E:,边集,V=1,2,3,4,5,E=1,2,2,3,3,4,2,5,4,5,无向边,:,对称关系,例如,World wide web,节点,URL,边,(,u,v,)u,指向,v,亿万个节点和边,!,有向,图,(,x,y,):,从,x,到,y,的边,图在计算机中如何存储？,邻接矩阵表示法,V x V,矩阵,A,A(i,j,)=1,如果,(,i,j,),在,E,0,否则,如果,G,是无向图，则矩阵是对称,的,邻接表表示法,每个节点,对应一个表,无向图的深度优先搜索,可能遇到的困难,不要在圈中转,不要漏掉任何节点,常见方法,用粉笔标示访问过的节点,标记线,引导回到起始点,计算机模拟,用布尔变量表示每个节点是否已访问,堆栈,从一个给定的节点，图的那些部分可达,?,采用邻接表表示，这就象在迷宫中行走,.,一个探索过程,procedure,explore(G,v,),input:graph G=(V,E);node v in V,output:,visitedu,is set to true,for all u reachable from v,visitedv,=true,previsit,(v,),for each edge(,v,u,)in E:,if not,visitedu,:,explore(G,u,),postvisit,(v,),explore(G,a,):,“探索,”,过程可行吗？,procedure,explore(G,v,),visitedv,=true,for each edge(,v,u,)in E:,if not,visitedu,:,explore(G,u,),它会停吗,?,对任一节点,u,explore(G,u,),最多调用一次,;,其后,visitedu,被设置。,.,它访问从,v,可达每个节点吗,?,假设它漏掉从,v,可达节点,u,，我们可推出一个矛盾。,任选一条从,v,到,u,的路径,设,z,是路径上最后被访问的节点。,那么,w,会在,explore(G,z,),中被错过，这是个矛盾,.,无向图连通性,一个无向图是连通的如果任意节点对之间都存在一条路径。,procedure,dfs(G,),for all v in V:,visitedv,=false,for all v in V:,if not,visitedv,:,explore(G,v,),此图有,2,个连通部分,explore(G,v,),返回包含,v,的连通部分。,要探索图的其余部分，在其余地方重新调用,explore().,DFS,分解该无向图成二个连通部分,!,explore(G,a,),explore(G,h,),运行时间分析,procedure,explore(G,v,),visitedv,=true,for each edge(,v,u,)in E:,if not,visitedu,:,explore(G,u,),procedure,dfs(G,),for all v in V:,visitedv,=false,for all v in V:,if not,visitedv,:,explore(G,v,),dfs(G,),要花多少时间,?,对每个节点,v,，,explore(G,v,),只调用一次。,在调用期间，,所花时间,=O(1)+,内部循环所花时间,因此，全部时间,=,O(,|,V,|,)+,全部内部循化所花时间,在内部循环中,:,每条边被检查二次，,每个端点一次。因此,O(|E|).,全部时间,:O(|V|+|E|),与图的大小成线性关系。,前、后访问数,procedure,explore(G,v,),visitedv,=true,previsit(v,),for each edge(,v,u,)in E:,if not,visitedu,:,explore(G,u,),postvisit(v,),procedure,dfs(G,),for all v in V:,visitedv,=false,for all v in V:,if not,visitedv,:,explore(G,v,),procedure,previsit(v,),prev,=clock+,procedure,postvisit(v,),postv,=clock+,要记录的额外信息,:,preu,=,最初访问时间,postu,=,最后离开时间,无向图,DFS,总结,区间,preu,postu,或嵌套或 不相交。为什么？,preu,postu,是节点,u,在栈中的时间。,术语,:,DFS,搜索森林,是指由二个,DFS,搜索树组成的森林。,树边是指由,DFS,走过的边,回边没走过的边（引导到一个已访问的节点）,有向图的,DFS:,例子,procedure,explore(G,v,),visitedv,=true,previsit(v,),for each edge(,v,u,)in E:,if not,visitedu,:,explore(G,u,),postvisit(v,),procedure,dfs(G,),for all v in V:,visitedv,=false,for all v in V:,if not,visitedv,:,explore(G,v,),procedure,previsit(v,),prev,=clock+,procedure,postvisit(v,),postv,=clock+,有向图的,DFS:,术语,祖先,后代,根,父母,孩子,四种类型的边,树边,DFS,森林的组成部分,回边,引导到一个祖先,前向边,引导到一个非孩子后代,横跨边,既不引导到后代也不引导,到祖先,祖先节点的前,/,后签名,边的类型,边,(,u,v,),的前,/,后准则,树边,preu,prev,postv,postu,前向边,preu,prev,postv,postu,回边,prev,preu,postu,postv,横跨边,prev,postv,preu,postu,节点,u,是节点,v,的祖先当且仅当,preu,prev,postu,的边,(,u,v,),是回边。一个,dag,没有回边,!,任务应按什么顺序执行,?,如果存在一个圈,:,没希望,!,有向无环图,(dag),源是没有进入边的节点,.,汇点没有出来边的节点,.,断言：在一个,dag,中,有最高,post,数的节点是源，最低,post,数的节点是汇点,.,另一个拓扑排序算法,:,-,找一个源,输出,-,从图中删除它,-,重复这个过程直到图为空,有向图的连通性,元图,（,metagraph,）：,把每个,SCC,表示为一个元,节点,（,meta-node,）,.,如果在二个元节点各自节点间有一边，则在二元节点间连一边（方向相同）。,2,个源,SCC,1,个汇,SCC,每个有向图是它的强连通分量构成的,DAG.,有向图的双重结构,:,顶层,:DAG,非常简单的结构,更细内容,:,窥视元节点内部,在有向图中,u,和,v,是连通的如果存在一条从,u,到,v,的路径且存在一条从,v,到,u,的路径,.,划分,V,成强连通分量（,SCC,）,.,分解图成强连通分量,性质,1:,如果程序,explore,在节点,u,开始执行,则当所有从,u,可达的节点都访问后它停止,.,因此,:,如果从一个汇,SCC,开始,我们将确切地识别那个,SCC!,二个问题,:,A.,如何找一个将肯定在汇,SCC,中的节点,?,B.,一旦我们识别一个汇,SCC,我们如何继续,?,问题,(A):,我们总能找到一个肯定在源,SCC,中的节点,!,找一个在源,SCC,中的节点,性质,2:,在,G,上运行,DFS.,则具有最大,post,值的节点在源,SCC,中,.,性质,3:,如果,C,C,是,SCC,且存在一条从,C,到,C,的边，则,C,中最大,post,值大于,C,中的,post,最大值,.,通过按最大,post,值降序地排序,SCC,可得到,SCC,的拓扑排序,.,找一个在源,SCC,中的节点,性质,3:,如果,C,C,是,SCC,且存在一条从,C,到,C,的边，则,C,中最大,post,值大于,C,中的,post,最大值。,情形,1:DFS,首先看见,C,。,假设,DFS,首先看见,C,中节点,u,。那么在探索,u,时，它将看见,C,中所有节点。因此，,postu,比,C,中每个,post,值大。,情形,2:DFS,首先看见,C,。,假设,DFS,首先看见,C,中的节点,v,。那么在探索,v,时，它将看见,C,中所有节点,但,C,中节点看不见。因此，,C,中的每个,post,值小于,C,中的任意,post,值。,通过按最大,post,值降序地排序,SCC,可得到,SCC,的拓扑排序,.,把图分解成强连通分量,性质,1,:,当从,u,可达的所有节点都访问后，,explore(G,u,),停止,.,因此,:,如果我们从一个汇,SCC,开始，我们将精确地识别这个,SCC!,A.,如何找一个肯定在汇,SCC,中的节点,?,B.,一旦我们识别一个汇,SCC,，接下来我们该如何办,?,问题,(A),我们总能找到一个肯定在,源,SCC,中的节点。,逆图,G,R,=,将,G,的每条边倒置。,G,R,和,G,有相同的,SCC,。,G,R,中的源,SCC=G,中的汇,SCC,因此,:,在,G,R,上运行,DFS,，选出,post,值最大的节点,;,则该节点在,G,的一个汇,SCC,中。,问题,(B),识别汇,SCC,从图中删除,.,在余下的节点中,G,R,中,post,值最大的节点将在,G,的剩余部分的汇,SCC,中。,强连通算法,G,run DFS on G,R,for v in V,按,G,R,-post,值降序,:,if not,visitedv,:,explore(G,v,),把已见过的节点作为一个,SCC,输出,从,G,R,排序,:,c,g,f,j,i,h,d,e,b,a,