圖的搜索技巧是整個(gè)圖算法領(lǐng)域的核心。
圖的表示
有兩種標(biāo)準(zhǔn)方法：
1.鄰接鏈表
2.鄰接矩陣
鄰接鏈表是將一個(gè)結(jié)點(diǎn)所有相鄰的結(jié)點(diǎn)放到一個(gè)鏈表中，將所有的鏈表放在一個(gè)數(shù)組中，就表示了整個(gè)圖的結(jié)點(diǎn)和邊。
鄰接矩陣是用一個(gè) n * n 的矩陣（n 為結(jié)點(diǎn)的個(gè)數(shù)）來表示圖，其中 A[ij] 表示結(jié)點(diǎn) i 和結(jié)點(diǎn) j 之間是否存在邊。
鄰接鏈表擴(kuò)展方便，占用空間較少，但是查找速度略慢。
廣度優(yōu)先搜索
思路是優(yōu)先處理離源結(jié)點(diǎn)近的結(jié)點(diǎn)。
廣度優(yōu)先搜索的過程是這樣的：
1.將源結(jié)點(diǎn)放入隊(duì)列
2.開始循環(huán)的處理隊(duì)列，直到隊(duì)列為空
處理的做法是從隊(duì)列中出棧一個(gè)元素，將元素的相鄰結(jié)點(diǎn)（還沒有被放入過）放入隊(duì)列中
過程中的細(xì)節(jié)包括兩方面：
1.結(jié)點(diǎn)標(biāo)記顏色（白、灰、黑），來標(biāo)記是否進(jìn)入過隊(duì)列，相鄰結(jié)點(diǎn)是否都處理完畢
2.結(jié)點(diǎn)填寫額外的數(shù)據(jù)，如 d 表示到根結(jié)點(diǎn)的距離，π 表示結(jié)點(diǎn)的父結(jié)點(diǎn)
廣度優(yōu)先搜索的運(yùn)行時(shí)間為 O(V+E)，即鄰接鏈表大小的一個(gè)線性函數(shù)。
書中給出了一堆引理，定理，證明運(yùn)行廣度優(yōu)先搜索后，結(jié)點(diǎn)的 d
是結(jié)點(diǎn)到根結(jié)點(diǎn)的最短路徑長(zhǎng)度，可以由結(jié)點(diǎn)的 π 一路向上找出一條最短路徑。
廣度優(yōu)先樹，是上述算法運(yùn)行后得到的結(jié)果，還可以被稱為圖 G 的前驅(qū)子圖。
深度優(yōu)先搜索
思路是在圖中盡量深入的探索，處理完結(jié)點(diǎn)的所有出發(fā)邊后再回來處理該結(jié)點(diǎn)。
深度優(yōu)先搜索形成的前驅(qū)子圖和廣度優(yōu)先搜索不同，是一個(gè)深度優(yōu)先森林。且算法能夠保證所有的深度優(yōu)先樹是不相交的。
深度優(yōu)先搜索樹能夠提供關(guān)于圖結(jié)構(gòu)的重要信息。
深度優(yōu)先搜索的運(yùn)行時(shí)間為 θ(V+E)
括號(hào)化定理、白色路徑定理
邊可以分為樹邊、后向邊、前向邊、橫向邊，書中解釋了如何給邊分類
在對(duì)無向圖的深度優(yōu)先搜索中，從來不會(huì)出現(xiàn)前向邊和橫向邊
拓?fù)渑判?/h2>
拓?fù)渑判蚴怯邢驘o環(huán)圖中所有結(jié)點(diǎn)的一種線性次序，該次序滿足，對(duì)圖的任意一條邊（u, v），u 在次序中處于 v 的前面。
我們可以用拓?fù)渑判騺斫o一堆有相對(duì)次序的事件指明一個(gè)線性次序，例如穿衣服的次序。
生成拓?fù)渑判虻姆椒ㄊ?，利用深度?yōu)先搜索遍歷圖，用一個(gè)鏈表來存儲(chǔ)拓?fù)渑判虻慕Y(jié)果，當(dāng)深度優(yōu)先搜索算法給某個(gè)結(jié)點(diǎn)標(biāo)記 f（完成時(shí)間）時(shí)，將結(jié)點(diǎn)插入到鏈表的頭部。
生成拓?fù)渑判虻倪\(yùn)行時(shí)間為 θ(V+E)
一個(gè)有用的引理：引理 22.11，一個(gè)有向圖是無環(huán)的當(dāng)且僅當(dāng)對(duì)其進(jìn)行的深度優(yōu)先搜索不產(chǎn)生后向邊。
可以引申出一個(gè)面試題：如何確定一個(gè)有向圖是否有環(huán)？
書中還給出了上述生成算法的正確性證明
強(qiáng)連通分量
強(qiáng)連通分量是指，有向圖的一個(gè)最大（意思是盡可能的大）結(jié)點(diǎn)集，其中的任意兩個(gè)結(jié)點(diǎn)都可以互相到達(dá)。通俗的說就是有向圖中的環(huán)組成的結(jié)點(diǎn)集，不能連通的環(huán)就是一個(gè)強(qiáng)連通分量。
一個(gè)概念，有向圖的轉(zhuǎn)置，是指將圖中所有邊反向后形成的有向圖。圖的轉(zhuǎn)置和圖有相同的強(qiáng)連通分量
如何計(jì)算一個(gè)有向圖的強(qiáng)連通分量？
1.先對(duì)有向圖進(jìn)行深度優(yōu)先搜索
2.生成圖的轉(zhuǎn)置圖
3.對(duì)轉(zhuǎn)置圖進(jìn)行深度優(yōu)先搜索，特別的是在主循環(huán)中探索結(jié)點(diǎn)時(shí)，按照第一步中計(jì)算的結(jié)點(diǎn)完成時(shí)間降序進(jìn)行探索
又是一個(gè)概念，分量圖，定義為通過收縮所有相鄰結(jié)點(diǎn)都在同一個(gè)強(qiáng)連通分量中的邊，就得到了分量圖。通俗的說就是將計(jì)算完強(qiáng)連通的圖進(jìn)行收縮，規(guī)則是每個(gè)強(qiáng)連通分量都收縮成一個(gè)結(jié)點(diǎn)，那么剩下的邊就是強(qiáng)連通分量以外的邊（連接強(qiáng)連通分量的邊，或者說不在環(huán)中的邊）
分量圖是一個(gè)有向無環(huán)圖（因?yàn)榄h(huán)都在強(qiáng)連通分量中了）
接下來書中花了一些篇幅證明上述計(jì)算強(qiáng)連通分量算法的正確性，引理 22.13、引理22.14、推論 22.15 以及最后的定理 22.16
其中的關(guān)鍵在于理解算法中對(duì)轉(zhuǎn)置圖的深度優(yōu)先探索形成的森林為何就是圖的強(qiáng)連通分量
