數(shù)據(jù)結(jié)構(gòu)(四) 圖的物理存儲(chǔ)結(jié)構(gòu)與深搜、廣搜（Swift面向?qū)ο蟀妫?/a>

開(kāi)門(mén)見(jiàn)山，本篇博客就介紹圖相關(guān)的東西。圖其實(shí)就是樹(shù)結(jié)構(gòu)的升級(jí)版。上篇博客我們聊了樹(shù)的一種，在后邊的博客中我們還會(huì)介紹其他類型的樹(shù)，比如紅黑樹(shù)，B樹(shù)等等，以及這些樹(shù)結(jié)構(gòu)的應(yīng)用。本篇博客我們就講圖的存儲(chǔ)結(jié)構(gòu)以及圖的搜索，這兩者算是圖結(jié)構(gòu)的基礎(chǔ)。下篇博客會(huì)在此基礎(chǔ)上聊一下最小生成樹(shù)的Prim算法以及克魯斯卡爾算法，然后在聊聊圖的最短路徑、拓?fù)渑判?、關(guān)鍵路徑等等。廢話少說(shuō)開(kāi)始今天的內(nèi)容。

 

一、概述

在博客開(kāi)頭，我們先聊一下什么是圖。在此我不想在這兒論述圖的定義，當(dāng)然那些是枯燥無(wú)味的。圖在我們生活中無(wú)處不在呢，各種地圖，比如鐵路網(wǎng)，公路網(wǎng)等等這都是典型的圖形結(jié)構(gòu)。來(lái)點(diǎn)直觀的，我們就以北京的地鐵為例。如果你在北京坐過(guò)地鐵，那么對(duì)下方的這張圖并不陌生。下方就是一個(gè)典型的圖形結(jié)構(gòu)，而且還是連通圖呢。也就是說(shuō)，你從任意一個(gè)地鐵站進(jìn)去，就可以在其他相連的地鐵站出來(lái)。

下方每個(gè)地鐵站就是圖的結(jié)點(diǎn)，地鐵站與地鐵站之間的連線就是圖的弧，如果我們給弧添加上距離，那么這個(gè)距離就是這個(gè)弧所對(duì)應(yīng)的權(quán)值。比如我們舉個(gè)例子，假如大望路站到國(guó)貿(mào)站的距離是1.5公里。那么我們翻譯成我們圖中的術(shù)語(yǔ)就是大望路結(jié)點(diǎn)到國(guó)貿(mào)結(jié)點(diǎn)有一條弧，這條弧的權(quán)值是1.5公里。當(dāng)然，從大望路到國(guó)貿(mào)有多條路徑，那么那條路徑最近呢，這就是我們后面要說(shuō)的最優(yōu)路徑了。我們?nèi)绻脒B通每個(gè)站點(diǎn)，并且想連接每個(gè)站點(diǎn)的權(quán)值的和最小，那么就是我們以后要聊的最小生成樹(shù)了。

今天我們博客的主題就是如果去存儲(chǔ)下方這種類型的圖，然后對(duì)圖中的節(jié)點(diǎn)進(jìn)行遍歷。當(dāng)然存儲(chǔ)的時(shí)候我們要存儲(chǔ)弧度所對(duì)應(yīng)的權(quán)值。

當(dāng)然，上面這個(gè)地鐵站的地鐵是比較復(fù)雜的，我們就簡(jiǎn)單畫(huà)一個(gè)圖，來(lái)模擬一下上述圖的結(jié)構(gòu)即可。然后將該結(jié)構(gòu)進(jìn)行存儲(chǔ)。然后再基于該存儲(chǔ)結(jié)構(gòu)對(duì)圖進(jìn)行遍歷。圖的物理存儲(chǔ)結(jié)構(gòu)可以分為鄰接矩陣和鄰接鏈表的形式。則圖的搜索分為廣度優(yōu)先搜索（BSF -- Breadth First Search）和深度優(yōu)先搜索（DFS -- Depth First Search）。下面這個(gè)圖的結(jié)構(gòu)就是我們要存儲(chǔ)以及遍歷的圖。紅色的部分就是每條邊的權(quán)值。

 

二、鄰接矩陣

接下來(lái)我們就將上面這個(gè)圖存儲(chǔ)下來(lái)，當(dāng)然是使用我們上面提到過(guò)的鄰接矩陣或者鄰接鏈表來(lái)存儲(chǔ)。在構(gòu)建圖之前呢，我們依然要先定義圖的協(xié)議，因?yàn)閳D的物理存儲(chǔ)結(jié)構(gòu)分為鄰接矩陣和鄰接鏈表。不同的存儲(chǔ)方式也就對(duì)應(yīng)著構(gòu)建圖的方式不同，那么圖的BFS與DFS的具體實(shí)現(xiàn)也是不同的，但是對(duì)外的接口是一致的。還是那句話，面向接口編程。所以我們要先定義完圖的相