5-31.
DFS和BFS使用了哪些資料結構?
解析：
其實剛讀完這一章，我一開始想到的是用鄰接表來表示圖，但其實用鄰接矩陣也能實作啊？後來才發現應該回答，BFS用隊列實作；DFS可以用棧實作也可以改寫成遞歸形式。用棧來消除遞歸改寫DFS也出現在《算法導論》的練習題22.3-6。
5-32.
寫一個函數，在周遊二叉查找數的時候，輸出第i個結點。
模仿DFS周遊時維護一個進入時間數組和完成時間數組的特點，維護一個全局變量n，在中序周遊的時候，每周遊一個結點就n++，直到n=i時列印這個結點，或者周遊完成時仍然n!=i時報錯即可。
題外話：
第5章“圖周遊”的Interview Problems部分确實隻有這兩題，而第6章“帶權圖算法”幹脆就沒Interview Problems這一部分。其實圖本身的表示就比較複雜，幾個基本的圖算法雖然思路不難，但是代碼量不小，同時要寫繁瑣的初始化方法，寫具體算法實作時還要用到各種輔助資料結構，編碼起來想少都不行。況且就算真寫出來了，正确性的證明又很費功夫（比如拓撲排序、強聯通分支），是以面試時除了專門做這個方向的，很少會考到具體的代碼書寫，更不用說其他變形、改進了。這也就是為什麼圖相關的面試題并不多的原因。
另外提一下，《算法設計手冊》上的拓撲排序和強聯通分支算法是基于邊分類的，而且它把DFS寫成了一個可擴充的架構；而《算法導論》則是利用最後完成時間來實作這兩個算法，在此之前把DFS寫成了一個子程式供這兩個算法調用。究竟孰優孰劣我不評價，從先入為主和對我而言易于了解的角度和來說，我更傾向于使用後者。
既然提到了《算法設計手冊》上DFS的架構寫法了，這個算法正好來進行示範。（《算法導論》思考題22-2曾提到了這個概念）。
先來看看《算法設計手冊》版DFS架構：
《算法設計手冊》版DFS架構
挂接點是指，如果我們從連通圖中删除這個結點，會導緻圖不再連通。下圖中的白點就是挂接點，可以把它看作為圖上最脆弱的點。
使用DFS或BFS寫一個暴力算法很簡單：删除一個結點，用DFS或BFS判斷是否連通；恢複原圖，删除下一個結點繼續判斷，直至所有接點都判斷過。如果結點數n個，邊數m個，暴力算法時間複雜度為O(n(m+n))。
現在用DFS周遊時生成樹的角度來看。對于這棵樹上所有在原圖的邊，歸為TREE邊；其餘所有邊是BACK邊，即它們指向一個先于這個結點周遊的另一個結點。
可以發現一些規律：
DFS樹的葉結點不可能是挂接點，删去它樹的連通性未被破壞。隻有樹的内結點可能是挂接點。
對于DFS樹的根，如果它隻有一個孩子，那麼删去它和删去一個葉結點是一樣的。而孩子多于1個時，删去根會導緻孩子們不再連通，也即它是挂接點。
對于一個BACK邊，它連接配接的兩個結點的TREE路徑（即DFS時形成的路徑）上的所有結點都不可能是挂接點。
尋找挂接點需要維護BACK邊連接配接DFS樹上結點與其祖先的資訊。用reachable_ancesor[v]表示結點v用BACK邊能連接配接的最老祖先（初始化為v），tree_out_degree[v]表示結點在DFS樹的出度。edge_classification(int x,int y)用于判斷(x,y)是TREE還是BACK。
下面是v與祖先的連通性和v是否是挂接點的關系，一共是三種情況：
用代碼實作在process_vertex_late()裡，即：
最後幾行用entry_time[v]表示v的年齡，time_v是v通過BACK邊達到的最老結點。如果v的parent能通過v的BACK到達v的最老祖先，那麼parent(v)肯定不是挂接點，下次處理parent(v)時做出這樣的标記讓它能通過v的BACK到達v的最老祖先。
本文轉自五嶽部落格園部落格，原文連結：www.cnblogs.com/wuyuegb2312/p/3264943.html，如需轉載請自行聯系原作者