《數(shù)據(jù)結(jié)構(gòu)Python 語言描述》 第7章

第7章圖簽到掃碼下載文旌課堂APP掃碼簽到（202X.X.XXXX:00至202X.X.XXXX:10）簽到方式教師通過“文旌課堂APP”生成簽到二維碼，并設(shè)置簽到時(shí)間，學(xué)生通過“文旌課堂APP”掃描“簽到二維碼”進(jìn)行簽到。。圖本章導(dǎo)讀圖形結(jié)構(gòu)簡稱圖，是一種比樹型結(jié)構(gòu)更復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，它可以用于描述各種復(fù)雜的數(shù)據(jù)對(duì)象，在系統(tǒng)工程、計(jì)算機(jī)科學(xué)、數(shù)學(xué)等多個(gè)領(lǐng)域都有著廣泛的應(yīng)用。本章首先介紹圖的定義及基本術(shù)語，然后介紹圖的基本操作、存儲(chǔ)結(jié)構(gòu)及遍歷方法，最后介紹圖的應(yīng)用，包括最小生成樹、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑。

第7章圖知識(shí)目標(biāo)

第7章 理解圖的定義、基本術(shù)語和基本操作。 掌握圖的兩種存儲(chǔ)結(jié)構(gòu)，包括鄰接矩陣和鄰接表。 掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷方法。 掌握圖的應(yīng)用，包括最小生成樹、最短路徑、拓?fù)渑判蚝完P(guān)鍵路徑。圖技能目標(biāo)

第7章 能利用圖解決實(shí)際應(yīng)用中的最短路徑問題。 能利用AOE網(wǎng)預(yù)估一個(gè)工程的完工時(shí)間。圖素質(zhì)目標(biāo)

第7章 強(qiáng)化學(xué)習(xí)意識(shí)，努力提高應(yīng)用理論知識(shí)解決實(shí)際問題的能力。 樹立全局意識(shí)，學(xué)會(huì)抓住關(guān)鍵，并利用關(guān)鍵環(huán)節(jié)掌控全局進(jìn)展。Content第7章圖的存儲(chǔ)結(jié)構(gòu)圖概述圖的遍歷最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵路徑7.1圖概述第7章圖7.1圖概述圖（graph）由頂點(diǎn)及描述頂點(diǎn)之間關(guān)系的邊的有限集合組成，其形式化定義為G=(V,E)。其中，V是圖G中頂點(diǎn)的有限集合（頂點(diǎn)集），記為V(G)；E是連接V中兩個(gè)不同頂點(diǎn)的邊的有限集合（邊集），記為E(G)。E(G)可以為空集，當(dāng)E(G)為空集時(shí)，圖G只有頂點(diǎn)而沒有邊。對(duì)于圖G，如果其中的邊為無向邊，即兩個(gè)頂點(diǎn)之間的邊沒有方向，則稱圖G為無向圖；如果其中的邊為有向邊，即兩個(gè)頂點(diǎn)之間的邊有方向，則稱圖G為有向圖。7.1.1圖的定義7.1圖概述在無向圖中，頂點(diǎn)對(duì)通常用圓括號(hào)“()”括起來，以表示一條無向邊。例如，<v0,v1>表示與頂點(diǎn)v0和頂點(diǎn)v1相關(guān)聯(lián)的一條無向邊。由此可見，<v0,v1>和(v1,v0)是同一條邊。而在有向圖中，頂點(diǎn)對(duì)通常用尖括號(hào)“<>”括起來，以表示一條有向邊。例如，<v0,v1>表示從頂點(diǎn)v0到頂點(diǎn)v1的一條有向邊，<v1,v0>表示從頂點(diǎn)v1到頂點(diǎn)v0的一條有向邊。由此可見，<v0,v1>和<v1,v0>是兩條不同的邊。例如，無向圖G1頂點(diǎn)集V(G1)={A,B,C,D}，邊集E(G1)={(A,B),(A,C),(B,C),(C,D)}；有向圖G2頂點(diǎn)集V(G2)={A,B,C,D}，邊集E(G2)={<A,B>,<A,C>,<B,C>,<C,D>}。7.1圖概述提示在有向圖中，<v0,v1>又稱為弧，其中v0是弧尾，v1是弧頭。7.1圖概述7.1.2圖的基本術(shù)語1．無向完全圖和有向完全圖對(duì)于一個(gè)無向圖，如果圖中任意兩個(gè)頂點(diǎn)之間都存在一條邊，則稱該無向圖為無向完全圖。對(duì)于一個(gè)有向圖，如果圖中任意兩個(gè)頂點(diǎn)之間都存在兩條方向相反的邊，則稱該有向圖為有向完全圖。例如，下圖為無向完全圖和有向完全圖。7.1圖概述2．子圖對(duì)于兩個(gè)圖G=(V,E)和G‘=(V’,E‘)，如果V’是V的子集，E‘是E的子集，則稱圖G’是圖G的子圖。例如，下圖為上圖無向完全圖和有向完全圖的子圖。7.1圖概述3．稀疏圖和稠密圖有較少條邊的圖稱為稀疏圖，反之稱為稠密圖。4．鄰接點(diǎn)對(duì)于無向圖G=(V,E)，如果邊(v0,v1)∈E，則稱頂點(diǎn)v0與頂點(diǎn)v1互為鄰接點(diǎn)，即頂點(diǎn)v0與頂點(diǎn)v1相鄰接；同時(shí)稱邊(v0,v1)依附于頂點(diǎn)v0和頂點(diǎn)v1，或者說邊(v0,v1)與頂點(diǎn)v0和頂點(diǎn)v1相關(guān)聯(lián)。對(duì)于有向圖G=(V,E)，如果邊<v0,v1>∈E，則稱頂點(diǎn)v0鄰接到頂點(diǎn)v1，頂點(diǎn)v1鄰接自頂點(diǎn)v0；同時(shí)稱邊<v0,v1>依附于頂點(diǎn)v0和頂點(diǎn)v1，或者說邊<v0,v1>與頂點(diǎn)v0和頂點(diǎn)v1相關(guān)聯(lián)。7.1圖概述5．頂點(diǎn)的度、入度和出度對(duì)于無向圖，頂點(diǎn)v的度是指與頂點(diǎn)v相關(guān)聯(lián)的邊的數(shù)目，記作TD(v)。對(duì)于有向圖，頂點(diǎn)v的度分為入度和出度。其中，入度是以頂點(diǎn)v為弧頭的弧的數(shù)目，記作ID(v)；出度是以頂點(diǎn)v為弧尾的弧的數(shù)目，記作OD(v)，因此，頂點(diǎn)v的度TD(v)=ID(v)+OD(v)。7.1圖概述6．權(quán)和網(wǎng)在實(shí)際應(yīng)用中，圖的邊往往具有一定意義且會(huì)被賦予相應(yīng)的數(shù)值，該數(shù)值稱為該邊的權(quán)（也稱為權(quán)值）。這種帶權(quán)的圖稱為網(wǎng)。例如，在交通網(wǎng)中用頂點(diǎn)表示城市時(shí)，邊的權(quán)可以表示兩個(gè)城市之間的距離，如下圖所示。7.1圖概述7．路徑和路徑長度8．回路或環(huán)若一條路徑中的開始頂點(diǎn)和結(jié)束頂點(diǎn)相同，則稱該路徑為回路或環(huán)。對(duì)于圖G=(V,E)，從頂點(diǎn)v出發(fā)到達(dá)頂點(diǎn)v'的一條路徑是一個(gè)頂點(diǎn)序列(v,v0,v1,…,vm,v')。其中，若G為無向圖，則邊(v,v0)、(v0,v1)、…、(vm,v')∈E；若G為有向圖，則邊<v,v0>、<v0,v1>、…、<vm,v'

>∈E。一條路徑中經(jīng)過的邊的數(shù)目稱為路徑長度。7.1圖概述9．簡單路徑、簡單回路或簡單環(huán)頂點(diǎn)序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除了開始頂點(diǎn)和結(jié)束頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡單回路或簡單環(huán)。10．連通、連通圖和連通分量對(duì)于無向圖G=(V,E)，如果從頂點(diǎn)v0到頂點(diǎn)v1有路徑，則稱頂點(diǎn)v0和頂點(diǎn)v1是連通的。如果圖G中任意兩個(gè)頂點(diǎn)都是連通的，則稱圖G為連通圖，否則稱為非連通圖。無向圖中的極大連通子圖稱為無向圖的連通分量。7.1圖概述提示在無向圖中，若某一個(gè)連通子圖不包含在其他連通子圖內(nèi)，則稱該連通子圖為極大連通子圖。也就是說，與該連通子圖中某頂點(diǎn)連通的所有頂點(diǎn)必包含在該連通子圖中。顯然，連通圖的極大連通子圖只有其自身一個(gè)，而非連通圖的極大連通子圖有多個(gè)。7.1圖概述11．強(qiáng)連通圖和強(qiáng)連通分量對(duì)于有向圖G=(V,E)，如果從頂點(diǎn)v0到頂點(diǎn)v1、從頂點(diǎn)v1到頂點(diǎn)v0都有路徑，則稱圖G為強(qiáng)連通圖，否則稱為非強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。7.1圖概述12．連通圖的生成樹一個(gè)連通圖的生成樹是指該連通圖的一個(gè)極小連通子圖，它含有圖中的全部頂點(diǎn)（頂點(diǎn)個(gè)數(shù)為n），但只有足以構(gòu)成一棵樹的n-1條邊。7.1圖概述提示極小連通子圖既要保證圖的流暢，又要使圖的邊數(shù)最少。如果一個(gè)無向圖有n個(gè)頂點(diǎn)和少于n-1條邊，則該圖是非連通圖；如果一個(gè)無向圖有n個(gè)頂點(diǎn)和多于n-1條邊，則該圖中一定有回路。值得注意的是，有n個(gè)頂點(diǎn)和n-1條邊的圖不一定是生成樹。圖基本操作的定義如表7-1所示。7.1.3圖的基本操作7.1圖概述基本操作說明createGraph()構(gòu)造圖locateVex(v)已知圖存在，若圖中存在頂點(diǎn)v，則返回頂點(diǎn)v在圖中的位置；否則返回0getVex(v)已知圖存在，v是圖中的某個(gè)頂點(diǎn)，返回v的值putVex(v,value)已知圖存在，v是圖中的某個(gè)頂點(diǎn)，將value值賦給vfirstAdjVex(v)已知圖存在，v是圖中的某個(gè)頂點(diǎn)，返回v的第一個(gè)鄰接點(diǎn)；若v無鄰接點(diǎn)，則返回NonenextAdjVex(v,w)已知圖存在，v是圖中的某個(gè)頂點(diǎn)，w是v的鄰接點(diǎn)，返回v的相對(duì)于w的下一個(gè)鄰接點(diǎn)；若w是v的最后一個(gè)鄰接點(diǎn)，則返回NoneinsertVex(v)已知圖存在，在圖中插入一個(gè)新頂點(diǎn)vdeleteVex(v)已知圖存在，v是圖中的某個(gè)頂點(diǎn)，刪除頂點(diǎn)v及與其相關(guān)聯(lián)的邊insertArc(v,w)已知圖存在，v和w是圖中的兩個(gè)頂點(diǎn)，在圖中增加一條從頂點(diǎn)v到頂點(diǎn)w的邊deleteArc(v,w)已知圖存在，v和w是圖中的兩個(gè)頂點(diǎn)，刪除圖中從頂點(diǎn)v到頂點(diǎn)w的邊dfsTraverse()已知圖存在，對(duì)圖進(jìn)行深度優(yōu)先遍歷bfsTraverse()已知圖存在，對(duì)圖進(jìn)行廣度優(yōu)先遍歷表7-1圖基本操作的定義7.2圖的存儲(chǔ)結(jié)構(gòu)第7章圖7.2圖的存儲(chǔ)結(jié)構(gòu)7.2.1鄰接矩陣1．鄰接矩陣表示法鄰接矩陣表示法也稱數(shù)組表示法，通常采用二維數(shù)組存儲(chǔ)圖中各頂點(diǎn)之間的鄰接關(guān)系。（1）假設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，則它的鄰接矩陣是一個(gè)n×n的方陣，定義如下。7.2圖的存儲(chǔ)結(jié)構(gòu)例如，鄰接矩陣如下圖所示。（2）假設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是一個(gè)n×n的方陣，定義如下。7.2圖的存儲(chǔ)結(jié)構(gòu)其中，表示頂點(diǎn)i和頂點(diǎn)j之間邊的權(quán)值。圖的鄰接矩陣類的定義如下。classALGraph: #圖的鄰接矩陣類

GRAPHKIND_UDG='UDG' #無向圖7.2圖的存儲(chǔ)結(jié)構(gòu)GRAPHKIND_DG='DG' #有向圖

GRAPHKIND_UDN='UDN' #無向網(wǎng)

GRAPHKIND_DN='DN' #有向網(wǎng)

def__init__(self,kind=None,vNum=0,eNum=0,v=None,e=None):self.kind=kind #圖的類別

self.vNum=vNum #圖的頂點(diǎn)數(shù)

self.eNum=eNum #圖的邊數(shù)

self.v=v #頂點(diǎn)列表

self.e=e #鄰接矩陣7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣表示法的特點(diǎn)如下。（1）圖的鄰接矩陣是唯一的。（2）根據(jù)鄰接矩陣很容易判斷任意兩個(gè)頂點(diǎn)之間是否有邊，且時(shí)間復(fù)雜度為O(1)。（3）對(duì)于無向圖，鄰接矩陣第i（0≤i≤n-1）行非零元素（或非∞元素）的個(gè)數(shù)是頂點(diǎn)vi的度；對(duì)于有向圖，第i（0≤i≤n-1）行非零元素（或非∞元素）的個(gè)數(shù)是頂點(diǎn)vi的出度，第i（0≤i≤n-1）列非零元素（或非∞元素）的個(gè)數(shù)是頂點(diǎn)vi的入度。7.2圖的存儲(chǔ)結(jié)構(gòu)（4）鄰接矩陣中增加和刪除頂點(diǎn)的操作不易實(shí)現(xiàn)。（5）要統(tǒng)計(jì)圖中邊的總數(shù)，需要掃描鄰接矩陣中的所有元素，其時(shí)間復(fù)雜度為O(n2)。（6）如果是有向圖，n個(gè)頂點(diǎn)需要n2個(gè)存儲(chǔ)單元存儲(chǔ)邊；如果是無向圖，因其鄰接矩陣是一個(gè)對(duì)稱矩陣，因此在頂點(diǎn)數(shù)n很大時(shí)，可以采用對(duì)稱矩陣的壓縮存儲(chǔ)方法，僅存儲(chǔ)下三角（或上三角）的元素［需要n(n-1)/2個(gè)存儲(chǔ)單元］，從而減小存儲(chǔ)空間。但無論以什么方式存儲(chǔ)，鄰接矩陣表示法的空間復(fù)雜度均為O(n2)，因此更適合存儲(chǔ)稠密圖。7.2圖的存儲(chǔ)結(jié)構(gòu)2．鄰接矩陣中基本操作的實(shí)現(xiàn)1）返回頂點(diǎn)在圖中的位置該算法是根據(jù)頂點(diǎn)的值獲取其在頂點(diǎn)集中的位置，若頂點(diǎn)不存在，則返回-1。deflocateVex(self,x):foriinrange(self.vNum): #查找頂點(diǎn)信息

ifself.v[i]==x: #如果頂點(diǎn)的值為x，返回其位置

returnireturn-1 #否則返回-1【算法描述】7.2圖的存儲(chǔ)結(jié)構(gòu)2）創(chuàng)建圖下面以創(chuàng)建無向網(wǎng)為例，介紹創(chuàng)建圖的方法，其具體步驟如下。（1）輸入圖的頂點(diǎn)數(shù)和邊數(shù)。（2）依次輸入頂點(diǎn)信息并將其存入頂點(diǎn)集中。（3）初始化鄰接矩陣，將每條邊的權(quán)值初始化為極大值（∞）。（4）構(gòu)造鄰接矩陣。依次輸入每條邊依附的頂點(diǎn)及邊的權(quán)值，確定兩個(gè)頂點(diǎn)在圖中的位置后，為邊賦相應(yīng)的權(quán)值，同時(shí)為其對(duì)稱邊也賦相同的權(quán)值。importsys #sys模塊提供了與python解釋器緊密相關(guān)的一些變量和函數(shù)defcreateUDN(self,vNum,eNum,v,e): #創(chuàng)建無向網(wǎng)

self.vNum=vNum #圖的頂點(diǎn)數(shù)【算法描述】7.2圖的存儲(chǔ)結(jié)構(gòu)self.eNum=eNum #圖的邊數(shù)

self.v=[None]*vNum #構(gòu)造頂點(diǎn)集

foriinrange(vNum): #輸入頂點(diǎn)信息

self.v[i]=v[i] self.e=[[sys.maxsize]*vNum]*vNum #初始化鄰接矩陣

foriinrange(eNum): #構(gòu)造鄰接矩陣

a,b,w=e[i] #輸入每條邊依附的頂點(diǎn)及權(quán)值

#返回頂點(diǎn)在圖中的位置

m,n=self.locateVex(a),self.locateVex(b) #為邊(a,b)及邊(b,a)賦權(quán)值

self.e[m][n]=self.e[n][m]=w若要建立無向圖，只需對(duì)上述算法進(jìn)行如下兩處修改。（1）初始化鄰接矩陣時(shí)，將每條邊的權(quán)值初始化為0。（2）構(gòu)造鄰接矩陣時(shí)，將每條邊的權(quán)值賦值為1。同樣，創(chuàng)建有向網(wǎng)或有向圖時(shí)，也可通過對(duì)上述算法進(jìn)行簡單修改實(shí)現(xiàn)，感興趣的讀者可自行完成。高手點(diǎn)撥7.2圖的存儲(chǔ)結(jié)構(gòu)7.2圖的存儲(chǔ)結(jié)構(gòu)3）輸出圖該算法是輸出圖的鄰接矩陣。defdisGraph(self):foriinrange(self.vNum): forjinrange(self.vNum):ifself.e[i][j]==sys.maxsize: #如果權(quán)值為極大值

print('%4s'%('∞'),end='') #輸出∞

else: #輸出權(quán)值

print('%5d'%(self.e[i][j]),end='')print() #換行【算法描述】7.2圖的存儲(chǔ)結(jié)構(gòu)7.2.2鄰接表1．鄰接表表示法鄰接表表示法是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接表中，對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，將與該頂點(diǎn)相鄰的頂點(diǎn)鏈接到該單鏈表中。也就是說，具有n個(gè)頂點(diǎn)的圖，頂點(diǎn)間的鄰接關(guān)系可構(gòu)成n個(gè)單鏈表，其中第i（0≤i≤n-1）個(gè)單鏈表由所有鄰接于頂點(diǎn)vi的頂點(diǎn)鏈接而成。鄰接表中每個(gè)單鏈表的第一個(gè)結(jié)點(diǎn)（表頭結(jié)點(diǎn)）存放有關(guān)頂點(diǎn)的信息，以便于隨機(jī)訪問任一頂點(diǎn)的單鏈表，其余結(jié)點(diǎn)存放有關(guān)邊的信息。7.2圖的存儲(chǔ)結(jié)構(gòu)（1）表頭結(jié)點(diǎn)的結(jié)構(gòu)如下圖所示。其中，data域用于存儲(chǔ)頂點(diǎn)vi的名稱或其他信息，firstarc域用于指向單鏈表中除表頭結(jié)點(diǎn)外的第一個(gè)結(jié)點(diǎn)（即與頂點(diǎn)vi相鄰接的第一個(gè)頂點(diǎn)）。在鄰接表中，假設(shè)表頭結(jié)點(diǎn)為HNode類對(duì)象，則表頭結(jié)點(diǎn)的定義如下。classHNode:def__init__(self,data):self.data=data #頂點(diǎn)的名稱或其他信息

self.firstarc=None#指向單鏈表中除表頭結(jié)點(diǎn)外的第一個(gè)結(jié)點(diǎn)7.2圖的存儲(chǔ)結(jié)構(gòu)（2）邊結(jié)點(diǎn)的結(jié)構(gòu)如下圖所示。無權(quán)圖的邊結(jié)點(diǎn)包括兩部分。其中，adjvex域用于存儲(chǔ)與頂點(diǎn)vi相鄰接的頂點(diǎn)在頂點(diǎn)數(shù)組中的下標(biāo)，nextarc域用于指向與頂點(diǎn)vi相鄰接的下一個(gè)頂點(diǎn)。相較于無權(quán)圖，有權(quán)圖的邊結(jié)點(diǎn)需要額外增加一個(gè)info域存儲(chǔ)邊相關(guān)的信息，如權(quán)值。假設(shè)邊結(jié)點(diǎn)為ArcNode類對(duì)象，則邊結(jié)點(diǎn)的定義如下。classArcNode:def__init__(self,adjVex,info):self.adjVex=adjVex #頂點(diǎn)的鄰接點(diǎn)在頂點(diǎn)數(shù)組中的下標(biāo)

=info #邊的權(quán)值

self.nextarc=None #與頂點(diǎn)相鄰接的下一個(gè)頂點(diǎn)7.2圖的存儲(chǔ)結(jié)構(gòu)為此，可以對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)以頂點(diǎn)vi為弧頭的單鏈表。這樣，在逆鄰接表中第i（0≤i≤n-1）個(gè)單鏈表中邊結(jié)點(diǎn)的個(gè)數(shù)就是頂點(diǎn)vi的入度。對(duì)于無向圖，鄰接表中第i（0≤i≤n-1）個(gè)單鏈表中邊結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的度。對(duì)于有向圖，鄰接表中第i（0≤i≤n-1）個(gè)單鏈表中邊結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的出度，但要求頂點(diǎn)vi的入度必須遍歷整個(gè)鄰接表。7.2圖的存儲(chǔ)結(jié)構(gòu)鄰接表表示法的特點(diǎn)如下。（1）圖的鄰接表是不唯一的。（2）在鄰接表中，無法很快判斷任意兩個(gè)頂點(diǎn)之間是否有邊，且最壞時(shí)間復(fù)雜度為O(n)。（3）鄰接表中增加和刪除頂點(diǎn)的操作很容易實(shí)現(xiàn)。（4）要統(tǒng)計(jì)圖中邊的總數(shù)，按單鏈表順序掃描所有邊即可，其時(shí)間復(fù)雜度為O(n+e)。（5）對(duì)n個(gè)頂點(diǎn)e條邊的圖，若該圖為無向圖，則在其鄰接表表示中有n個(gè)表頭結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)；若該圖為有向圖，則在其鄰接表表示中有n個(gè)表頭結(jié)點(diǎn)和e個(gè)邊結(jié)點(diǎn)。因此，鄰接表表示法的空間復(fù)雜度為O(n+e)，更適合存儲(chǔ)稀疏圖。7.2圖的存儲(chǔ)結(jié)構(gòu)2．鄰接表中基本操作的實(shí)現(xiàn)1）返回頂點(diǎn)在圖中的位置該算法是根據(jù)頂點(diǎn)的值獲取其在頂點(diǎn)集中的位置，若頂點(diǎn)不存在，則返回-1。deflocateVex(self,x):foriinrange(self.vNum): #查找頂點(diǎn)信息

ifself.v[i].data==x: #如果頂點(diǎn)的值為x，返回其位置

returnireturn-1 #否則返回-1【算法描述】7.2圖的存儲(chǔ)結(jié)構(gòu)2）創(chuàng)建圖下面以創(chuàng)建無向圖為例，介紹創(chuàng)建圖的方法，其具體步驟如下。（1）構(gòu)造表頭結(jié)點(diǎn)，初始化表頭結(jié)點(diǎn)的指針域?yàn)镹one。（2）創(chuàng)建鄰接表。依次輸入每條邊依附的兩個(gè)頂點(diǎn)，并確認(rèn)頂點(diǎn)在圖中的位置，然后插入邊結(jié)點(diǎn)。defcreateUDG(self): #創(chuàng)建無向圖

v=self.vself.v=[None]*self.vNum #構(gòu)造表頭結(jié)點(diǎn)

foriinrange(self.vNum):self.v[i]=HNode(v[i]) #生成一個(gè)新的結(jié)點(diǎn)表7.2圖的存儲(chǔ)結(jié)構(gòu)foriinrange(self.eNum):a,b=self.e[i] #輸入每條邊依附的兩個(gè)頂點(diǎn)

#返回頂點(diǎn)在圖中的位置

u,v=self.locateVex(a),self.locateVex(b)self.addArc(u,v,1) #插入邊結(jié)點(diǎn)

self.addArc(v,u,1) #插入另一個(gè)對(duì)稱的邊結(jié)點(diǎn)若要?jiǎng)?chuàng)建有向圖，只需對(duì)上述算法進(jìn)行簡單修改，即僅需生成一個(gè)邊結(jié)點(diǎn)，并將其插入表頭結(jié)點(diǎn)后面。高手點(diǎn)撥7.2圖的存儲(chǔ)結(jié)構(gòu)3）插入邊結(jié)點(diǎn)該算法是指在單鏈表中插入一個(gè)頂點(diǎn)i指向頂點(diǎn)j的權(quán)值為e的邊結(jié)點(diǎn)。采用頭插法插入邊結(jié)點(diǎn)的算法如下。defaddArc(self,i,j,e):arc=ArcNode(j,e) #生成新結(jié)點(diǎn)

'''頭插法插入邊結(jié)點(diǎn)'''arc.nextarc=self.v[i].firstarc self.v[i].firstarc=arc7.3圖的遍歷第7章圖7.3圖的遍歷7.3.1深度優(yōu)先遍歷圖的深度優(yōu)先遍歷類似于樹的先根遍歷，其步驟如下。（1）從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問該頂點(diǎn)。（2）找出剛訪問過的頂點(diǎn)的第一個(gè)未被訪問的鄰接點(diǎn)，訪問該鄰接點(diǎn)。以該鄰接點(diǎn)為新頂點(diǎn)，重復(fù)步驟（2），直到剛訪問過的頂點(diǎn)沒有未被訪問的鄰接點(diǎn)。（3）退回到上一個(gè)訪問過且還有未被訪問的鄰接點(diǎn)的頂點(diǎn)，繼續(xù)訪問該頂點(diǎn)的下一個(gè)未被訪問的鄰接點(diǎn)。（4）重復(fù)步驟（2）和步驟（3），直到圖中所有頂點(diǎn)均被訪問。提示上述深度優(yōu)先遍歷步驟是針對(duì)連通圖的。若是非連通圖，執(zhí)行上述遍歷步驟后，圖中一定還有未訪問過的頂點(diǎn)，此時(shí)，需要從圖中選擇一個(gè)未訪問過的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述深度優(yōu)先遍歷步驟，直到圖中所有頂點(diǎn)均被訪問。7.3圖的遍歷defdfsTraverse(g): globalvisited #定義全局變量

visited=[False]*g.getVNum() #創(chuàng)建訪問標(biāo)記數(shù)組，并賦初值False'''以每個(gè)頂點(diǎn)作為開始頂點(diǎn)進(jìn)行深度優(yōu)先遍歷'''foriinrange(g.getVNum()): ifnotvisited[i]: #如果頂點(diǎn)未被訪問

dFS(g,i) #訪問頂點(diǎn)并進(jìn)行遍歷

defdFS(g,i):

visited[i]=True #對(duì)訪問過的頂點(diǎn)進(jìn)行標(biāo)記

print(g.getVex(i),end='') #打印訪問過的頂點(diǎn)【算法描述】7.3圖的遍歷v=g.firstAdj(i) #訪問頂點(diǎn)的第一個(gè)鄰接點(diǎn)

whilev!=-1: ifnotvisited[v]: #如果該鄰接點(diǎn)沒有被訪問

dFS(g,v) #重復(fù)執(zhí)行深度優(yōu)先遍歷算法

v=g.nextAdj(i,v) #否則訪問頂點(diǎn)的下一個(gè)鄰接點(diǎn)提示為了在遍歷過程中區(qū)分頂點(diǎn)是否已經(jīng)被訪問，可設(shè)置一個(gè)訪問標(biāo)志數(shù)組visited且為其賦初值False，當(dāng)頂點(diǎn)被訪問過后，將其賦值為True。如果給定的圖是無向連通圖或有向強(qiáng)連通圖，則遍歷一次就能訪問圖中所有頂點(diǎn)，從而得到圖的深度優(yōu)先遍歷序列。7.3圖的遍歷下面具體分析深度優(yōu)先遍歷無向圖的過程。（1）從頂點(diǎn)A出發(fā)，首先訪問頂點(diǎn)A。頂點(diǎn)A的鄰接點(diǎn)有頂點(diǎn)B和頂點(diǎn)F，選擇未被訪問過的鄰接點(diǎn)B，從頂點(diǎn)B繼續(xù)遍歷。（2）訪問頂點(diǎn)B。頂點(diǎn)B的鄰接點(diǎn)有頂點(diǎn)A、頂點(diǎn)C、頂點(diǎn)D和頂點(diǎn)G，選擇未被訪問過的鄰接點(diǎn)C，從頂點(diǎn)C繼續(xù)遍歷。（3）訪問頂點(diǎn)C。由于頂點(diǎn)C的鄰接點(diǎn)只有已被訪問過的頂點(diǎn)B，故退回到頂點(diǎn)B，從頂點(diǎn)B的另一個(gè)未被訪問過的鄰接點(diǎn)D繼續(xù)遍歷。（4）訪問頂點(diǎn)D。頂點(diǎn)D的鄰接點(diǎn)有頂點(diǎn)B、頂點(diǎn)G和頂點(diǎn)E，選擇未被訪問過的鄰接點(diǎn)E，從頂點(diǎn)E繼續(xù)遍歷。（5）訪問頂點(diǎn)E。由于頂點(diǎn)E的鄰接點(diǎn)只有已被訪問過的頂點(diǎn)D，故退回到頂點(diǎn)D，從頂點(diǎn)D的另一個(gè)未被訪問過的鄰接點(diǎn)G繼續(xù)遍歷。（6）訪問頂點(diǎn)G。頂點(diǎn)G的鄰接點(diǎn)有頂點(diǎn)B、頂點(diǎn)D和頂點(diǎn)F，選擇未被訪問過的鄰接點(diǎn)F，從頂點(diǎn)F繼續(xù)遍歷。（7）訪問頂點(diǎn)F。由于頂點(diǎn)F的鄰接點(diǎn)A和G均已被訪問過，故該無向圖遍歷結(jié)束，得到的深度優(yōu)先遍歷序列為A、B、C、D、E、G、F。7.3圖的遍歷提示當(dāng)進(jìn)行深度優(yōu)先遍歷時(shí)，如果一個(gè)頂點(diǎn)有多個(gè)鄰接點(diǎn)，可以任選其一，故圖的深度優(yōu)先遍歷序列不是唯一的。也就是說，對(duì)于如圖7-18所示的無向圖，其深度優(yōu)先遍歷序列也可以為A、B、C、D、G、F、E。7.3圖的遍歷7.3.2廣度優(yōu)先遍歷圖的廣度優(yōu)先遍歷類似于二叉樹的層次遍歷，其步驟如下。（1）從圖中的某個(gè)頂點(diǎn)v出發(fā)，訪問該頂點(diǎn)。（2）依次訪問頂點(diǎn)v的所有未被訪問過的鄰接點(diǎn)。（3）分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問。（4）重復(fù)步驟（3），直到圖中所有頂點(diǎn)均被訪問。defbfsTraverse(g):globalvisited #定義全局變量

visited=[False]*g.getVNum()#創(chuàng)建訪問標(biāo)記數(shù)組，并賦初值Fasle'''以每個(gè)頂點(diǎn)作為開始頂點(diǎn)進(jìn)行廣度優(yōu)先遍歷'''【算法描述】7.3圖的遍歷foriinrange(g.getVNum()):ifnotvisited[i]: #如果頂點(diǎn)未被訪問

bFS(g,i) #訪問頂點(diǎn)并進(jìn)行遍歷defbFS(g,i):q=LinkQueue() #創(chuàng)建輔助隊(duì)列

q.inQueue(i) #將開始頂點(diǎn)插入隊(duì)尾

whilenotq.queueEmpty(): #如果隊(duì)列不為空

u=q.deQueue() #刪除隊(duì)頭元素

visited[u]=True #對(duì)訪問過的頂點(diǎn)進(jìn)行標(biāo)記

print(g.getVex(u),end='') #打印訪問過的頂點(diǎn)

v=g.firstAdj(u) #訪問頂點(diǎn)的第一個(gè)鄰接點(diǎn)7.3圖的遍歷

whilev!=-1:ifnotvisited[v]: #如果該鄰接點(diǎn)沒有被訪問

q.inQueue(v) #將頂點(diǎn)插入隊(duì)尾

v=g.nextAdj(u,v) #否則訪問頂點(diǎn)的下一個(gè)鄰接點(diǎn)提示上述廣度優(yōu)先遍歷步驟是針對(duì)連通圖的。若是非連通圖，執(zhí)行上述遍歷步驟后，圖中一定還有未訪問過的頂點(diǎn)，此時(shí)，需要從圖中選擇一個(gè)未訪問過的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述廣度優(yōu)先遍歷步驟，直到圖中所有頂點(diǎn)均被訪問。在廣度優(yōu)先遍歷中，先被訪問的頂點(diǎn)的鄰接點(diǎn)也先被訪問，因此，在算法中需記錄頂點(diǎn)的訪問順序，以便后續(xù)按此順序訪問各頂點(diǎn)的鄰接點(diǎn)。為此，可以利用一個(gè)隊(duì)列來記錄頂點(diǎn)的訪問順序，即將訪問的每個(gè)頂點(diǎn)進(jìn)隊(duì)后再依次出隊(duì)，利用隊(duì)列“先進(jìn)先出”的特點(diǎn)按順序訪問它們的鄰接點(diǎn)。高手點(diǎn)撥7.3圖的遍歷7.3圖的遍歷下面具體分析廣度優(yōu)先遍歷無向圖的過程。（1）從頂點(diǎn)A出發(fā)，首先訪問頂點(diǎn)A。頂點(diǎn)A的鄰接點(diǎn)有頂點(diǎn)B和頂點(diǎn)F。（2）訪問頂點(diǎn)B和頂點(diǎn)F。（3）按照頂點(diǎn)A訪問其鄰接點(diǎn)的順序，首先訪問頂點(diǎn)B未被訪問過的鄰接點(diǎn)C、D、G，然后訪問頂點(diǎn)F未被訪問過的鄰接點(diǎn)（無符合條件的鄰接點(diǎn)）。（4）按照頂點(diǎn)B訪問其鄰接點(diǎn)的順序，首先訪問頂點(diǎn)C未被訪問過的鄰接點(diǎn)（無符合條件的鄰接點(diǎn)），然后訪問頂點(diǎn)D未被訪問過的鄰接點(diǎn)E，最后訪問頂點(diǎn)G未被訪問過的鄰接點(diǎn)（無符合條件的鄰接點(diǎn)）。（5）至此，該無向圖遍歷結(jié)束，得到的廣度優(yōu)先遍歷序列為A、B、F、C、D、G、E。7.3圖的遍歷在對(duì)無向連通圖進(jìn)行遍歷時(shí)，由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹，由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。無論是哪種生成樹，都是由相應(yīng)遍歷中經(jīng)過的邊構(gòu)成的。例如，無向圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹如下圖所示。需要注意的是，由于圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列不是唯一的，故其對(duì)應(yīng)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹也不是唯一的。7.4最小生成樹第7章圖7.4最小生成樹在一個(gè)無向連通網(wǎng)的所有生成樹中，各條邊權(quán)值之和最小的生成樹稱為該無向連通網(wǎng)的最小生成樹。構(gòu)造最小生成樹時(shí)，需要遵循如下3條原則。常用的構(gòu)造最小生成樹的算法有Prim算法和Kruskal算法。（1）盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路。（2）最小生成樹應(yīng)具有n個(gè)頂點(diǎn)和n-1條邊。（3）最小生成樹一定是連通的。7.4最小生成樹7.4.1Prim算法假設(shè)N=(V,E)是一個(gè)無向連通網(wǎng)，其中V為頂點(diǎn)集，E為邊集。另設(shè)置兩個(gè)集合U和TE，令U為最小生成樹的頂點(diǎn)集，TE為最小生成樹的邊集，則使用Prim算法求最小生成樹T的步驟如下。（1）令U的初始值為U={u0}（u0∈V），TE的初始值為TE={}。（2）在所有u∈U，v∈V-U的邊(u,v)∈E中選擇一條權(quán)值最小的邊(u0,v0)，并將其加入TE中，同時(shí)將頂點(diǎn)v0加入U(xiǎn)中。（3）重復(fù)步驟（2），直到U=V。此時(shí)，TE中必含有n-1條邊，T=(U,TE)即為N的最小生成樹。7.4最小生成樹classCloseEdge:def__init__(self,adjVex,lowCost):self.adjVex=adjVex #U中的頂點(diǎn)值

self.lowCost=lowCost #到U中各頂點(diǎn)邊的權(quán)值的最小值

classMiniSpanTree:

'''從值為u的頂點(diǎn)出發(fā)構(gòu)造最小生成樹，返回由最小生成樹的邊組成的二維數(shù)組'''defprim(g,u): #存放最小生成樹邊的頂點(diǎn)

tree=[[None,None]foriinrange(g.getVNum()-1)]count=0【算法描述】7.4最小生成樹#構(gòu)造輔助數(shù)組closEdge，用于存儲(chǔ)從U到V-U具有最小權(quán)值的邊，初值為NonecloseEdge=[None]*g.getVNum() k=g.locateVex(u) #記錄初始頂點(diǎn)的位置

forjinrange(g.getVNum()): ifk!=j: #如果不是初始頂點(diǎn)

#將邊加入最小生成樹的邊集TE中

closeEdge[j]=CloseEdge(u,g.getArcs(k,j)) #將頂點(diǎn)加入最小生成樹的頂點(diǎn)集U中

closeEdge[k]=CloseEdge(u,0) foriinrange(1,g.getVNum()): #找出具有到U中最短距離的頂點(diǎn)的序號(hào)7.4最小生成樹k=MiniSpanTree.getMinMum(closeEdge)tree[count][0]=closeEdge[k].adjVex #U中的頂點(diǎn)

tree[count][1]=g.getVex(k) #V-U中的頂點(diǎn)

count+=1 #更新輔助數(shù)組closeEdgecloseEdge[k].lowCost=0 forjinrange(g.getVNum()):

#判斷權(quán)值的大小，將權(quán)值最小的邊加入最小生成樹

ifg.getArcs(k,j)<closeEdge[j].lowCost:closeEdge[j]=CloseEdge(g.getVex(k),g.getArcs(k,j))returntree7.4最小生成樹 '''選出lowCost最小的頂點(diǎn)'''defgetMinMum(closeEdge):minvalue=sys.maxsizev=-1foriinrange(len(closeEdge)):ifcloseEdge[i].lowCost!=0andcloseEdge[i].lowCost<minvalue:minvalue=closeEdge[i].lowCostv=ireturnv7.4最小生成樹7.4.2Kruskal算法假設(shè)N=(V,E)是一個(gè)無向連通網(wǎng)，其中V為頂點(diǎn)集，E為邊集，則使用Kruskal算法求最小生成樹T的步驟如下。（1）令N的最小生成樹T的初始狀態(tài)為T=(V,{})，即T由V中的n個(gè)頂點(diǎn)構(gòu)成，頂點(diǎn)之間不存在邊。（2）在E中選擇權(quán)值最小的邊(u,v)，若該條邊未使最小生成樹T形成回路，則將其加入T中，否則舍去該條邊。（3）重復(fù)步驟（2），直到T中所有頂點(diǎn)構(gòu)成一個(gè)連通分量（或者包含n-1條邊）。Kruskal算法的關(guān)鍵是判斷選擇一條權(quán)值最小的邊后最小生成樹是否會(huì)形成回路，這可以通過判斷該條邊的兩個(gè)頂點(diǎn)所在的連通分量是否相同來解決。7.4最小生成樹defKruskal(g):

vset=[-1]*100#構(gòu)造輔助數(shù)組vset，用于存儲(chǔ)頂點(diǎn)所屬的連通分量的編號(hào)

E=[] #建立存放所有邊的數(shù)組E

foriinrange(g.n):

forjinrange(i+1,g.n): #無向圖的上三角部分的邊【算法描述】判斷規(guī)則為，每個(gè)連通分量用其中一個(gè)頂點(diǎn)的編號(hào)來標(biāo)識(shí)（稱為連通分量編號(hào)），同一個(gè)連通分量中所有頂點(diǎn)的連通分量編號(hào)相同，不同連通分量中兩個(gè)頂點(diǎn)的連通分量編號(hào)不相同。如果選擇的邊的兩個(gè)頂點(diǎn)的連通分量編號(hào)相同，則一定會(huì)形成回路，此時(shí)，須舍棄該條邊。7.4最小生成樹ifg.e[i][j]!=0andg.e[i][j]!=sys.maxsize:E.append([i,j,g.e[i][j]]) #添加[i,j,w]元素

E.sort(key=itemgetter(2)) #按權(quán)值遞增排序所有邊

foriinrange(g.n):vset[i]=i #初始化數(shù)組vsetcnt=1 #初值為最小生成樹的第1條邊

j=0 #E中邊的下標(biāo)

whilecnt<g.n: #生成的邊數(shù)小于nu1,v1=E[j][0],E[j][1] #邊的起點(diǎn)和終點(diǎn)

#兩個(gè)頂點(diǎn)所屬連通分量的編號(hào)7.4最小生成樹sn1=vset[u1]sn2=vset[v1]ifsn1!=sn2:#兩個(gè)頂點(diǎn)屬于不同連通分量時(shí)，加入不會(huì)構(gòu)成回路

print('(%d,%d):%d'%(u1,v1,E[j][2]),end='')#加入該條邊

cnt+=1 #最小生成樹的邊數(shù)加1

'''將加入最小生成樹的邊的兩個(gè)頂點(diǎn)所屬的連通分量編號(hào)改為一致'''foriinrange(g.n):ifvset[i]==sn2:vset[i]=sn1j+=1 #否則繼續(xù)取下一條權(quán)值最小的邊7.5最短路徑第7章圖7.5最短路徑7.5.1Dijkstra算法Dijkstra算法可解決有向網(wǎng)中從源點(diǎn)v0到其他頂點(diǎn)的最短路徑問題。假設(shè)G=(V,E)是一個(gè)有向網(wǎng)，其中，V為頂點(diǎn)集，E為邊集。如果用S表示已求得最短路徑的頂點(diǎn)集，用U表示尚未求得最短路徑的頂點(diǎn)集，則使用Dijkstra算法求最短路徑的步驟如下。（1）初始時(shí)，S中只有源點(diǎn)v0，U中是除源點(diǎn)v0之外的其他頂點(diǎn)。（2）從U中找出源點(diǎn)v0到U中最短路徑長度最小的頂點(diǎn)u，并將其加入S中。（3）以頂點(diǎn)u為中間點(diǎn)，此時(shí)從源點(diǎn)v0到某個(gè)頂點(diǎn)（假設(shè)為頂點(diǎn)v1）的最短路徑有兩條，一條經(jīng)過頂點(diǎn)u；另一條不經(jīng)過頂點(diǎn)u。（4）重復(fù)步驟（2）和步驟（3），直到所有頂點(diǎn)均加入S中。7.5最短路徑classShortestPath:defdjikstra(g,v0):#存儲(chǔ)最短路徑，p[v][k]表示從v0到v的最短路徑中經(jīng)過的第k個(gè)頂點(diǎn)

p=[([-1]*g.getVNum())foriinrange(g.getVNum())]#存儲(chǔ)當(dāng)前所找到的從源點(diǎn)到終點(diǎn)的最短路徑長度

D=[sys.maxsize]*g.getVNum()#設(shè)置finish標(biāo)志，初值為False。若已找到最短路徑，則修改為Truefinish=[False]*g.getVNum()v0=g.locateVex(v0) #頂點(diǎn)的位置【算法描述】7.5最短路徑forvinrange(g.getVNum()):D[v]=g.getArcs(v0,v) #獲取權(quán)值

ifD[v]<sys.maxsize: #若兩個(gè)頂點(diǎn)之間存在邊

p[v][0]=v0p[v][1]=vp[v0][0]=v0 #v0本身可以直接到達(dá)v0D[v0]=0finish[v0]=True #更新finish的值

v=-1 #若兩個(gè)頂點(diǎn)之間不存在邊，初值為-1foriinrange(1,g.getVNum()):minvalue=sys.maxsize7.5最短路徑forwinrange(g.getVNum()):'''找出所有最短路徑中的最小值'''ifnotfinish[w]:ifD[w]<minvalue:v=wminvalue=D[w]finish[v]=True #更新finish的值

forwinrange(g.getVNum()):

'''如果經(jīng)過頂點(diǎn)v后的路徑小于不經(jīng)過頂點(diǎn)v的路徑，則經(jīng)過頂點(diǎn)v的路徑的權(quán)值之和為最短路徑長度'''7.5最短路徑ifnotfinish[w]andg.getArcs(v,w)<sys.maxsizeand(minvalue+g.getArcs(v,w)<D[w]): D[w]=minvalue+g.getArcs(v,w) '''更新最短路徑信息'''forkinrange(g.getVNum()):p[w][k]=p[v][k]ifp[w][k]==-1:p[w][k]=wbreakdis={g.getVex(i):D[i]foriinrange(g.getVNum())}returndis,p #返回源點(diǎn)到其他頂點(diǎn)的最短路徑長度與路徑矩陣7.5最短路徑

'''輸出源點(diǎn)到其他頂點(diǎn)的最短路徑'''defprintDjikstraPath(g,v0,p):u=v0v0=g.locateVex(v0) #返回源點(diǎn)v0的位置

foriinrange(g.getVNum()):v=g.getVex(i) #返回頂點(diǎn)的值

print('%s->%s的最短路徑為:'%(u,v),end='') '''輸出最短路徑中經(jīng)過的各頂點(diǎn)'''ifp[i][0]!=-1:print(g.getVex(p[v0][0]),end='')7.5最短路徑forkinrange(1,g.getVNum()):ifp[i][k]==-1:breakprint('->%s'%g.getVex(p[i][k]),end='')print()7.5.2Floyd算法Floyd算法可解決有向網(wǎng)中任意兩個(gè)頂點(diǎn)之間的最短路徑問題。Floyd算法可以使用n階方陣來描述，其中D-1[i][j]表示從頂點(diǎn)i出發(fā)不經(jīng)過其他頂點(diǎn)直接到達(dá)頂點(diǎn)j的路徑長度，D(k)[i][j]表示從頂點(diǎn)i到頂點(diǎn)j的中間可能經(jīng)過頂點(diǎn)0、1、…、k，但不經(jīng)過頂點(diǎn)k+1、k+2、…、n-1的最短路徑長度。7.5最短路徑所以，F(xiàn)loyd算法的求解過程是按照圖中頂點(diǎn)的順序依次計(jì)算D(k)（0≤k≤n-1），最終得到的D(n-1)[i][j]就是從頂點(diǎn)i到頂點(diǎn)j的最短路徑長度。classShortestPath:deffloyd(g):vNum=g.getVNum() #返回頂點(diǎn)數(shù)

#存儲(chǔ)最短路徑長度

D=[[sys.maxsize]*vNumforiinrange(vNum)] #存儲(chǔ)最短路徑

p=[[-1]*vNumforiinrange(vNum)]foruinrange(vNum):forvinrange(vNum):7.5最短路徑

#如果u不等于v，D[u][v]等于邊<u,v>的權(quán)值，否則為0D[u][v]=g.getArcs(u,v)ifu!=velse0ifu!=vandD[u][v]<sys.maxsize:p[u][v]=u #頂點(diǎn)v的前驅(qū)為uforkinrange(vNum):foriinrange(vNum):forjinrange(vNum)'''若利用中轉(zhuǎn)點(diǎn)后路徑變短，則修改最短路徑及其長度'''ifD[i][j]>D[i][k]+D[k][j]:D[i][j]=D[i][k]+D[k][j]p[i][j]=p[k][j]7.5最短路徑dis={(g.getVex(u),g.getVex(v)):D[u][v]foruinrange(vNum)forvinrange(vNum)}returndis,p #返回兩個(gè)頂點(diǎn)之間的最短路徑長度與路徑矩陣

'''輸出任意兩個(gè)頂點(diǎn)之間的最短路徑'''defprintFloydPath(g,p):vNum=g.getVNum() #獲取頂點(diǎn)數(shù)

foruinrange(vNum):forvinrange(vNum):ifu==v: #同一個(gè)頂點(diǎn)的最短路徑為本身print('%s->%s的最短路徑為:%s'%(g.getVex(u),g.getVex(v),g.getVex(u)))7.5最短路徑continue '''兩個(gè)不同頂點(diǎn)之間的最短路徑'''flag=True path=[v]t=p[u][path[0]]whilet!=u:ift==-1:flag=False

break7.5最短路徑path=[t]+patht=p[u][t]

print('%s->%s的最短路徑為:'%(g.getVex(u),g.getVex(v)),end='')ifflag:print(g.getVex(u),end='')fornodeinpath:print('->%s'%g.getVex(node),end='')print()同步訓(xùn)練求城市之間交通費(fèi)用最少的路線【問題描述】已知下圖為一個(gè)城市交通網(wǎng)，其中各頂點(diǎn)表示城市，邊的權(quán)值表示從一個(gè)城市到另一個(gè)城市的交通費(fèi)用。現(xiàn)有一位旅客要從城市A到其他城市，設(shè)計(jì)算法找出一條路線，使得這位旅客從城市A到其他城市所花費(fèi)的交通費(fèi)用最少。同步訓(xùn)練求城市之間交通費(fèi)用最少的路線【問題分析】該問題反映在圖上就是要找從頂點(diǎn)A到其他頂點(diǎn)的最短路徑，因此可以使用Dijkstra算法求解該問題，并用從頂點(diǎn)A到其他頂點(diǎn)的最短路徑及最短路徑長度表示從城市A到其他城市在交通費(fèi)用最少情況下的路線及花銷?！敬a實(shí)現(xiàn)】importsysclassHNode: #表頭結(jié)點(diǎn)類

def__init__(self,data=None):self.data=data #頂點(diǎn)的名稱或其他信息

self.firstarc=None #指向單鏈表中除表頭結(jié)點(diǎn)外的第一個(gè)結(jié)點(diǎn)classArcNode: #邊結(jié)點(diǎn)類同步訓(xùn)練求城市之間交通費(fèi)用最少的路線def__init__(self,adjVex,weight):self.adjVex=adjVex #頂點(diǎn)的鄰接點(diǎn)在頂點(diǎn)數(shù)組中的下標(biāo)

self.weight=weight #邊的權(quán)值

self.nextarc=None #與頂點(diǎn)相鄰接的下一個(gè)頂點(diǎn)classALGraph: #圖的鄰接表類

GRAPHKIND_UDG='UDG'GRAPHKIND_DG='DG'GRAPHKIND_UDN='UDN'GRAPHKIND_DN='DN'def__init__(self,kind=None,vNum=0,eNum=0,v=None,e=None):同步訓(xùn)練求城市之間交通費(fèi)用最少的路線self.kind=kindself.vNum=vNumself.eNum=eNumself.v=vself.e=edefcreateDN(self): #創(chuàng)建有向網(wǎng)

v=self.vself.v=[None]*self.vNumforiinrange(self.vNum):self.v[i]=HNode(v[i])同步訓(xùn)練求城市之間交通費(fèi)用最少的路線foriinrange(self.eNum):a,b,w=self.e[i]u,v=self.locateVex(a),self.locateVex(b)self.addArc(u,v,w)defaddArc(self,i,j,weight): #插入邊結(jié)點(diǎn)

arc=ArcNode(j,weight)arc.nextarc=self.v[i].firstarcself.v[i].firstarc=arcdefgetVNum(self): #返回頂點(diǎn)數(shù)

returnself.vNum同步訓(xùn)練求城市之間交通費(fèi)用最少的路線defgetVex(self,i): #返回頂點(diǎn)的值

ifi<0ori>=self.vNum:raiseException('第%s個(gè)結(jié)點(diǎn)不存在'%i)returnself.v[i].datadeflocateVex(self,x): #返回值為x的頂點(diǎn)的位置

foriinrange(self.vNum):ifself.v[i].data==x:returnireturn-1defgetArcs(self,u,v): #返回頂點(diǎn)u到頂點(diǎn)v的權(quán)值同步訓(xùn)練求城市之間交通費(fèi)用最少的路線ifu<0oru>=self.vNum:raiseException('第%s個(gè)結(jié)點(diǎn)不存在'%u)ifv<0orv>=self.vNum:raiseException('第%s個(gè)結(jié)點(diǎn)不存在'%v)p=self.v[u].firstarcwhilepisnotNone:ifp.adjVex==v:returnp.weightp=p.nextarcreturnsys.maxsize同步訓(xùn)練求城市之間交通費(fèi)用最少的路線classShortestPath:defdjikstra(g,v0):

#存儲(chǔ)最短路徑，p[v][k]表示從v0到v的最短路徑中經(jīng)過的第k個(gè)頂點(diǎn)

p=[([-1]*g.getVNum())foriinrange(g.getVNum())]#存儲(chǔ)當(dāng)前所找到的從源點(diǎn)到終點(diǎn)的最短路徑長度

D=[sys.maxsize]*g.getVNum()

#設(shè)置finish標(biāo)志，初值為False。若已找到最短路徑，則修改為Truefinish=[False]*g.getVNum()v0=g.locateVex(v0) #頂點(diǎn)的位置

forvinrange(g.getVNum()):同步訓(xùn)練求城市之間交通費(fèi)用最少的路線D[v]=g.getArcs(v0,v) #獲取權(quán)值

ifD[v]<sys.maxsize: #若兩個(gè)頂點(diǎn)之間存在邊

p[v][0]=v0p[v][1]=vp[v0][0]=v0 #v0本身可以直接到達(dá)v0D[v0]=0finish[v0]=True #更新finish的值

v=-1 #若兩個(gè)頂點(diǎn)之間不存在邊，初值為-1foriinrange(1,g.getVNum()):minvalue=sys.maxsize同步訓(xùn)練求城市之間交通費(fèi)用最少的路線forwinrange(g.getVNum()):'''找出所有最短路徑中的最小值'''ifnotfinish[w]:ifD[w]<minvalue:v=wminvalue=D[w]finish[v]=True #更新finish的值

forwinrange(g.getVNum()):

'''如果經(jīng)過頂點(diǎn)v后的路徑小于不經(jīng)過頂點(diǎn)v的路徑，則經(jīng)過頂點(diǎn)v的路徑的權(quán)值之和為最短路徑長度'''同步訓(xùn)練求城市之間交通費(fèi)用最少的路線ifnotfinish[w]andg.getArcs(v,w)<sys.maxsizeand(minvalue+g.getArcs(v,w)<D[w]):D[w]=minvalue+g.getArcs(v,w)'''更新最短路徑信息'''forkinrange(g.getVNum()):p[w][k]=p[v][k]ifp[w][k]==-1:p[w][k]=wbreakdis={g.getVex(i):D[i]foriinrange(1,g.getVNum())}returndis,p #返回源點(diǎn)到其他頂點(diǎn)的最短路徑長度與路徑矩陣同步訓(xùn)練求城市之間交通費(fèi)用最少的路線'''輸出源點(diǎn)到其他頂點(diǎn)的最短路徑'''defprintDjikstraPath(g,v0,p):u=v0v0=g.locateVex(v0) #返回源點(diǎn)的位置

foriinrange(1,g.getVNum()):v=g.getVex(i) #返回頂點(diǎn)的值

print('城市%s->城市%s:'%(u,v),end='')'''輸出最短路徑中經(jīng)過的各頂點(diǎn)'''ifp[i][0]!=-1:print(g.getVex(p[v0][0]),end='')同步訓(xùn)練求城市之間交通費(fèi)用最少的路線forkinrange(1,g.getVNum()):ifp[i][k]==-1:breakprint('->%s'%g.getVex(p[i][k]),end='')print()v=['A','B','C','D','E','F'] #頂點(diǎn)集e=[('A','B',500),('A','C',300),('A','D',380),('A','E',380),('B','D',100),('C','E',50),('D','B',100),('D','F',170),('E','C',50),('E','F',100),('F','D',170)] #邊集g=ALGraph(ALGraph.GRAPHKIND_DN,