開門見山，本篇部落格就介紹圖相關的東西。圖其實就是樹結構的更新版。上篇部落格我們聊了樹的一種，在後邊的部落格中我們還會介紹其他類型的樹，比如紅黑樹，B樹等等，以及這些樹結構的應用。本篇部落格我們就講圖的存儲結構以及圖的搜尋，這兩者算是圖結構的基礎。下篇部落格會在此基礎上聊一下最小生成樹的Prim算法以及克魯斯卡爾算法，然後在聊聊圖的最短路徑、拓撲排序、關鍵路徑等等。廢話少說開始今天的内容。
一、概述
在部落格開頭，我們先聊一下什麼是圖。在此我不想在這兒論述圖的定義，當然那些是枯燥無味的。圖在我們生活中無處不在呢，各種地圖，比如鐵路網，公路網等等這都是典型的圖形結構。來點直覺的，我們就以北京的地鐵為例。如果你在北京坐過地鐵，那麼對下方的這張圖并不陌生。下方就是一個典型的圖形結構，而且還是連通圖呢。也就是說，你從任意一個地鐵站進去，就可以在其他相連的地鐵站出來。
下方每個地鐵站就是圖的結點，地鐵站與地鐵站之間的連線就是圖的弧，如果我們給弧添加上距離，那麼這個距離就是這個弧所對應的權值。比如我們舉個例子，假如大望路站到國貿站的距離是1.5公裡。那麼我們翻譯成我們圖中的術語就是大望路結點到國貿結點有一條弧，這條弧的權值是1.5公裡。當然，從大望路到國貿有多條路徑，那麼那條路徑最近呢，這就是我們後面要說的最優路徑了。我們如果想連通每個站點，并且想連接配接每個站點的權值的和最小，那麼就是我們以後要聊的最小生成樹了。
今天我們部落格的主題就是如果去存儲下方這種類型的圖，然後對圖中的節點進行周遊。當然存儲的時候我們要存儲弧度所對應的權值。
當然，上面這個地鐵站的地鐵是比較複雜的，我們就簡單畫一個圖，來模拟一下上述圖的結構即可。然後将該結構進行存儲。然後再基于該存儲結構對圖進行周遊。圖的實體存儲結構可以分為鄰接矩陣和鄰接連結清單的形式。則圖的搜尋分為廣度優先搜尋（BSF -- Breadth First Search）和深度優先搜尋（DFS -- Depth First Search）。下面這個圖的結構就是我們要存儲以及周遊的圖。紅色的部分就是每條邊的權值。
二、鄰接矩陣
接下來我們就将上面這個圖存儲下來，當然是使用我們上面提到過的鄰接矩陣或者鄰接連結清單來存儲。在建構圖之前呢，我們依然要先定義圖的協定，因為圖的實體存儲結構分為鄰接矩陣和鄰接連結清單。不同的存儲方式也就對應着建構圖的方式不同，那麼圖的BFS與DFS的具體實作也是不同的，但是對外的接口是一緻的。還是那句話，面向接口程式設計。是以我們要先定義完圖的相關接口，然後在給出具體實作。
1.圖的接口的定義
下方代碼片段就是我們圖結構的協定，所有定義的圖結構都要遵循下方的協定。createGraph()方法會根據傳入的參數建構相應存儲結構的圖，breadthFirstSearch()方法對應的就是圖的廣度優先搜尋，depthFirstSearch()對應的就是圖的深度優先搜尋，displayGraph()就負責将圖的整個存儲結構進行輸出。
還是那句話，因為圖對外的調用接口是一緻的，是以我們對于不同的實體存儲結構的圖，我們可以使用同一個測試用例。定義好了下方的協定後，我們就可以根據圖的實體存儲結構，給出具體實作了。
2、圖中關系的輸入
要想建構上面的圖的結構，我們得根據圖所提供的資訊來建構相應實體結構的圖。下方就是我們在建構圖結構時，所輸入的資訊。allGraphNote數組中存儲的是圖中的所有結點，就類似于某個地鐵站的名字。而relation數組中存儲的就是結點之間的資訊。其中一個元組就是一個結點間的關系。(A, B, 10)就說明A到B有條弧，該弧的權值是10，類似于大望路到國貿有條地鐵，距離是1.5一樣。我們就可以根據下方的這個資訊來建構我們想建構的圖了。
當然下方資訊在鄰接矩陣和鄰接連結清單中的存儲方式是不同的，下方會詳細介紹。 而上面我們提到的createGraph()方法中的兩個參數，就是下方這兩個數組。
3.鄰接矩陣的建構
鄰接矩陣是存儲圖結構的一種實體存儲方式，其實說白了鄰接矩陣就是一個二維數組，這個二維數組中存儲的是圖中節點的關系。下方這個截圖就是上述圖結構的鄰接矩陣的存儲方式。節點與節點中間如果沒有弧的話，那麼權值就是0。如果兩個節點間有關系的話，那麼其中存儲的就是該弧上的權值，具體如下所示。
根據上面這個結構，我們就開始我們的代碼實作了，下方就是我們建立鄰接矩陣相應的代碼。createGraph()方法的第一個參數是我們上面提到過的allGraphNote，也就是圖中所有的結點集合。第二個參數則是上面我們提到過的relation，其中存儲的就是圖中結點間的關系。下方的initGraph()方法負責存儲圖的鄰接矩陣的初始化，而relationDic中存儲的就是圖的結點與鄰接矩陣下标的對應關系。通過下方這三個函數，我們就可以建構出上面圖結構所對應的鄰接矩陣了。
上面這個矩陣其實就是下方這段代碼建構的圖結構的輸出結果。通過輸出結果可以看出，上面的鄰接矩陣以紅線為中心軸對稱。因為A到B的的權值為10，那麼B到A的權值也是10，是以會形成上述對稱結構。這個在我們對圖的周遊時需要注意一下該對稱結構。
4.鄰接矩陣的廣度優先搜尋（BFS）
上面建立完鄰接矩陣後，我們就開始對此鄰接矩陣進行操作了。接下來要幹的事情就是對上面的鄰接矩陣進行廣度優先搜尋（Breadth Frist Search）。在之前二叉樹的層次周遊中我們提到過，二叉樹的層次周遊與圖的廣度優先搜尋就是一個東西。接下來我們仔細的聊聊。圖的廣度優先搜尋要借助我們之前聊的隊列。該隊列中記錄的就是上次周遊那一層節點，下次周遊結點的順序就按照隊列中記錄的節點的順序來。下方就是廣度搜尋的示意圖。
上面BFS示意圖中，是以A為首結點來進行的廣度優先搜尋。廣度優先搜尋的思想是借助隊列“一層一層的輸出”。在周遊一個點後，那麼就将與該結點相連并未周遊的點加入隊列，下次輸出的點從隊列中擷取，然後再輸出，不斷的重複這個過程。從描述中我們可以看出，此過程可以使用遞歸來解決。下方代碼段就是鄰接矩陣的廣度優先搜尋的代碼，如下所示：
上面的代碼并不複雜，上面用到的visited數組用來标記目前周遊的結點是否已經被周遊過，因為上述的矩陣是對稱的。代碼比較簡單，在此就不做過多贅述了。主要還是借助隊列來保證層級關系。
5.鄰接矩陣的深度優先搜尋（Depth First Search）
接下來我們來聊深度優先搜尋--DFS。一句話總結DFS，其實就是“一條道走到黑，走不通，退一步再找道”。其實深度優先搜尋與之前我們聊的二叉樹的先序周遊非常類似。在實作DFS時，如果不使用遞歸來實作的話，我們可以借助棧的操作來實作。因為遞歸本來就是一個棧結構，是以直接可以使用遞歸來完成DFS。下方就是DFS的示意圖，下方的示意圖看明白了，用代碼去實作也就不是什麼難事了。
下方這個遞歸函數就是鄰接矩陣的DFS的實作，同樣會用到visited來标記結點是否被周遊過。
6.測試用例
下方這段代碼就是我們的測試用例，該測試用例函數的參數的類型是GraphType, 也就是我們之前定義的協定。隻要是遵循該協定的類的對象都可以作為該函數的參數，是以我們下方這個測試用例是通用的。這也是面向接口程式設計的好處之一。
下方是上述代碼的測試用例所輸出的結果，如下所示。當然該測試用例也同樣适用于鄰接連結清單實作的圖，前提是要遵循我們之前定義的協定。
三、鄰接連結清單
上面介紹完鄰接矩陣及其相關内容後，我們還要聊一下另一種圖的存儲結構----鄰接連結清單。鄰接連結清單就是數組與連結清單的結合體，也就是将連結清單挂在一維數組中。開門見山，下方就是鄰接連結清單測試用例所輸出的結果。前面的下标其實就是一個一維數組，每個下标後方所跟的鍊就是挂在該下标後方的鍊。鍊中每個節點所存儲的内容是與該數組下标所連接配接的結點的下标以及權值。下方這個鄰接連結清單存儲的就是上面我們那個圖。
雖然下方的DFS和BFS與上述鄰接矩陣中的DFS和BFS不同，但是規則是按照我們之前聊的規則來的。
1.鄰接連結清單的建立
上面也說了，鄰接連結清單就是将一個個的連結清單挂在一維數組中。在建立鄰接連結清單之前，我們得先建立鄰接連結清單中連結清單所需的結點。下方這個就是我們鄰接連結清單中所需要的結點。data存儲的是所連結點在一維數組中的index，weightNumber存儲的就是權值，preNoteIndex存儲的就是目前結點所在連結清單連接配接的一維數組的index。next則指向連結清單中的下一個結點。
建立好我們需要的頭結點後，我們就該建立我們的鄰接連結清單了。下方代碼段的createGraph()方法所需的參數與鄰接矩陣對應的方法所需的參數一緻。下方函數中第一個循環是初始化一維數組，将每個結點的資訊添加到一維數組中，等待着與這些結點相連的結點挂在相應的鍊上。relationDic中記錄着結點與一維數組索引的對應資訊。第二個循環是周遊relation數組，取出每個結點間的關系資訊，根據這些資訊将相應的結點挂在相應的一維數組每個元素對應的鍊上。
2、鄰接連結清單的廣度優先搜尋（BFS）
鄰接連結清單的廣度優先搜尋與鄰接矩陣的廣度優先搜尋雖然算法一緻，但是由于其存儲資料的方式不同，具體實作起來還是有所不同的。因為是BFS, 是以，鄰接連結清單的BFS依然會借助隊列來實作。下方我們采用了隊列加遞歸的方式來實作的BFS。
方法中最外層的if語句塊用來判斷目前方法傳入的索引所對應的結點是否已經被周遊了，如果未被周遊則輸出，輸出後将标志位置為true。周遊完目前結點後，将與該結點相連接配接的并且未被周遊的結點進入隊列。然後再遞歸周遊隊列中未被周遊的結點。具體代碼如下所示：
3、鄰接連結清單的深度優先搜尋（DFS）
下方這段代碼就是鄰接連結清單的深度優先搜尋，下方代碼段沒有借用隊列，但是使用了遞歸。因為在遞歸調用函數的過程中，存在遞歸調用棧。棧有着先入後出的特點，上面我們在聊DFS時聊到，深度優先搜尋就是一直往下走，走不動了就回退一步繼續尋找可以往下走的路。這個一直往下走其實就是不斷push入棧的過程，而回退一步其實就是pop出棧的步驟。鑒于遞歸過程本身就是一個棧的結構，是以就不需要我們再建立一個棧來實作這個push和pop操作了。下方就是鄰接連結清單的DFS的相關代碼。代碼并不複雜，在此不做過多贅述了。
至此，圖的鄰接矩陣和鄰接連結清單的DFS、BFS就聊完了。當然本篇部落格往上貼的代碼隻是部分核心代碼，完整的Demo已在github上進行分享。下方就是分享連結，下篇部落格會聊一下圖的最小生成樹的兩個算法。今天部落格就先到這兒。
Github分享位址：https://github.com/lizelu/DataStruct-Swift/tree/master/Graph
作者：青玉伏案
出處：http://www.cnblogs.com/ludashi/
本文版權歸作者和共部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。
收履歷：某網際網路公司，招聘iOS/Android靠譜工程師，入職後，可内部聯系樓主，有小禮品贈送，有意者可郵箱投遞履歷：[email protected]