第二讲 图的分解

第二讲图的分解图31265478CostaRicaNicaraguaElSalvadorMexicoPanamaHondurasGuatemalaBelize•图是由节点和边来说明的节点=国家边=相邻国家•图染色问题：用尽可能少的颜色染节点，使得相同颜色节点间不存在边。制图师的问题考试安排问题考试安排者的问题期末考试安排：-用尽可能少的时间空档；-如果有学生考二门课，则不能安排它们在同一时间空档。这也是个图着色问题!节点=考试边=某个学生有节点表示的二门考试颜色=时间空档31254图的定义图是G=(V,E)，其中V:节点集E:边集31254V={1,2,3,4,5}E={{1,2},{2,3},{3,4},{2,5},{4,5}}无向边:对称关系例如Worldwideweb节点URL边(u,v)u指向v亿万个节点和边!有向图(x,y):从x到y的边图在计算机中如何存储？31254邻接矩阵表示法VxV矩阵AA(i,j)=1如果(i,j)在E0否则如果G是无向图，则矩阵是对称的0101010100010101010100010123452135243524邻接表表示法每个节点,对应一个表无向图的深度优先搜索egdbafc可能遇到的困难不要在圈中转不要漏掉任何节点常见方法用粉笔标示访问过的节点标记线–引导回到起始点计算机模拟用布尔变量表示每个节点是否已访问堆栈从一个给定的节点，图的那些部分可达?采用邻接表表示，这就象在迷宫中行走...hij一个探索过程abfcdegprocedureexplore(G,v)input:graphG=(V,E);nodevinVoutput:visited[u]issettotrueforallureachablefromvvisited[v]=trueprevisit(v)foreachedge(v,u)inE:ifnotvisited[u]:explore(G,u)postvisit(v)explore(G,a):hijegdbafc“探索”过程可行吗？procedureexplore(G,v)visited[v]=trueforeachedge(v,u)inE:ifnotvisited[u]:explore(G,u)它会停吗?对任一节点u,explore(G,u)最多调用一次;其后visited[u]被设置。.它访问从v可达每个节点吗?假设它漏掉从v可达节点u，我们可推出一个矛盾。任选一条从v到u的路径,设z是路径上最后被访问的节点。那么w会在explore(G,z)中被错过，这是个矛盾.uvzw无向图连通性egdbafchijabfcdeg一个无向图是连通的如果任意节点对之间都存在一条路径。proceduredfs(G)forallvinV:visited[v]=falseforallvinV:ifnotvisited[v]:explore(G,v)此图有2个连通部分explore(G,v)返回包含v的连通部分。要探索图的其余部分，在其余地方重新调用explore().DFS分解该无向图成二个连通部分!explore(G,a)explore(G,h)hij运行时间分析procedureexplore(G,v)visited[v]=trueforeachedge(v,u)inE:ifnotvisited[u]:explore(G,u)proceduredfs(G)forallvinV:visited[v]=falseforallvinV:ifnotvisited[v]:explore(G,v)dfs(G)要花多少时间?对每个节点v，explore(G,v)只调用一次。在调用期间，所花时间=O(1)+内部循环所花时间因此，全部时间=O(|V|)+全部内部循化所花时间在内部循环中:每条边被检查二次，每个端点一次。因此O(|E|).全部时间:O(|V|+|E|),与图的大小成线性关系。前、后访问数egdbafchijabfcdegprocedureexplore(G,v)visited[v]=trueprevisit(v)foreachedge(v,u)inE:ifnotvisited[u]:explore(G,u)postvisit(v)proceduredfs(G)forallvinV:visited[v]=falseforallvinV:ifnotvisited[v]:explore(G,v)procedureprevisit(v)pre[v]=clock++procedurepostvisit(v)post[v]=clock++要记录的额外信息:pre[u]=最初访问时间post[u]=最后离开时间hij无向图DFS总结egdbafchijabfcdeg1,142,93,46,75,810,1311,12区间[pre[u],post[u]]或嵌套或不相交。为什么？[pre[u],post[u]]是节点u在栈中的时间。术语:DFS搜索森林是指由二个DFS搜索树组成的森林。树边是指由DFS走过的边回边没走过的边（引导到一个已访问的节点）hij15,2016,1917,18有向图的DFS:例子abcdefghprocedureexplore(G,v)visited[v]=trueprevisit(v)foreachedge(v,u)inE:ifnotvisited[u]:explore(G,u)postvisit(v)proceduredfs(G)forallvinV:visited[v]=falseforallvinV:ifnotvisited[v]:explore(G,v)procedureprevisit(v)pre[v]=clock++procedurepostvisit(v)post[v]=clock++abcdefgh有向图的DFS:术语abcdefgh祖先后代根父母孩子四种类型的边树边DFS森林的组成部分回边引导到一个祖先前向边引导到一个非孩子后代横跨边既不引导到后代也不引导到祖先abcdefgh祖先节点的前/后签名边的类型边(u,v)的前/后准则树边pre[u]pre[v]post[v]post[u]前向边pre[u]pre[v]post[v]post[u]回边pre[v]pre[u]post[u]post[v]横跨边pre[v]post[v]pre[u]post[u]节点u是节点v的祖先当且仅当pre[u]pre[v]post[u]为什么?因为:u是v的一个祖先当且仅当u首先被发现并且v在u的探索中被发现abcdefgh1,162,153,67,144,58,911,1210,13圈有向图中的圈是一条循环路径010...vvvvk断言：一个有向图G有一个圈当且仅当DFS遇到一条回边.()假设DFS遇到一条从节点v到节点u的回边。那么G有个圈，由搜索树中从u到v的路径及边(v,u)构成。()假设G一个圈设是将要探索的这些节点中的第一个；那么其余节点在下面的DFS子树中；（或如果）是条回边。检测图无圈的算法时间是线性的!010...vvvvk无圈图:非循环的.如何区分图是否非循环?iviv),(1iivv),(0vvk0iabcdefgh有向无圈图(dag)对建模层次关系，因果关系，时间依赖关系，…...调度问题：拓扑排序输入:一个dag目标:给每个节点一个编号使得每条边都是从较高编号到较低编号(即满足先后顺序).解决方案:运行DFS并按POST数降序执行任务.断言：在一个dag中，每条边引导到一个较低的post数。证明:只有post[v]post[u]的边(u,v)是回边。一个dag没有回边!任务应按什么顺序执行?如果存在一个圈:没希望!醒来吃早餐淋浴上车打扮哄小孩有向无环图(dag)源是没有进入边的节点.汇点没有出来边的节点.断言：在一个dag中,有最高post数的节点是源，最低post数的节点是汇点.另一个拓扑排序算法:-找一个源,输出-从图中删除它-重复这个过程直到图为空醒来吃早餐淋浴上车打扮哄小孩1,122,73,64,58,119,10有向图的连通性abcgdefhij元图（metagraph）：把每个SCC表示为一个元节点（meta-node）.如果在二个元节点各自节点间有一边，则在二元节点间连一边（方向相同）。abdefhijcg2个源SCC1个汇SCC每个有向图是它的强连通分量构成的DAG.有向图的双重结构:顶层:DAG,非常简单的结构更细内容:窥视元节点内部在有向图中,u和v是连通的如果存在一条从u到v的路径且存在一条从v到u的路径.划分V成强连通分量（SCC）.分解图成强连通分量abcgdefhij性质1:如果程序explore在节点u开始执行,则当所有从u可达的节点都访问后它停止.因此:如果从一个汇SCC开始,我们将确切地识别那个SCC!二个问题:A.如何找一个将肯定在汇SCC中的节点?B.一旦我们识别一个汇SCC,我们如何继续?问题(A):我们总能找到一个肯定在源SCC中的节点!找一个在源SCC中的节点abcgdefhij性质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’中所有节点。因此，post[u]比C’中每个post值大。情形2:DFS首先看见C’。假设DFS首先看见C’中的节点v。那么在探索v时，它将看见C’中所有节点,但C中节点看不见。因此，C’中的每个post值小于C中的任意post值。通过按最大post值降序地排序SCC可得到SCC的拓扑排序.把图分解成强连通分量abcgdefhij性质1:当从u可达的所有节点都访问后，explore(G,u)停止.因此:如果我们从一个汇SCC开始，我们将精确地识别这个SCC!A.如何找一个肯定在汇SCC中的节点?B.一旦我们识别一个汇SCC，接下来我们该如何办?问题(A)我们总能找到一个肯定在源SCC中的节点。逆图GR=将G的每条边倒置。GR和G有相同的SCC。GR中的源SCC=G中的汇SCC因此:在GR上运行DFS，选出post值最大的节点;则该节点在G的一个汇SCC中。问题(B)识别汇SCC,从图中删除.在余下的节点中,GR中post值最大的节点将在G的剩余部分的汇SCC中。强连通算法abcgdefhij1,23,45,209,106,178,157,1612,1311,1418,19GRabcgdefhijGrunDFSonGRforvinV,按GR-post值降序:ifnotvisited[v]:explore(G,v)把已见过的节点作为一个SCC输出从GR排序:c,g,f,j,i,h,d,e,b,a