第二講圖的分解

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

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

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

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

后代

根

父母

孩子

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

樹邊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頁，共24頁，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è)圈，由搜索樹中從u到v的路徑及邊(v,u)構(gòu)成。()假設(shè)G一個(gè)圈設(shè)是將要探索的這些節(jié)點(diǎn)中的第一個(gè)；那么其余節(jié)點(diǎn)在下面的DFS子樹中；（或如果）是條回邊。檢測圖無圈的算法時(shí)間是線性的!

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

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