編程教程

　　 編程問答　 ACM與藍(lán)橋杯競(jìng)賽入門　 C語言教程　 C++教程　 數(shù)據(jù)結(jié)構(gòu)教程　 Python教程　 JAVA教程　 編譯器教程　 C語言函數(shù)庫(kù)　 更多教程

圖文解析圖論DFS（深度優(yōu)先搜索）

130425 閱讀 0 評(píng)論 0 點(diǎn)贊

DFS 全稱是 Depth First Search，中文名是深度優(yōu)先搜索，是一種用于遍歷或搜索樹或圖的算法。所謂深度優(yōu)先，就是說每次都嘗試向更深的節(jié)點(diǎn)走。

一、圖搜索Graph Search的分類

（1）BFS廣度優(yōu)先(寬搜)

（2）DFS深度優(yōu)先(深搜)

二、深度優(yōu)先搜索DFS

（1）深度優(yōu)先遍歷DFS, 這個(gè)策略其實(shí)是非常stupid or simple的，比BSF要簡(jiǎn)單的多

（2）同樣，我們可以通過一個(gè)故事來開始

● 在古希臘神話中, Ariadne是Crete的國(guó)王Minos的公主，她給忒修斯(Theseus)一個(gè)線團(tuán)使得忒修斯成功進(jìn)入迷宮殺死牛頭怪獸，但事后忒修斯拋棄了她，這是一個(gè)有道德意義的故事又或者存在不同的版本, 但不是我們的研究的對(duì)象。

● 假如你是一位探險(xiǎn)家，要降落在一片未知的迷宮做路線探測(cè)，比如降落在一個(gè)地點(diǎn)(某一點(diǎn))，你要知道這個(gè)點(diǎn)有幾條邊(方向)到達(dá)潛在的拐點(diǎn)，在任何一個(gè)點(diǎn)你都應(yīng)該知道，當(dāng)然可以做一個(gè)標(biāo)記，比如撒上一點(diǎn)熒光劑(任何實(shí)用東西都可)，標(biāo)記是用來標(biāo)識(shí)出自己走過的地方，接下來的任務(wù)就是要把該區(qū)域可達(dá)路徑畫出來，不失一般性，我們先畫一個(gè)未知的路線圖，我們隨便畫一幅圖，如下圖

深度優(yōu)先搜索DFS

● 我們假設(shè)一開始自己未知路線，這個(gè)路線圖是上帝視角，人類未知(灰色)，只能一點(diǎn)點(diǎn)探索，我們可以把上帝視角下的所有拐點(diǎn)標(biāo)記為：A,B,…H，以備后續(xù)的說明使用，假設(shè)我們的降落地點(diǎn)是紅色的A點(diǎn)，一開始就通向2個(gè)方向，不同于BFS，DFS不能多向走，只能選擇一個(gè)方向，不失一般性，我們可以選擇向下去的一條(綠邊)，如下圖4所示，持續(xù)向下走，會(huì)抵達(dá)一個(gè)拐點(diǎn)，藍(lán)色點(diǎn)，如圖5

● 接下來你會(huì)發(fā)現(xiàn)又出現(xiàn)了3條可走的路線，你可以繼續(xù)任意選擇一個(gè)方向，如下圖6所示

● 繼續(xù)往前走，每走到一個(gè)拐點(diǎn)，就進(jìn)行一次標(biāo)記(比如灑下熒光劑)，你會(huì)發(fā)現(xiàn)這個(gè)過程有點(diǎn)stupid

● 簡(jiǎn)單來說，就一條路跑到黑，基于這個(gè)策略其實(shí)是非常美妙的，可以解決很多算法解決不了的問題

● 這時(shí)候，你已經(jīng)走到如圖9的位置了，你會(huì)發(fā)現(xiàn)似乎有一條邊可以過去，但是走過去之后發(fā)現(xiàn)了自己灑下的標(biāo)記

● 你會(huì)知道，這個(gè)方向通往的地方，你曾經(jīng)訪問過，這時(shí)候這條邊可以做一個(gè)特別的記號(hào)，就是所謂的跨邊，如圖10所示

● 按照慣例，我們?cè)L問過的這些綠色的邊，叫做TREE EDGE, 而灰色的跨邊叫做CROSS(因?yàn)闀?huì)構(gòu)成環(huán)路)

● 當(dāng)我們發(fā)現(xiàn)走進(jìn)了跨邊之后，就要進(jìn)行回退，因?yàn)榫G色的邊構(gòu)成的是一棵樹，而樹中的任意兩個(gè)點(diǎn)之間有唯一的通路，所以回退的方向是唯一的，就是逐個(gè)找到自己的parent

● 回退到B點(diǎn)之后發(fā)現(xiàn)有2條可選的路，我們很快會(huì)發(fā)現(xiàn)其中有一條路存在標(biāo)記(CROSS邊)

● 于是就剩下最后一個(gè)方向了，如下圖11所示，繼續(xù)往前走，到達(dá)拐點(diǎn)，如圖12所示，緊接著發(fā)現(xiàn)還有3條可選的路

● 繼續(xù)按著以往的策略任選一條，如下圖13，14，15，到達(dá)圖16的時(shí)候，又會(huì)標(biāo)記一條CROSS邊，如圖17

● 繼續(xù)做回退，當(dāng)?shù)竭_(dá)E點(diǎn)的時(shí)候，發(fā)現(xiàn)又可以往前走，最終到達(dá)一個(gè)死胡同，如圖19所示，這樣只能繼續(xù)回退一直到初始紅點(diǎn)A

● 然后對(duì)新發(fā)現(xiàn)的CROSS邊進(jìn)行標(biāo)記，如圖20，到這個(gè)時(shí)候，整個(gè)遍歷完成

三、算法實(shí)現(xiàn)框架

template <typename Tv, typename Te> // 頂點(diǎn)類型、邊類型

void Graph<Tv, Te>:: DFS(int v, int & clock) {
    // v是起點(diǎn)，clock是計(jì)時(shí)器，dTime為每個(gè)點(diǎn)都加上時(shí)間戳
    dTime(v) = ++clock;
    status(v) = DISCOVERED; // 發(fā)現(xiàn)當(dāng)前頂點(diǎn)v
    // 考察v的每一鄰居u，枚舉所有的鄰居，這里的鄰居都是當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
    for (int u = firstNbr(v); -1 < u; u = nextNbr(v,u)) {
        // 視u的狀態(tài)，分別處理
        switch(status(u)) {
            case UNDISCOVERED: // u 尚未發(fā)現(xiàn)，意味著支撐樹可在此拓展 (類比BFS的初始植被狀態(tài))
                type(v, u) = TREE; // 樹枝向前邁進(jìn)
                parent(u) = v; // 從v到孩子u之間的關(guān)系
                DFS(u, clock); // 新的起點(diǎn)，開始遞歸，向孩子節(jié)點(diǎn)進(jìn)發(fā)，貪心處理
                break;
            case DISCOVERED: // u 已被發(fā)現(xiàn)但尚未訪問完畢，應(yīng)屬被后代指向的祖先 (類比BFS的燃燒狀態(tài))
                type(v, u) = BACKWARD; // 這是一條回邊，進(jìn)行標(biāo)記處理
                break;
            default: // u已訪問完畢(VISITED, 有向圖)，則視承襲關(guān)系分為前向邊或跨邊 (類比BFS的灰燼狀態(tài))
                // 通過時(shí)間戳來判斷是向前邊還是跨邊
                type(v,u) = dTime(v) < dTime(u) ? FORWARD : CROSS;
                break;
        }
    }
    status(v) = VISITED; // 處理完所有孩子節(jié)點(diǎn)之后，標(biāo)記自己為已訪問
    fTime(v) = ++clock; // 至此，當(dāng)前頂點(diǎn)v方告訪問完畢，fTime是指結(jié)束時(shí)間
}

我們可以看到上述算法中有4種邊：TREE、FORWARD、BACKWARD、CROSS, 下面我們會(huì)詳細(xì)來說明

四、DFS算法步驟圖解

DFS算法步驟圖解

（1）上面是一個(gè)有向圖, 每一個(gè)節(jié)點(diǎn)都是一個(gè)圓角矩形，不失一般性，我們從a開始

（2）圓角矩形上的每個(gè)點(diǎn)都有左右兩個(gè)空間用于記錄dTime, fTime的數(shù)字

（3）圓角矩形的顏色和狀態(tài)分別對(duì)應(yīng)：綠色(UNDISCOVERED), 鮮紅(最活躍的點(diǎn)), 暗紅(活躍的點(diǎn)), 藍(lán)色(VISITED)

（4）大小寫用于輔助顏色的區(qū)分, 如果可以看清顏色, 可以忽略字母的大小寫, 此處不再過多說明

（5）對(duì)于a來說，作為起點(diǎn), 在第一個(gè)單位時(shí)間內(nèi)會(huì)被點(diǎn)著，從綠色變成鮮紅，a接過控制權(quán)之后，去找到他的鄰居

（6）請(qǐng)注意這時(shí)候，它會(huì)貪心的找鄰居中的一個(gè)優(yōu)先做，不失一般性，在第二個(gè)單位時(shí)間把b點(diǎn)燃

（7）這時(shí)候b變成鮮紅色，a從鮮紅變?yōu)榘导t，立足于b, 真正的鄰居只有c, 這個(gè)時(shí)候在第三個(gè)時(shí)間單位

（8）c被點(diǎn)燃變?yōu)轷r紅，b變?yōu)榘导t，因?yàn)槭怯邢驁D，c點(diǎn)走投無路就會(huì)執(zhí)行代碼中的default，變?yōu)閂ISITED狀態(tài)的藍(lán)色

（9）而且c點(diǎn)的fTime進(jìn)行clock++, 從3變?yōu)?，意味著這個(gè)點(diǎn)從第3個(gè)時(shí)間單位被發(fā)現(xiàn)，但在第4個(gè)時(shí)間單位被耗盡了

（10）這個(gè)時(shí)候程序是遞歸的，在遞歸的意義上它會(huì)做一個(gè)回溯(backtrack)，從c到b, b的顏色從暗紅變?yōu)轷r紅

（11）這時(shí)候b想要找周圍的鄰居，發(fā)現(xiàn)已經(jīng)沒有可找的鄰居了，b點(diǎn)走投無路變?yōu)樗{(lán)色，它的fTime變?yōu)榱?

（12）同理，繼續(xù)進(jìn)行回溯，從b到a，a從暗紅變?yōu)轷r紅，a還有鄰居，如c,f, 如果選擇鄰居c, 那么這時(shí)候就有意思了

（13）當(dāng)前活躍的點(diǎn)a試圖通過一條有向邊去指向死亡狀態(tài)的點(diǎn)c，這種情況在有向圖才會(huì)發(fā)生

（14）如果不是有向圖，而是無向圖，每一條邊都是對(duì)等的，當(dāng)一開始到達(dá)c點(diǎn)的時(shí)候，c不會(huì)變?yōu)樗{(lán)色而是會(huì)去找無向圖中的鄰居, 比如a

（15）所以這是一件不可能的事情，在有向圖中才會(huì)發(fā)生這種奇特的現(xiàn)象：活躍指向死亡, 從a->c這種

（16）按照程序中的設(shè)定，dTime(a) < dTime(c), 這時(shí)候a->c是一條FORWARD的邊，在圖上標(biāo)記為粉紅色的邊

（17）如何理解這個(gè)FORWARD邊，綠色的箭頭都是將來構(gòu)成樹的樹枝，一旦構(gòu)成樹就會(huì)有輩分高低之分

（18）c的備份從圖上看要比a低2層, 就像是爺爺照顧孫子，我們稱之為FORWARD

好的，回到流程中來，標(biāo)記完a->c為FORWARD邊之后，a要繼續(xù)尋找它的鄰居，這里找到了f點(diǎn)

（19）此時(shí), f的dTime為6，f會(huì)試圖在第7個(gè)時(shí)間單位找到g, g會(huì)繼續(xù)尋找它的鄰居：a和c

（20）好的，這個(gè)時(shí)候，故事又來了, a的輩分很高, a是g的祖先，我們稱之為BACKWARD邊(可以理解為孫子照顧爺爺)

（21）打個(gè)比方，當(dāng)Theseus在迷宮漫游的時(shí)候，他把線團(tuán)的一頭記在了迷宮的洞口，在迷宮中的"遍歷"的過程中

（22）手里始終攥著那個(gè)繩子的線團(tuán)，每向前走一步，就把線團(tuán)放一步, 每一次做backtrack, 手就會(huì)收這個(gè)線團(tuán)

（23）因?yàn)槭辗?，繩子忽長(zhǎng)忽短，正是這條繩子，可以讓他原路返回?；氐剿惴ㄖ衼?，每一個(gè)節(jié)點(diǎn)都是輩分明確的

（24）Theseus的線就像是上圖中任意時(shí)刻紅色節(jié)點(diǎn)和它們的連邊，關(guān)于輩分就像是繩子一樣, 末端的點(diǎn)輩分最低

（25）輩分低的到輩分高的方向的邊就叫做BACKWARD邊，用淺藍(lán)色箭頭表示，如g->a

（26）從圖上可以看出，每一次BACKWARD的出現(xiàn)，就會(huì)構(gòu)成一個(gè)環(huán)

（27）所謂的環(huán)，如果在有向圖中是有方向的，如a->f->g->a

（28）而a->b->c并不能構(gòu)成一個(gè)環(huán)，因?yàn)榉较虻脑?，a->c屬于FORWARD邊

（29）這個(gè)時(shí)候，我們可以判斷一個(gè)圖是否是樹，以及找出圖中所有的環(huán)

（30）好的，再次回到流程中來，g會(huì)繼續(xù)尋找它的鄰居，找到了c, 這個(gè)時(shí)候活躍點(diǎn)g試圖連接死亡的點(diǎn)c

（31）這個(gè)情況之前也碰到過，如a試圖連接c, 但不同的是，dTime(g) < dTime(c), 這時(shí)候g->c就是一條CROSS邊

（32）所謂CROSS邊的理解是共同祖先如a點(diǎn)的不同直系分支下的點(diǎn)，g和c不構(gòu)成直系的血緣關(guān)系，可能是叔伯兄弟的關(guān)系

（33）也就是跨越兩個(gè)家族之間的邊就是CROSS邊，這個(gè)算法可以繼續(xù)跑下去，直到最后

五、DFS的一些性質(zhì)

DFS的一些性質(zhì)

（1）DFS是基于一個(gè)非常簡(jiǎn)單策略支撐下的一個(gè)算法，但背后蘊(yùn)含了非常深刻的道理甚至是哲學(xué)思想

（2）注意上圖中左右兩部分，其中右邊又分為上下兩部分，注意圖中箭頭的顏色，DFS有四種邊

（3）粉紅色代表FORWARD，綠色代表TREE，藍(lán)色代表BACKWARD，黃色代表CROSS邊

（4）按照DFS模型，從a點(diǎn)開始會(huì)生成一棵樹, 但是在這個(gè)有向圖中并沒有耗盡所有的點(diǎn)，比如d，e

（5）所以，在有向圖中選擇不同的點(diǎn)作為起點(diǎn)，可能走的過程會(huì)不一樣，而且得到的DFS樹也不一樣

（6）有的時(shí)候是一片森林(多棵樹，比如從a點(diǎn)開始)，有的時(shí)候是一棵樹(比如從d點(diǎn)開始)

（7）DFS出來的結(jié)果更多的時(shí)候出來的是一片森林，我們想從中找出一些不變的性質(zhì)

（8）其中dTime和fTime這對(duì)時(shí)間戳有非常顯著的意義, 通過它們可以把每個(gè)點(diǎn)畫成一個(gè)更長(zhǎng)的一個(gè)矩形

（9）如上圖右邊部分，橫向可以表示程序中clock所走的時(shí)間軸，如上圖1 ~ 14

（10）任何一點(diǎn)，比如a，它是1 ~ 10這個(gè)范圍(dTime是1,fTime是10)，在圖上表示就是跨越1和10的圓角藍(lán)色矩形，如上圖所示

（11）再比如，f是6 ~ 9，同理是一個(gè)跨越6 ~ 9范圍的圓角藍(lán)色矩形, 按照這個(gè)規(guī)則約定，我們畫出了上圖

（12）重點(diǎn)說一下上圖右上部分的d點(diǎn)，它是從11開始的，所以，它的后代也都會(huì)在11以后

（13）我們把藍(lán)色的范圍稱之為該點(diǎn)的活躍期, 從開始到死亡的周期, 從上圖可以看到，任何一個(gè)祖先的活躍期一定覆蓋它所有的后代節(jié)點(diǎn)

（14）比如所a的任意一個(gè)后代節(jié)點(diǎn)，f點(diǎn)的活躍期一定在a點(diǎn)之內(nèi)，這個(gè)關(guān)系是幾何圖形上的關(guān)系，從圖中很容易理解

（15）打個(gè)比方說在DFS這個(gè)舞臺(tái)上，無時(shí)無刻都在上演一出白發(fā)人送黑發(fā)人的劇情，祖先先出生，最后再離開

（16）在所有的非直系的DFS樹中，比如b和f，它們的活躍期永遠(yuǎn)不會(huì)出現(xiàn)重疊，再比如：c和f,g和b

（17）通過這個(gè)特點(diǎn)，方便我們判斷任意兩點(diǎn)之間是否直系的血緣關(guān)系

（18）比較活躍期這個(gè)方法，只需要一次比較，也就是O(1)的時(shí)間，如果按照回溯的方式，顯然比較麻煩

六、基于DFS解決實(shí)際問題的算法

（1）Topological Sorting 拓?fù)渑判?/p>

Topological Sorting 拓?fù)渑判? alt=

（1）這個(gè)問題和拓?fù)錄]有直接的關(guān)系，它是一個(gè)離散的關(guān)系

（2）首先看一下這個(gè)圖，實(shí)際上是我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的一個(gè)知識(shí)順序圖

（3）通過箭頭表示知識(shí)點(diǎn)的依賴關(guān)系，A->C表示要學(xué)習(xí)C就要先學(xué)習(xí)A, A是預(yù)備知識(shí)

（4）一般在編寫教材的時(shí)候要有一個(gè)順序可以讓讀者能夠輕松地看下來，不會(huì)因?yàn)槟骋豁?xiàng)知識(shí)的缺乏導(dǎo)致無法理解

（5）有的時(shí)候，比如要學(xué)習(xí)D,就要先學(xué)好A和C這樣，在編寫目錄的時(shí)候，A和C一定要在D的前面開始

（6）最下面的橫向圖可以理解為目錄的組織結(jié)構(gòu)

（7）話說回來，任何一個(gè)知識(shí)體系，其實(shí)并不能做到像直線這樣的排列，因?yàn)楹芏嘀R(shí)都是平行并列的發(fā)生，沒有先后之分

（8）作為理想的情況，我們可以把知識(shí)體系抽象為上面ABCD…這樣一個(gè)有向圖結(jié)構(gòu)

（9）我們需要寫一個(gè)算法來判斷是否可以，把這些知識(shí)體系排成一個(gè)序列使得原來的邊都是從前指向后這樣的目錄關(guān)系，而不會(huì)倒過來發(fā)生

（10）如何來做呢？

1. Topological Sorting: In-Degree

Topological Sorting: In-Degree

● 在一個(gè)有依托關(guān)系的有向圖中，必然會(huì)出現(xiàn)至少一個(gè)點(diǎn)是0入度的點(diǎn)(其Incoming Degree是0，沒有Incoming Edge)

● 比如上圖的A和B, A和B都是一本書的預(yù)備基礎(chǔ)知識(shí)，找到0入度的點(diǎn)就是我們算法的著眼點(diǎn)

● 如果沒有0入度的點(diǎn)，那么每一個(gè)點(diǎn)都要依賴其他的點(diǎn)，這樣的話就會(huì)出現(xiàn)一個(gè)死循環(huán)就無法進(jìn)行拓?fù)渑判?/p>

● 如果有0入度的點(diǎn)，任擇其一，比如選擇A點(diǎn)，準(zhǔn)備一個(gè)棧來記錄(存放)，等效的來說，處理完A點(diǎn)之后

● 可以認(rèn)為A點(diǎn)不存在, 打個(gè)比方，第一學(xué)期之后，假裝沒有第一學(xué)期，從第二學(xué)期開始學(xué)習(xí)，也就是過河拆橋

● 如果這個(gè)過程還能持續(xù)下去，到C點(diǎn)之前，還需要一個(gè)0入度的點(diǎn)即B點(diǎn), 處理完B之后，將B忘掉

● 這時(shí)候到了C點(diǎn)了，等效于C點(diǎn)是一個(gè)0入度的點(diǎn), 把C取出記錄到棧中去，按照這種方式直到最后將所有學(xué)期的課程都排好

● 所有的課程都會(huì)排列到一個(gè)倒序的棧中，自底而上，這是一種解決方案，但還不是很高明

● 如何才能更高明的處理呢? 我們下面來談

2. Topological Sorting: Out Degree + DFS

Topological Sorting: Out Degree + DFS

● 以終為始，我們要思考最后一個(gè)點(diǎn)應(yīng)該是怎樣的，換句話說，大學(xué)中最后一學(xué)期應(yīng)該學(xué)什么課程

● 如果大學(xué)課程是合理的，可以進(jìn)行拓?fù)渑判虻脑?，那么最后一門課必然存在, 沒有任何一門課依賴于它

● 它應(yīng)該不作為任何一門課程的先修課(預(yù)備課)，用專業(yè)術(shù)語來說，它的Out Going Degree是0(沒有發(fā)出的邊)

● 如何發(fā)現(xiàn)這類點(diǎn)，如果用之前一個(gè)個(gè)找出來刪掉來倒序排列就顯得很愚笨了，其實(shí)通過一次DFS即可發(fā)現(xiàn)

● 從任何一點(diǎn)出發(fā)，不失一般性，比如從C點(diǎn)開始最終會(huì)到達(dá)一個(gè)點(diǎn), 假如第一步到達(dá)D點(diǎn)，之后立即回溯并入棧

● 回到了C點(diǎn)又有多種選擇, 它可以到E，然后到F, 這時(shí)候F開始回溯并入棧，然后從E繼續(xù)進(jìn)行回溯并入棧

● 之后又一次回到了C點(diǎn), C點(diǎn)無路可走隨機(jī)也入棧，這個(gè)過程中逐步回溯，每一次回溯從效果上來看等效于回溯點(diǎn)不存在

● 我們的原則是一旦回溯就要把它push到棧中去，如果這里只有CDEF幾個(gè)點(diǎn)的話，那么CEFD就是大學(xué)中正確學(xué)習(xí)的一個(gè)有效次序

● 這時(shí)候，我們可以看到還有A和B沒有處理，沒有關(guān)系，我們可以繼續(xù)DFS, 比如從B再次開始，B在這個(gè)有向圖中是祖先

● B->C這條邊是FORWARD邊, 做了一次標(biāo)記，隨機(jī)進(jìn)行回溯并入棧，這時(shí)候還剩下A點(diǎn)，對(duì)A繼續(xù)進(jìn)行BFS

● 同理，A標(biāo)記之后也會(huì)隨即入棧，我們可以看到最后的這兩步，A和B的次序是可以顛倒的，沒有關(guān)系

● 從任意一點(diǎn)開始，按照這種算法都可以得到很多種解決方案，Begin With End In Mind 始終記住以終為始的哲學(xué)思想

3. BCC: Bi-connectivity/Cut-Vertex 雙連通分量

BCC: Bi-connectivity/Cut-Vertex 雙連通分量

● 所謂連通性

①如果一個(gè)圖中任何兩個(gè)點(diǎn)之間存在一條路，那么兩點(diǎn)是彼此連通的

②如果圖中任何兩個(gè)點(diǎn)都彼此聯(lián)通的，那么這個(gè)圖是連通的

● 所謂Bi-connectivity雙聯(lián)通性，我們首先要了解下Cut-Vertex(切分點(diǎn))

①上圖可以理解為兩個(gè)區(qū)域和一座橋的交通圖，可以看到，D和E兩點(diǎn)對(duì)于整個(gè)交通圖來說是非常重要的

②D和E任意一點(diǎn)缺失都會(huì)把一張圖變成2張，互相之間不能溝通，所以D和E這種點(diǎn)叫做Cut-Vertex

③如果我們?cè)贒和E點(diǎn)做切點(diǎn)，就會(huì)把圖分成若干塊，如上圖是分成了3塊

④接下來被切分的部分變得更加緊湊了，而且刪除被切分部分上的任意一點(diǎn)都不會(huì)再造成分離成不連通的子集

⑤比如刪除下面這粉紅色區(qū)域的任意一點(diǎn)，不失一般性，比如A點(diǎn)，也不會(huì)分離整個(gè)粉紅區(qū)域

⑥而不再存在Cut-Vertex的區(qū)域，我們就稱為雙聯(lián)通分量(Bi-Connected-Component)，比如：粉紅區(qū)域，淺藍(lán)區(qū)域，淺綠區(qū)域

⑦這里Bi暗示的是雙路，它會(huì)組成一個(gè)環(huán)路，一個(gè)環(huán)有雙保險(xiǎn)的意思，比如切斷了其中一條，從另一條路還可以實(shí)現(xiàn)繼續(xù)連通

● 現(xiàn)在任務(wù)很艱巨，我們希望任意給你一個(gè)無向圖都可以把其中的Cut-Vertex找出來，包括由其切割的雙聯(lián)通分量

● 我們可以用DFS來解決這個(gè)問題，如何解決呢?

DFS解決問題

● 從任何一個(gè)點(diǎn)出發(fā)，做一個(gè)DFS，得到一棵DFS樹，樹中有很多路徑，脈絡(luò)式的邊，不會(huì)存在環(huán)路

● 我們先把目光注意在最底層的葉子節(jié)點(diǎn)，這些點(diǎn)都不會(huì)是Cut-Vertex，必然不會(huì)影響整體的連通性

● 那么DFS樹的根節(jié)點(diǎn)(不失一般性，我們稱之為r點(diǎn))是不是呢，其實(shí)這個(gè)取決于當(dāng)初的選點(diǎn)，由其在圖中的地位決定的

● 主要考慮在做完DFS之后r點(diǎn)的Out Going Degree是幾，如果是1度(也就是由r發(fā)出的邊為1個(gè))

● 那它不會(huì)成為Cut-Vertex，因?yàn)樗拇嬖谂c否對(duì)其他點(diǎn)是否連通沒有任何影響

● 如果r點(diǎn)的Out Going Degree是>=2的，不失一般性，我們看2度的情況

● 這樣的話，也就是說r有2個(gè)孩子(L、R), 每個(gè)孩子都是一棵獨(dú)立的家族樹，如上圖(左)所示

● 這時(shí)候r點(diǎn)肯定是Cut-Vertex，顯然它會(huì)造成L、R兩部分分離, 同理2度以上更是如此

● 由此，我們來判斷DFS樹的根節(jié)點(diǎn)是否為Cut-Vertex只需要判斷它的Out Going Degree是1還是大于1

● 還有一種比較復(fù)雜的情況，就是如何判斷DFS樹中的內(nèi)部節(jié)點(diǎn)是否是Cut-Vertex, 如上圖(右)所示

● 不失一般性，我們?nèi)?nèi)部節(jié)點(diǎn)v，v點(diǎn)到根節(jié)點(diǎn)r必然有唯一的一條路徑，如深紅色的虛線路徑

● 同時(shí)，如果，v有兩個(gè)孩子家族, 這時(shí)候，我們就要看這兩個(gè)家族之間的關(guān)系

● 如果v只有1個(gè)孩子，那么v也必然不會(huì)成為Cut-Vertex，如上圖(右)所示

● v有兩個(gè)子家族，比如右邊的家族，如果有一點(diǎn)，比如黃色節(jié)點(diǎn)，它有一條邊能夠連接高于v節(jié)點(diǎn)的某一點(diǎn)如a點(diǎn)

● 也就是說v的BACKWARD邊能夠達(dá)到輩分更高的a點(diǎn)，也就是v的祖先，那么這時(shí)候v相對(duì)于其后代家族來說

● 不會(huì)起到關(guān)鍵的連通作用，這種情況，v刪除后，下面的點(diǎn)和上面的點(diǎn)依舊可以連通

● 這時(shí)候，我們?cè)賮砜磛左邊的孩子家族, 其中的任意一點(diǎn)，比如黃色節(jié)點(diǎn)，它也有一個(gè)BACKWARD邊

● 只不過這個(gè)BACKWARD邊能夠連接的祖先輩分沒有v點(diǎn)的高，如u點(diǎn)，最高到v點(diǎn)

● 這時(shí)候，v點(diǎn)刪除后，以u(píng)點(diǎn)為根的家族將會(huì)和整體分離，這時(shí)候，v點(diǎn)就非常重要且它是一個(gè)Cut-Vertex

● 總結(jié)一下，關(guān)于內(nèi)部節(jié)點(diǎn)是否是Cut-Vertex，關(guān)鍵看它是否存在一個(gè)分支

● 其分支中任意節(jié)點(diǎn)的所有BACKWARD邊的另一頭的點(diǎn)的輩分，都不會(huì)高于v點(diǎn)，這時(shí)候我們要用到一個(gè)指標(biāo)hca

● hca是heighest connected ancestor的縮寫，顧名思義，最高連接的祖先

● hca(v)表示，對(duì)任何一點(diǎn)v來說, 它最長(zhǎng)的BACKWARD邊的所對(duì)應(yīng)的另一頭的祖先點(diǎn)，如何找到v的hca呢

● 很簡(jiǎn)單，在DFS的過程中，對(duì)于任意一點(diǎn)如v點(diǎn)，每發(fā)現(xiàn)一條BACKWARD邊，都要對(duì)它的hca進(jìn)行更新即可

● 更好的方式是把hac指標(biāo)傳遞給他的父節(jié)點(diǎn)，以至再傳遞, 再傳遞…因?yàn)槎际窃谝粭l線上的螞蚱，父因子榮，傳遞給父節(jié)點(diǎn)更合理

● 那么我們?nèi)绾蝸碛沨ac呢，我們知道在DFS中祖先的[dTime, fTime]這個(gè)數(shù)據(jù)范圍一定包含所有孩子的

● 祖先的dTime < 后代的dTime, 我們只需要通過min函數(shù)保留最小的dTime, 越小就是輩分越高的祖先

● 而且在這里，我們并不需要判斷fTime, 而且它的存儲(chǔ)記錄是空閑的，可以把它和hca(v)等效起來

● 下面我們來看一下算法實(shí)現(xiàn)

算法框架

#define hac(x) (fTime(x)) // 利用此處閑置的fTime[]充當(dāng)hca[]
template <typename Tv, typename Te> // 頂點(diǎn)類型、邊類型
void Graph<Tv, Te>::BCC(int v, int& clock, Stack<int>& S) {
    hca(v) = dTime(v) = ++clock;
    status(v) = DISCOVERED; // 發(fā)現(xiàn)v點(diǎn)
    S.push(v); // 頂點(diǎn)v入棧，這個(gè)棧記錄當(dāng)下訪問過的點(diǎn)
    // 以下枚舉v的所有鄰居u
    for(int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) {
        switch(status(u)) {
            // 視u的狀態(tài)分別處理
            // 新點(diǎn)發(fā)現(xiàn)
            case UNDISCOVERED:
                parent(u) = v; // 標(biāo)記父子關(guān)系
                type(v, u) = TREE; // 拓展樹邊
                BCC(u, clock, S); // 從u開始遍歷遞歸做BCC，u會(huì)生成一棵DFS樹，全部返回后
                // 若u經(jīng)后向邊指向v的真祖先，O(1)的時(shí)間進(jìn)行比較
                if(hca(u) < dTime(v)) {
                    // 這時(shí)候u的BACKWARD邊的另一端比v的輩分大，v點(diǎn)就不是關(guān)鍵點(diǎn)
                    hca(v) = min(hca(v), hca(u)); // 則v亦必如此，將hca指標(biāo)掛載給父節(jié)點(diǎn)v
                } else {
                    // 否則，以v為關(guān)鍵點(diǎn)(u以下即是一個(gè)BCC, 且其中頂點(diǎn)此時(shí)正集中于棧S的頂部)
                    // 當(dāng)全部pop完成之后, BCC的成員會(huì)幾乎全被pop出來，這里用幾乎，是因?yàn)檫€應(yīng)該包含u的父節(jié)點(diǎn)v
                    // 也就是說u的這個(gè)BCC分量也會(huì)連帶包括v本身，此時(shí)的v是關(guān)鍵點(diǎn)，只要再通過parent(u)添加它即可
                    // 注意，這里的v并不一定會(huì)在S棧中u的下面, 需要用parent(u)來訪問v節(jié)點(diǎn)
                    // 彈出當(dāng)前BCC中(除v外)的所有節(jié)點(diǎn)，直到u重新出現(xiàn)在棧頂
                    while(u != S.pop()); 
                    // 可視需要做進(jìn)一步處理 TODO
                }
                break;
            case DISCOVERED:
                type(v, u) = BACKWARD; // 標(biāo)記為BACKWARD邊
                // 如果u不是父節(jié)點(diǎn)，換句話說而是祖先節(jié)點(diǎn)更新hca
                if(u != parent(v)) {
                    hac(v) = min(hca(v), dTime(u)); // 更新hca[v], 越小越高
                }
                break;
            default:
                // VISITED (digraphs only) 這里只是和DFS的算法做對(duì)比，可以忽略本分支
                // 這里的CROSS邊實(shí)際上是沒有意義的
                type(v,u) = dTime(v) < dTime(u) ? FORWARD : CROSS;
                break;
        }
    }
    status(v) = VISITED; // 對(duì)v的訪問結(jié)束
}
#undef hca

圖解BCC步驟