第二講圖的分解

第二講圖的分解第1頁(yè)，共24頁(yè)，2023年，2月20日，星期一圖圖是由節(jié)點(diǎn)和邊來(lái)說(shuō)明的

節(jié)點(diǎn)=國(guó)家

邊=相鄰國(guó)家圖染色問(wèn)題：用盡可能少的顏色染節(jié)點(diǎn)，使得相同顏色節(jié)點(diǎn)間不存在邊。第2頁(yè)，共24頁(yè)，2023年，2月20日，星期一考試安排問(wèn)題期末考試安排：-用盡可能少的時(shí)間空檔；-如果有學(xué)生考二門(mén)課，則不能安排它們?cè)谕粫r(shí)間空檔。這也是個(gè)圖著色問(wèn)題!節(jié)點(diǎn)=考試邊=某個(gè)學(xué)生有節(jié)點(diǎn)表示的二門(mén)考試顏色=時(shí)間空檔第3頁(yè)，共24頁(yè)，2023年，2月20日，星期一圖的定義圖是G=(V,E)，其中V:節(jié)點(diǎn)集E:邊集V={1,2,3,4,5}E={{1,2},{2,3},{3,4},{2,5},{4,5}}無(wú)向邊:對(duì)稱關(guān)系例如Worldwideweb節(jié)點(diǎn)URL邊(u,v)u指向v億萬(wàn)個(gè)節(jié)點(diǎn)和邊!有向圖(x,y):從

x到y(tǒng)的邊第4頁(yè)，共24頁(yè)，2023年，2月20日，星期一圖在計(jì)算機(jī)中如何存儲(chǔ)？鄰接矩陣表示法VxV矩陣AA(i,j)=1如果(i,j)在E0否則如果G是無(wú)向圖，則矩陣是對(duì)稱的鄰接表表示法每個(gè)節(jié)點(diǎn),對(duì)應(yīng)一個(gè)表第5頁(yè)，共24頁(yè)，2023年，2月20日，星期一無(wú)向圖的深度優(yōu)先搜索可能遇到的困難不要在圈中轉(zhuǎn)不要漏掉任何節(jié)點(diǎn)常見(jiàn)方法用粉筆標(biāo)示訪問(wèn)過(guò)的節(jié)點(diǎn)標(biāo)記線–引導(dǎo)回到起始點(diǎn)計(jì)算機(jī)模擬用布爾變量表示每個(gè)節(jié)點(diǎn)是否已訪問(wèn)堆棧從一個(gè)給定的節(jié)點(diǎn)，圖的那些部分可達(dá)?采用鄰接表表示，這就象在迷宮中行走...第6頁(yè)，共24頁(yè)，2023年，2月20日，星期一一個(gè)探索過(guò)程procedureexplore(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):第7頁(yè)，共24頁(yè)，2023年，2月20日，星期一“探索”過(guò)程可行嗎？procedureexplore(G,v)visited[v]=trueforeachedge(v,u)inE:ifnotvisited[u]:explore(G,u)它會(huì)停嗎?對(duì)任一節(jié)點(diǎn)u,explore(G,u)最多調(diào)用一次;其后visited[u]被設(shè)置。.它訪問(wèn)從v可達(dá)每個(gè)節(jié)點(diǎn)嗎?假設(shè)它漏掉從v可達(dá)節(jié)點(diǎn)u，我們可推出一個(gè)矛盾。任選一條從v到u的路徑,設(shè)z是路徑上最后被訪問(wèn)的節(jié)點(diǎn)。那么w會(huì)在explore(G,z)中被錯(cuò)過(guò)，這是個(gè)矛盾.第8頁(yè)，共24頁(yè)，2023年，2月20日，星期一無(wú)向圖連通性一個(gè)無(wú)向圖是連通的如果任意節(jié)點(diǎn)對(duì)之間都存在一條路徑。proceduredfs(G)forallvinV:visited[v]=falseforallvinV:ifnotvisited[v]:explore(G,v)此圖有2個(gè)連通部分explore(G,v)返回包含v的連通部分。要探索圖的其余部分，在其余地方重新調(diào)用explore().DFS分解該無(wú)向圖成二個(gè)連通部分!explore(G,a)explore(G,h)第9頁(yè)，共24頁(yè)，2023年，2月20日，星期一運(yùn)行時(shí)間分析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)要花多少時(shí)間?對(duì)每個(gè)節(jié)點(diǎn)v，explore(G,v)只調(diào)用一次。在調(diào)用期間，所花時(shí)間=O(1)+內(nèi)部循環(huán)所花時(shí)間因此，全部時(shí)間=O(|V|)+全部?jī)?nèi)部循化所花時(shí)間在內(nèi)部循環(huán)中:每條邊被檢查二次，每個(gè)端點(diǎn)一次。因此O(|E|).全部時(shí)間:O(|V|+|E|),與圖的大小成線性關(guān)系。第10頁(yè)，共24頁(yè)，2023年，2月20日，星期一前、后訪問(wèn)數(shù)procedureexplore(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]=最初訪問(wèn)時(shí)間post[u]=最后離開(kāi)時(shí)間第11頁(yè)，共24頁(yè)，2023年，2月20日，星期一無(wú)向圖DFS總結(jié)區(qū)間[pre[u],post[u]]或嵌套或不相交。為什么？[pre[u],post[u]]是節(jié)點(diǎn)u在棧中的時(shí)間。術(shù)語(yǔ):DFS搜索森林是指由二個(gè)DFS搜索樹(shù)組成的森林。樹(shù)邊是指由DFS走過(guò)的邊回邊沒(méi)走過(guò)的邊（引導(dǎo)到一個(gè)已訪問(wèn)的節(jié)點(diǎn)）第12頁(yè)，共24頁(yè)，2023年，2月20日，星期一有向圖的DFS:例子procedureexplore(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++第13頁(yè)，共24頁(yè)，2023年，2月20日，星期一有向圖的DFS:術(shù)語(yǔ)祖先

后代

根

父母

孩子

四種類(lèi)型的邊樹(shù)邊DFS森林的組成部分回邊引導(dǎo)到一個(gè)祖先前向邊引導(dǎo)到一個(gè)非孩子后代橫跨邊既不引導(dǎo)到后代也不引導(dǎo)到祖先第14頁(yè)，共24頁(yè)，2023年，2月20日，星期一祖先節(jié)點(diǎn)的前/后簽名邊的類(lèi)型邊(u,v)的前/后準(zhǔn)則

樹(shù)邊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]節(jié)點(diǎn)u是節(jié)點(diǎn)v的祖先當(dāng)且僅當(dāng)

pre[u]<pre[v]<post[u]為什么?因?yàn)?u是v的一個(gè)祖先當(dāng)且僅當(dāng)u首先被發(fā)現(xiàn)并且v在u的探索中被發(fā)現(xiàn)第15頁(yè)，共24頁(yè)，2023年，2月20日，星期一圈有向圖中的圈是一條循環(huán)路徑斷言：一個(gè)有向圖G有一個(gè)圈當(dāng)且僅當(dāng)DFS遇到一條回邊.()假設(shè)DFS遇到一條從節(jié)點(diǎn)v到節(jié)點(diǎn)u的回邊。那么G有個(gè)圈，由搜索樹(shù)中從u到v的路徑及邊(v,u)構(gòu)成。()假設(shè)G一個(gè)圈設(shè)是將要探索的這些節(jié)點(diǎn)中的第一個(gè)；那么其余節(jié)點(diǎn)在下面的DFS子樹(shù)中；（或如果）是條回邊。檢測(cè)圖無(wú)圈的算法時(shí)間是線性的!

無(wú)圈圖:非循環(huán)的.如何區(qū)分圖是否非循環(huán)?第16頁(yè)，共24頁(yè)，2023年，2月20日，星期一有向無(wú)圈圖(dag)對(duì)建模層次關(guān)系，因果關(guān)系，時(shí)間依賴關(guān)系，…...調(diào)度問(wèn)題：拓?fù)渑判蜉斎?一個(gè)dag目標(biāo):給每個(gè)節(jié)點(diǎn)一個(gè)編號(hào)使得每條邊都是從較高編號(hào)到較低編號(hào)(即滿足先后順序).解決方案:運(yùn)行DFS并按POST數(shù)降序執(zhí)行任務(wù).斷言：在一個(gè)dag中，每條邊引導(dǎo)到一個(gè)較低的post數(shù)。證明:只有post[v]>post[u]的邊(u,v)是回邊。一個(gè)dag沒(méi)有回邊!任務(wù)應(yīng)按什么順序執(zhí)行?如果存在一個(gè)圈:沒(méi)希望!第17頁(yè)，共24頁(yè)，2023年，2月20日，星期一有向無(wú)環(huán)圖(dag)源是沒(méi)有進(jìn)入邊的節(jié)點(diǎn).匯點(diǎn)沒(méi)有出來(lái)邊的節(jié)點(diǎn).斷言：在一個(gè)dag中,有最高post數(shù)的節(jié)點(diǎn)是源，最低post數(shù)的節(jié)點(diǎn)是匯點(diǎn).另一個(gè)拓?fù)渑判蛩惴?-找一個(gè)源,輸出-從圖中刪除它-重復(fù)這個(gè)過(guò)程直到圖為空第18頁(yè)，共24頁(yè)，2023年，2月20日，星期一有向圖的連通性元圖（metagraph）：把每個(gè)SCC表示為一個(gè)元節(jié)點(diǎn)（meta-node）.如果在二個(gè)元節(jié)點(diǎn)各自節(jié)點(diǎn)間有一邊，則在二元節(jié)點(diǎn)間連一邊（方向相同）。2個(gè)源SCC1個(gè)匯SCC每個(gè)有向圖是它的強(qiáng)連通分量構(gòu)成的DAG.有向圖的雙重結(jié)構(gòu):頂層:DAG,非常簡(jiǎn)單的結(jié)構(gòu)更細(xì)內(nèi)容:窺視元節(jié)點(diǎn)內(nèi)部在有向圖中,u和v是連通的如果存在一條從u到v的路徑且存在一條從v到u的路徑.劃分V成強(qiáng)連通分量（SCC）.第19頁(yè)，共24頁(yè)，2023年，2月20日，星期一分解圖成強(qiáng)連通分量性質(zhì)1:如果程序explore在節(jié)點(diǎn)u開(kāi)始執(zhí)行,則當(dāng)所有從u可達(dá)的節(jié)點(diǎn)都訪問(wèn)后它停止.因此:如果從一個(gè)匯SCC開(kāi)始,我們將確切地識(shí)別那個(gè)SCC!二個(gè)問(wèn)題:A.如何找一個(gè)將肯定在匯SCC中的節(jié)點(diǎn)?B.一旦我們識(shí)別一個(gè)匯SCC,我們?nèi)绾卫^續(xù)?問(wèn)題(A):我們總能找到一個(gè)肯定在源SCC中的節(jié)點(diǎn)!第20頁(yè)，共24頁(yè)，2023年，2月20日，星期一找一個(gè)在源SCC中的節(jié)點(diǎn)性質(zhì)2:在G上運(yùn)行DFS.則具有最大post值的節(jié)點(diǎn)在源SCC中.性質(zhì)3:如果C,C’是SCC且存在一條從C到C’的邊，則C中最大post值大于C’中的post最大值.通過(guò)按最大post值降序地排序SCC可得到SCC的拓?fù)渑判?第21頁(yè)，共24頁(yè)，2023年，2月20日，星期一找一個(gè)在源SCC中的節(jié)點(diǎn)性質(zhì)3:如果C,C’是SCC且存在一條從C到C’的邊，則C中最大post值大于C’中的post最大值。情形1:DFS首先看見(jiàn)C。假設(shè)DFS首先看見(jiàn)C中節(jié)點(diǎn)u。那么在探索u時(shí)，它將看見(jiàn)C’中所有節(jié)點(diǎn)。因此，post[u]比C’中每個(gè)post值大。

情形2:DFS首先看見(jiàn)C’。假設(shè)DFS首先看見(jiàn)C’中的節(jié)點(diǎn)v。那么在探索v時(shí)，它將看見(jiàn)C’中所有節(jié)點(diǎn),但C中節(jié)點(diǎn)看不見(jiàn)。因此，C’中的每個(gè)post值小于C中的任意post值。通過(guò)按最大post值降序地排序SCC可得到SCC的拓?fù)渑判?第22頁(yè)，共24頁(yè)，2023年，2月20日，星期一把圖