深度優(yōu)先搜索
在圖中搜索的一般過程為：
- 記錄當(dāng)前結(jié)點(diǎn)被發(fā)現(xiàn)的時(shí)間(discovery time)
- 遍歷訪問未被訪問過的子節(jié)點(diǎn)澜汤，并依次進(jìn)行DFS
- 記錄當(dāng)前節(jié)點(diǎn)的結(jié)束時(shí)間(finish time)
- 遍歷完成
節(jié)點(diǎn)被發(fā)現(xiàn)時(shí)間和遍歷完成時(shí)間都是圖的重要參數(shù)傻丝。
當(dāng)v是u的后代，u.d<v.d<v.f<u.f。
邊的分類
- 樹邊 - 前驅(qū)森林中的邊，如果v是因?yàn)樗惴▽?duì)邊(u,v)的搜索首先發(fā)現(xiàn)v，那么(u,v)是一條樹邊
- 前向邊 - 指向深度優(yōu)先樹中一個(gè)后代節(jié)點(diǎn)的邊
- 后向邊 - 指向深度優(yōu)先樹中一個(gè)祖先節(jié)點(diǎn)的邊
- 橫向邊 - 其它所有邊
將沒有遍歷過的點(diǎn)標(biāo)記為白色撤蟆，正在遍歷中的點(diǎn)標(biāo)記為灰色，后代遍歷完成的點(diǎn)標(biāo)記為黑色堂污，那么在對(duì)節(jié)點(diǎn)u的后代v遍歷過程中生成的邊(u,v)家肯，有
- v為白色，那么邊為樹邊
- v為灰色盟猖，邊為后向邊
- v為黑色讨衣，邊為前向邊或橫向邊
在對(duì)無向圖的深度優(yōu)先遍歷中，從來不會(huì)出現(xiàn)橫向邊和前向邊式镐。
拓?fù)渑判?/h1>
以有向無環(huán)圖未被訪問過的點(diǎn)開始反镇，對(duì)其進(jìn)行DFS。節(jié)點(diǎn)拓?fù)湫驗(yàn)樗耐瓿蓵r(shí)間倒序娘汞。拓?fù)湫虿晃ㄒ淮醪瑁cDFS時(shí)遍歷后繼節(jié)點(diǎn)的順序有關(guān)。對(duì)于有環(huán)的圖你弦，拓?fù)湫驘o法確定惊豺。
強(qiáng)連通分量(Strongly Connected Components)
- 有向圖中可以兩兩互達(dá)的極大點(diǎn)集點(diǎn)構(gòu)成一個(gè)強(qiáng)連通分量
- 將強(qiáng)連通分量縮點(diǎn)后的圖稱為分量圖，分量圖一定是有向無環(huán)圖
Kosaraju算法
用該算法對(duì)有向圖G求解SCC的過程可以表述如下
- 利用DFS(G)計(jì)算出所有節(jié)點(diǎn)的結(jié)束時(shí)間(finish time)
- 構(gòu)建G的轉(zhuǎn)置
- DFS(G轉(zhuǎn)置)禽作，但是DFS的主循環(huán)中尸昧，對(duì)節(jié)點(diǎn)以結(jié)束時(shí)間遞減序訪問
- 上一步中生成的DFS森林每棵樹即為一個(gè)SCC
以下內(nèi)容來自書后習(xí)題
半連通性判別
22.5-7 有向圖G=(V,E)中，如果對(duì)于所有的節(jié)點(diǎn)對(duì)u领迈、v彻磁，從u到v的路徑和從v到u的路徑至少存在一條，那么稱G為半連通的(semiconnected)狸捅。給出一個(gè)有效的算法判別有向圖G是否為半連通圖衷蜓，并分析時(shí)間復(fù)雜度。
引理 有向無環(huán)圖G尘喝，如果是半連通的磁浇，則總是存在一條路徑，經(jīng)過G的所有點(diǎn)朽褪。
- 充分性 若上述路徑存在置吓，顯然任意兩節(jié)點(diǎn)都有至少一條路徑連通。
- 必要性 對(duì)G進(jìn)行拓?fù)渑判虻拊玫焦?jié)點(diǎn)序列衍锚。考察序列中任意兩相鄰節(jié)點(diǎn)u和v嗤堰，根據(jù)半連通的性質(zhì)戴质，u和v之間存在路徑將它們連起來。因?yàn)閡和v是拓?fù)湫蛑邢噜弮晒?jié)點(diǎn)，若u告匠、v不直接相連戈抄，那么可以證明u和v在拓?fù)湫蛑胁幌噜彛芎笞āＫ評(píng)划鸽、v必須直接相連。現(xiàn)在討論u戚哎、v之間邊的方向裸诽，如果是(v,u)的話，違背拓?fù)渑判虻囊?guī)定型凳，不可能存在崭捍，于是所有邊的方向都相同。所以在該拓?fù)湫蛑兴邢噜弮牲c(diǎn)都有一條邊將它們連接起來啰脚，這些邊構(gòu)成了上述路徑殷蛇。
定理 有向圖G對(duì)應(yīng)的分量圖如果是半連通的，則G也是半連通的橄浓。
證明 由于G對(duì)應(yīng)的分量圖半連通粒梦，所以存在一條路徑經(jīng)過所有的分量。由于分量?jī)?nèi)部任意兩點(diǎn)是互達(dá)的荸实，所以G中存在一條路徑經(jīng)過所有點(diǎn)匀们。于是任意兩點(diǎn)u、v准给，從u到v的路徑和從v到u的路徑至少存在一條泄朴，故G是半連通圖。
算法SEMICONNECTED-GRAPH(G)描述如下
- DFS查找G的所有SCC并縮點(diǎn)露氮，構(gòu)建分量圖G1
- 對(duì)G1進(jìn)行拓?fù)渑判蜃婊遥玫近c(diǎn)列
- 判斷2中點(diǎn)列是否滿足相鄰直接相連的性質(zhì)，若滿足則G為半連通圖
時(shí)間復(fù)雜度分析 第1畔规、2步時(shí)間復(fù)雜度均是O(V+E)局扶，3的時(shí)間復(fù)雜度是O(V)，故總的時(shí)間復(fù)雜度為O(V+E)叁扫。
銜接點(diǎn)三妈、橋和雙連通分量
此處討論的為“邊雙連通分量”。
22-2 設(shè)G=(V,E)是一個(gè)無向圖莫绣，G的銜接點(diǎn)是G中的一個(gè)節(jié)點(diǎn)畴蒲，刪除該節(jié)點(diǎn)將導(dǎo)致圖不連通。橋是一條邊对室，刪除該條邊會(huì)使圖不連通模燥。雙連通分量是指一個(gè)最大邊集合狞玛，里面任意兩條邊都處于同一簡(jiǎn)單環(huán)路中。
我們可以用深度優(yōu)先搜索算法來進(jìn)行這三種元素的判別涧窒。設(shè)G_pi=(V,E_pi)是G的深度優(yōu)先樹。定義v.low=min{v.d,w.d:u是v的一個(gè)后代且(u,w)是一條后向邊}
如何在O(E)時(shí)間內(nèi)計(jì)算出u.low
對(duì)G進(jìn)行DFS锭亏，當(dāng)訪問到節(jié)點(diǎn)u時(shí)
- 初始化u.low=u.d
- 查找u的相鄰節(jié)點(diǎn)纠吴，設(shè)其為v
- 若v是未訪問過的節(jié)點(diǎn)，則對(duì)v進(jìn)行DFS慧瘤，并用求得的v.low更新u.low
- 若v被訪問過且非u戴已，則u.low=min{u.low,v.d}
算法的關(guān)鍵在于——u.low是可以傳遞的，具體地說锅减，就是在G的某個(gè)點(diǎn)集中糖儡，節(jié)點(diǎn)v具有最小的low值的話，它在這個(gè)點(diǎn)集中所有的祖先節(jié)點(diǎn)都會(huì)具有同樣的low值怔匣。通過這種算法握联，最小low值會(huì)被不斷上傳，從而實(shí)現(xiàn)求解每瞒。
如何在O(E)時(shí)間內(nèi)計(jì)算出銜接點(diǎn)
對(duì)G進(jìn)行DFS并更新low值金闽，再檢查所有點(diǎn)。對(duì)于點(diǎn)u剿骨，若存在相鄰點(diǎn)v代芜，使得u.low!=v.low，則u為銜接點(diǎn)浓利。
如何在O(E)時(shí)間內(nèi)計(jì)算出橋
對(duì)G進(jìn)行DFS并更新low值挤庇，再檢查所有邊。對(duì)于邊(u,v)贷掖，當(dāng)u.d<v.low時(shí)嫡秕，(u,v)是橋。（u.d>v.low也可以）
如何在O(E)時(shí)間內(nèi)對(duì)G中所有的邊做上e.bcc的正整數(shù)標(biāo)記苹威，其中e.bcc=f.bcc當(dāng)且僅當(dāng)e和f處于同一雙連通分量中
一種可行的方法：
- 對(duì)G進(jìn)行橋的求解淘菩，并標(biāo)記不同的bcc
- 再次進(jìn)行DFS，只經(jīng)過非橋邊屠升，且將非橋邊標(biāo)記為同一bcc
可以肯定的是潮改，邊雙連通分量不可能通過公共點(diǎn)連接，所以每次DFS時(shí)訪問的節(jié)點(diǎn)一定屬于同一邊雙連通分量腹暖。
