相關概念
類比的樹的遍歷，圖的遍歷也是指從一個頂點開始，依次遍歷其餘所有頂點。圖的遍歷是許多圖論演算法的基礎，比如網路爬蟲。圖的遍歷，無論是DFS，還是BFS都是是建立在“記憶化訪問”基礎上，所以都需要相應的資料來記錄當前結點是否被訪問過。
圖的儲存
圖的儲存方法分為順序儲存（鄰接矩陣）和鏈式儲存（鄰接表，鄰接多重表，十字連結串列）兩大型別。其中鄰接矩陣，鄰接表使用最為常見，而在實際的應用中需要根據不同的需要來選擇不同的儲存方法。
鄰接表用於儲存稀疏圖，鄰接矩陣用於儲存稠密圖。
如下圖所示：
圖1，1代表結點相連線
圖2，將連線的頂點一次新增到頂點後
專案相關結構
圖按照不同的分類標準有不同的分類方式，例如有權圖，無權圖，有向圖，無向圖等。在具體的程式碼實現過程中，不可能為每一種圖專門實現一個遍歷方法，這樣做無疑增加了程式碼量，也不符合程式碼的重複利用。基於此的思考：
圖的底層無論使用鄰接表或者鄰接矩陣來儲存，都統一的實現一個介面，對於上層的圖相關演算法，都透過該介面來訪問獲取圖的資料。
基於此想法的考慮，我們利用迭代器模式來實現：
圖3，鄰接矩陣稠密圖的類設計
圖4，迭代器設計，可以遍歷一個頂點所有相鄰接的頂點
圖5，鄰接表稀疏圖的類設計
圖6，迭代器設計，可以遍歷一個頂點所有相鄰接的頂點
如上設計所示，無論在稠密圖中，還是稀疏圖中的迭代器實現的方法都是一致的，在上層的圖論演算法設計中，我們就可以使用相同的程式碼來操作鄰接表和鄰接矩陣。
注：以上的稀疏圖和稠密圖的設計中沒有考慮帶權圖，其實完全可以先將兩個頂點和邊封裝在一個Edge中，使用模板來實現，就能適用更為普遍的情況。
深度優先遍歷（DFS）
思想：
DFS的基本思想就是從某個頂點V出發，訪問並標記此頂點，然後依次從與V相鄰接並且未被訪問的鄰接點u出發，進行深度優先搜尋，直到途中所有和V有路徑想通的頂點都被訪問到，若此時途中尚未有頂點未被訪問，再選擇未被訪問的頂點作為起始點，重複以上操作，直到途中所有頂點都被訪問到。
以下是具體的程式碼實現：
圖7，DFS的非遞迴實現
圖8，DFS遞迴實現
廣度優先遍歷（BFS）
思想：
從某個頂點V出發，訪問並標記此頂點，然後依次訪問V的各個未被訪問的鄰接點，並對這些鄰接點做相同的操作，直至途中和V有路徑相通的頂點都被訪問到，若此時途中尚未有頂點未被訪問，再選擇未被訪問的頂點作為起始點，重複以上操作，直到途中所有頂點都被訪問到。
以下是具體的程式碼實現：
圖9，BFS實現
結論
以上的演算法都是基於簡單圖考慮，而對於有自環邊，平行邊同樣適用。圖的遍歷就可以實現一些簡單的圖演算法，例如求圖的連同分量，無權圖的最短路徑等。
不想成為full stack 的程式猿，不是好程式猿！專注分享計算機程式設計相關的知識點。新手一枚，誠求各路大神留下您寶貴的建議，不勝感激。
