本節(jié)主要介紹圖的遍歷算法BFS和DFS，以及尋找圖的(強)連通分量的算法

Traversal就是遍歷，主要是對圖的遍歷，也就是遍歷圖中的每個節(jié)點。對一個節(jié)點的遍歷有兩個階段，首先是發(fā)現(xiàn)(discover)，然后是訪問(visit)。遍歷的重要性自然不必說，圖中有幾個算法和遍歷沒有關(guān)系？！

[算法導(dǎo)論對于發(fā)現(xiàn)和訪問區(qū)別的非常明顯，對圖的算法講解地特別好，在遍歷節(jié)點的時候給節(jié)點標(biāo)注它的發(fā)現(xiàn)節(jié)點時間d[v]和結(jié)束訪問時間f[v]，然后由這些時間的一些規(guī)律得到了不少實用的定理，本節(jié)后面介紹了部分內(nèi)容，感興趣不妨閱讀下算法導(dǎo)論原書]

圖的連通分量是圖的一個最大子圖，在這個子圖中任何兩個節(jié)點之間都是相互可達(dá)的(忽略邊的方向)。我們本節(jié)的重點就是想想怎么找到一個圖的連通分量呢？

一個很明顯的想法是，我們從一個頂點出發(fā)，沿著邊一直走，慢慢地擴大子圖，直到子圖不能再擴大了停止，我們就得到了一個連通分量對吧，我們怎么確定我們真的是找到了一個完整的連通分量呢？可以看下作者給出的解釋，類似上節(jié)的Induction，我們思考從i-1到i的過程，只要我們保證增加了這個節(jié)點后子圖仍然是連通的就對了。

Let'slookatthefollowingrelatedproblem.Showthatyoucanorderthenodesinaconnectedgraph,V1,V2,…Vn,sothatforanyi=1…n,thesubgraphoverV1,…,Viisconnected.Ifwecanshowthisandwecanfigureouthowtodotheordering,wecangothroughallthenodesinaconnectedcomponentandknowwhenthey'reallusedup.

Howdowedothis?Thinkinginductively,weneedtogetfromi-1toi.Weknowthatthesubgraphoverthei-1firstnodesisconnected.Whatnext?Well,becausetherearepathsbetweenanypairofnodes,consideranodeuinthefirsti-1nodesandanodevintheremainder.Onthepathfromutov,considerthelastnodethatisinthecomponentwe'vebuiltsofar,aswellasthefirstnodeoutsideit.Let'scallthemxandy.Clearlytheremustbeanedgebetweenthem,soaddingytothenodesofourgrowingcomponentkeepsitconnected,andwe'veshownwhatwesetouttoshow.

經(jīng)過上面的一番思考，我們就知道了如何找連通分量：從一個頂點開始，沿著它的邊找到其他的節(jié)點(或者說站在這個節(jié)點上看，看能夠發(fā)現(xiàn)哪些節(jié)點)，然后就是不斷地向已有的連通分量中添加節(jié)點，使得連通分量內(nèi)部依然滿足連通性質(zhì)。如果我們按照上面的思路一直做下去，我們就得到了一棵樹，一棵遍歷樹，它也是我們遍歷的分量的一棵生成樹。在具體實現(xiàn)這個算法時，我們要記錄“邊緣節(jié)點”，也就是那些和已得到的連通分量中的節(jié)點相連的節(jié)點，它們就像是一個個待辦事項(to-dolist)一樣，而前面加入的節(jié)點就是標(biāo)記為已完成的(checkedoff)待辦事項。

這里作者舉了一個很有意思的例子，一個角色扮演的游戲，如下圖所示，我們可以將房間看作是節(jié)點，將房間的門看作是節(jié)點之間的邊，走過的軌跡就是遍歷樹。這么看的話，房間就分成了三種：(1)我們已經(jīng)經(jīng)過的房間；(2)我們已經(jīng)經(jīng)過的房間附近的房間，也就是馬上可以進(jìn)入的房間；(3)“黑屋”，我們甚至都不知道它們是否存在，存在的話也不知道在哪里。