Python 圖_系列之基于<鏈接表>實(shí)現(xiàn)無向圖最短路徑搜索

圖的常用存儲(chǔ)方式有 2 種：

鄰接矩陣

鏈接表

鄰接矩陣的優(yōu)點(diǎn)和缺點(diǎn)都很明顯。優(yōu)點(diǎn)是簡單、易理解，對(duì)于大部分圖結(jié)構(gòu)而言，都是稀疏的，使用炬陣存儲(chǔ)空間浪費(fèi)就較大。

鏈接表的存儲(chǔ)相比較鄰接矩陣，使用起來更方便，對(duì)于空間的使用是剛好夠用原則，不會(huì)產(chǎn)生太多空間浪費(fèi)。操作起來，也是簡單。

本文將以方式存儲(chǔ)圖結(jié)構(gòu)，在此基礎(chǔ)上實(shí)現(xiàn)無向圖最短路徑搜索。

1. 鏈接表

鏈接表的存儲(chǔ)思路：

使用鏈接表實(shí)現(xiàn)圖的存儲(chǔ)時(shí)，有主表和子表概念。

主表：用來存儲(chǔ)圖對(duì)象中的所有頂點(diǎn)數(shù)據(jù)。

子表：每一個(gè)頂點(diǎn)自身會(huì)維護(hù)一個(gè)子表，用來存儲(chǔ)與其相鄰的所有頂點(diǎn)數(shù)據(jù)。

如下圖結(jié)構(gòu)中有 5 個(gè)頂點(diǎn)，使用鄰接表保存時(shí)，會(huì)有主表 1 張，子表 5 張。鏈接表的優(yōu)點(diǎn)是能夠緊湊地表示稀疏圖。

在中可以使用列表嵌套實(shí)現(xiàn)鄰接表，這應(yīng)該是最簡單的表達(dá)方式。

在此基礎(chǔ)上，可以做一些簡單的常規(guī)操作。

查詢所有頂點(diǎn)：

查詢頂點(diǎn)及其相鄰頂點(diǎn)：

當(dāng)頂點(diǎn)和相鄰頂點(diǎn)之間的關(guān)系很復(fù)雜時(shí)，這種層層嵌套的存儲(chǔ)格式會(huì)讓人眼花繚亂。即使要使用這種嵌套方式，那也應(yīng)該選擇中的字典類型，對(duì)于查詢會(huì)方便很多。

如上結(jié)構(gòu)，在查詢時(shí)，無論是方便性還是性能，都要強(qiáng)于完全的列表方案。

查詢所有頂點(diǎn)：

查詢與某一頂點(diǎn)相鄰的頂點(diǎn)時(shí)，只需要提供頂點(diǎn)名稱就可以了。

以上的存儲(chǔ)方案，適合于演示，并不適合于開發(fā)環(huán)境，因頂點(diǎn)本身是具有特定的數(shù)據(jù)含義（如，可能是城市、公交車站、網(wǎng)址、路由器……），且以上存儲(chǔ)方案讓頂點(diǎn)和其相鄰頂點(diǎn)的信息過度耦合，在實(shí)際運(yùn)用時(shí)，會(huì)牽一發(fā)而動(dòng)全身。

也許一個(gè)微不足道的修改，會(huì)波動(dòng)到整個(gè)結(jié)構(gòu)的更新。

所以，有必要引于 設(shè)計(jì)理念，讓頂點(diǎn)和圖有各自特定數(shù)據(jù)結(jié)構(gòu)，通過 2 種類類型可以更好地體現(xiàn)圖是頂點(diǎn)的集合，頂點(diǎn)和頂點(diǎn)之間的多對(duì)多關(guān)系。

項(xiàng)點(diǎn)類：

頂點(diǎn)類結(jié)構(gòu)說明：

：用于搜索路徑算法中，檢查節(jié)點(diǎn)是否已經(jīng)被搜索過。

：存儲(chǔ)與項(xiàng)點(diǎn)相鄰的頂點(diǎn)信息。這里使用了字典，以頂點(diǎn)為鍵，權(quán)重為值。

圖類：

圖類結(jié)構(gòu)說明：

：使用隊(duì)列模擬?；蜿?duì)列。用于路徑搜索過程中保存臨時(shí)數(shù)據(jù)。

怎么使用列表模擬隊(duì)列或棧？

列表有 、 2 個(gè)很價(jià)值的方法。

用來向列表中添加數(shù)據(jù)，且每次都是從列表最后面添加。

默認(rèn)從列表最后面刪除且彈出數(shù)據(jù)， 可以提供索引值用來從指定位置刪除且彈出數(shù)據(jù)。

使用 和 方法就能模擬棧，從同一個(gè)地方進(jìn)出數(shù)據(jù)。

使用 和 方法就能模擬隊(duì)列，從后面添加數(shù)據(jù)，從最前面獲取數(shù)據(jù)

：用于保存搜索到的路徑數(shù)據(jù)。

2. 最短路徑算法

從圖結(jié)構(gòu)可知，從一個(gè)頂點(diǎn)到達(dá)另一個(gè)頂點(diǎn)，可不止一條可行路徑，在眾多路徑我們總是試圖選擇一條最短路徑，當(dāng)然，需求不同，衡量一個(gè)路徑是不是最短路徑的標(biāo)準(zhǔn)也會(huì)不同。

如打開導(dǎo)航系統(tǒng)后，最短路徑可能是費(fèi)用最少的那條，可能是速度最快的那條，也可能是量程數(shù)最少的或者是紅綠燈是最少的……

在中，以經(jīng)過的邊數(shù)最少的路徑為最短路徑。

在有向加權(quán)圖中，會(huì)以附加在每條邊上的權(quán)重的數(shù)據(jù)含義來衡量。權(quán)重可以是時(shí)間、速度、量程數(shù)……

2.1 無向圖最短路徑算法

查找無向圖中任意兩個(gè)頂點(diǎn)間的最短路徑長度，可以直接使用廣度搜索算法。如下圖求解 的最短路徑。

Tips：無向圖中任意 2 個(gè)頂點(diǎn)間的最短路徑長度由邊數(shù)決定。

廣度優(yōu)先搜索算法流程：

廣度優(yōu)先搜索算法的基本原則：以某一頂點(diǎn)為參考點(diǎn)，先搜索離此頂點(diǎn)最近的頂點(diǎn)，再搜索離最近頂點(diǎn)最近的頂點(diǎn)……以此類推，一層一層向目標(biāo)頂點(diǎn)推進(jìn)。

如從頂點(diǎn) 找到頂點(diǎn) 。先從離 最近的頂點(diǎn) 、 找起，如果沒找到，再找離 、 最近的頂點(diǎn) 、，如果還是沒有找到，再找離 、 最近的頂點(diǎn) 。

因?yàn)槊恳淮嗡阉鞫际遣捎米罱瓌t，最后搜索到的目標(biāo)也一定是最近的路徑。

也因?yàn)椴捎米罱瓌t，所以搜索過程中，在搜索過程中所經(jīng)歷到的每一個(gè)頂點(diǎn)的路徑都是最短路徑。。

顯然，廣度優(yōu)先搜索的最近搜索原則是符合先進(jìn)先出思想的，具體算法實(shí)施時(shí)可以借助隊(duì)列實(shí)現(xiàn)整個(gè)過程。

算法流程：

先確定起始點(diǎn) 。

找到 的 2 個(gè)后序頂點(diǎn) 、 （或者說 的前序頂點(diǎn)是 ），壓入隊(duì)列中。除去起點(diǎn) ，、 頂點(diǎn)屬于第一近壓入隊(duì)列的節(jié)點(diǎn)。

和 壓入隊(duì)列的順序并不影響 ~ 或 ~ 的路徑距離（都是 1）。

~ 的最短路徑長度為 1

~ 的最短路徑長度為 1

從隊(duì)列中搜索 時(shí)，找到 的后序頂點(diǎn) 并壓入隊(duì)列。 是 的前序頂點(diǎn)。

~ 的最短路徑長度為 1，而又因?yàn)?~ 的最短路徑長度為 1 ，所以 ~ 的最短路徑為 2

搜索完畢后，在隊(duì)列中搜索 時(shí)，找到 的后序頂點(diǎn) ，壓入隊(duì)列。因 和 屬于第一近頂點(diǎn)，所以這 2 個(gè)頂點(diǎn)的后序頂點(diǎn) 、 屬于第二近壓入隊(duì)列，或說 、 的路徑距離是相同的（都為 2）。

當(dāng)搜索到 時(shí)，沒有后序頂點(diǎn)，此時(shí)隊(duì)列沒有壓入操作。

當(dāng) 搜索到 時(shí)， 有 2 個(gè)后序頂點(diǎn) 、，因 已經(jīng)壓入過，所以僅壓入 。因 是由第二近頂點(diǎn)壓入，所以 是屬于第三近壓入頂點(diǎn)。

的路徑為 3。

編碼實(shí)現(xiàn)廣度優(yōu)先算法：

在頂點(diǎn)類中添加如下幾個(gè)方法：

頂點(diǎn)類用來構(gòu)造一個(gè)新頂點(diǎn)，并維護(hù)與相鄰頂點(diǎn)的關(guān)系。

對(duì)圖類中的方法做一下詳細(xì)解釋：

初始化方法：

為圖添加新頂點(diǎn)方法：

頂點(diǎn)的編號(hào)由圖對(duì)象內(nèi)部指定，便于統(tǒng)一管理。

所有頂點(diǎn)保存在一個(gè)字典中，以頂點(diǎn)名稱為鍵，頂點(diǎn)對(duì)象為值。也可以使用列表直接保存頂點(diǎn)，根據(jù)需要決定。

提供一個(gè)根據(jù)頂點(diǎn)名稱返回頂點(diǎn)的方法：

添加頂點(diǎn)與相鄰頂點(diǎn)的關(guān)系：此方法屬于一個(gè)封裝方法，本質(zhì)是調(diào)用頂點(diǎn)自身的添加相鄰頂點(diǎn)方法。

圖中核心方法：用來廣度優(yōu)先搜索算法查找頂點(diǎn)與頂點(diǎn)之間的路徑

廣度優(yōu)先搜索算法有一個(gè)核心點(diǎn)，當(dāng)搜索到某一個(gè)頂點(diǎn)后，需要找到與此頂點(diǎn)相鄰的其它頂點(diǎn)，并壓入隊(duì)列中。 方法就是做些事情的。如果某一個(gè)頂點(diǎn)曾經(jīng)進(jìn)過隊(duì)列，就不要再重復(fù)壓入隊(duì)列了。

測(cè)試代碼：

輸出結(jié)果：

廣度優(yōu)先搜索算法也可以使用遞歸方案：

在無向圖中，查找起始點(diǎn)到目標(biāo)點(diǎn)的最短路徑，使用廣度優(yōu)先搜索算法便可實(shí)現(xiàn)，但如果是有向加權(quán)圖，可能不會(huì)稱心如愿。因有向加權(quán)圖中的邊是有權(quán)重的。所以對(duì)于有向加權(quán)圖則需要另擇方案。

3. 總結(jié)

圖數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)過程中會(huì)涉及到其它數(shù)據(jù)結(jié)構(gòu)的運(yùn)用。學(xué)習(xí)、使用圖數(shù)據(jù)結(jié)構(gòu)對(duì)其它數(shù)據(jù)結(jié)構(gòu)有重新認(rèn)識(shí)和鞏固作用。

關(guān)鍵詞： Python 圖_系列之基于鏈接表實(shí)現(xiàn)無向圖最短路徑搜索