數(shù)據(jù)結(jié)構(gòu)(四) 圖的物理存儲結(jié)構(gòu)與深搜、廣搜（Swift面向?qū)ο蟀妫?/a>
開門見山，本篇博客就介紹圖相關(guān)的東西。圖其實(shí)就是樹結(jié)構(gòu)的升級版。上篇博客我們聊了樹的一種，在后邊的博客中我們還會介紹其他類型的樹，比如紅黑樹，B樹等等，以及這些樹結(jié)構(gòu)的應(yīng)用。本篇博客我們就講圖的存儲結(jié)構(gòu)以及圖的搜索，這兩者算是圖結(jié)構(gòu)的基礎(chǔ)。下篇博客會在此基礎(chǔ)上聊一下最小生成樹的Prim算法以及克魯斯卡爾算法，然后在聊聊圖的最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑等等。廢話少說開始今天的內(nèi)容。
一、概述
在博客開頭，我們先聊一下什么是圖。在此我不想在這兒論述圖的定義，當(dāng)然那些是枯燥無味的。圖在我們生活中無處不在呢，各種地圖，比如鐵路網(wǎng)，公路網(wǎng)等等這都是典型的圖形結(jié)構(gòu)。來點(diǎn)直觀的，我們就以北京的地鐵為例。如果你在北京坐過地鐵，那么對下方的這張圖并不陌生。下方就是一個典型的圖形結(jié)構(gòu)，而且還是連通圖呢。也就是說，你從任意一個地鐵站進(jìn)去，就可以在其他相連的地鐵站出來。
下方每個地鐵站就是圖的結(jié)點(diǎn)，地鐵站與地鐵站之間的連線就是圖的弧，如果我們給弧添加上距離，那么這個距離就是這個弧所對應(yīng)的權(quán)值。比如我們舉個例子，假如大望路站到國貿(mào)站的距離是1.5公里。那么我們翻譯成我們圖中的術(shù)語就是大望路結(jié)點(diǎn)到國貿(mào)結(jié)點(diǎn)有一條弧，這條弧的權(quán)值是1.5公里。當(dāng)然，從大望路到國貿(mào)有多條路徑，那么那條路徑最近呢，這就是我們后面要說的最優(yōu)路徑了。我們?nèi)绻脒B通每個站點(diǎn)，并且想連接每個站點(diǎn)的權(quán)值的和最小，那么就是我們以后要聊的最小生成樹了。
今天我們博客的主題就是如果去存儲下方這種類型的圖，然后對圖中的節(jié)點(diǎn)進(jìn)行遍歷。當(dāng)然存儲的時候我們要存儲弧度所對應(yīng)的權(quán)值。
當(dāng)然，上面這個地鐵站的地鐵是比較復(fù)雜的，我們就簡單畫一個圖，來模擬一下上述圖的結(jié)構(gòu)即可。然后將該結(jié)構(gòu)進(jìn)行存儲。然后再基于該存儲結(jié)構(gòu)對圖進(jìn)行遍歷。圖的物理存儲結(jié)構(gòu)可以分為鄰接矩陣和鄰接鏈表的形式。則圖的搜索分為廣度優(yōu)先搜索（BSF -- Breadth First Search）和深度優(yōu)先搜索（DFS -- Depth First Search）。下面這個圖的結(jié)構(gòu)就是我們要存儲以及遍歷的圖。紅色的部分就是每條邊的權(quán)值。
二、鄰接矩陣
接下來我們就將上面這個圖存儲下來，當(dāng)然是使用我們上面提到過的鄰接矩陣或者鄰接鏈表來存儲。在構(gòu)建圖之前呢，我們依然要先定義圖的協(xié)議，因?yàn)閳D的物理存儲結(jié)構(gòu)分為鄰接矩陣和鄰接鏈表。不同的存儲方式也就對應(yīng)著構(gòu)建圖的方式不同，那么圖的BFS與DFS的具體實(shí)現(xiàn)也是不同的，但是對外的接口是一致的。還是那句話，面向接口編程。所以我們要先定義完圖的相
