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

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

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

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

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

第7章 強(qiáng)化學(xué)習(xí)意識，努力提高應(yīng)用理論知識解決實(shí)際問題的能力。 樹立全局意識，學(xué)會抓住關(guān)鍵，并利用關(guān)鍵環(huán)節(jié)掌控全局進(jìn)展。Content第7章圖的存儲結(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中兩個不同頂點(diǎn)的邊的有限集合（邊集），記為E(G)。E(G)可以為空集，當(dāng)E(G)為空集時，圖G只有頂點(diǎn)而沒有邊。對于圖G，如果其中的邊為無向邊，即兩個頂點(diǎn)之間的邊沒有方向，則稱圖G為無向圖；如果其中的邊為有向邊，即兩個頂點(diǎn)之間的邊有方向，則稱圖G為有向圖。7.1.1圖的定義7.1圖概述在無向圖中，頂點(diǎn)對通常用圓括號“()”括起來，以表示一條無向邊。例如，<v0,v1>表示與頂點(diǎn)v0和頂點(diǎn)v1相關(guān)聯(lián)的一條無向邊。由此可見，<v0,v1>和(v1,v0)是同一條邊。而在有向圖中，頂點(diǎn)對通常用尖括號“<>”括起來，以表示一條有向邊。例如，<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．無向完全圖和有向完全圖對于一個無向圖，如果圖中任意兩個頂點(diǎn)之間都存在一條邊，則稱該無向圖為無向完全圖。對于一個有向圖，如果圖中任意兩個頂點(diǎn)之間都存在兩條方向相反的邊，則稱該有向圖為有向完全圖。例如，下圖為無向完全圖和有向完全圖。7.1圖概述2．子圖對于兩個圖G=(V,E)和G‘=(V’,E‘)，如果V’是V的子集，E‘是E的子集，則稱圖G’是圖G的子圖。例如，下圖為上圖無向完全圖和有向完全圖的子圖。7.1圖概述3．稀疏圖和稠密圖有較少條邊的圖稱為稀疏圖，反之稱為稠密圖。4．鄰接點(diǎn)對于無向圖G=(V,E)，如果邊(v0,v1)∈E，則稱頂點(diǎn)v0與頂點(diǎn)v1互為鄰接點(diǎn)，即頂點(diǎn)v0與頂點(diǎn)v1相鄰接；同時稱邊(v0,v1)依附于頂點(diǎn)v0和頂點(diǎn)v1，或者說邊(v0,v1)與頂點(diǎn)v0和頂點(diǎn)v1相關(guān)聯(lián)。對于有向圖G=(V,E)，如果邊<v0,v1>∈E，則稱頂點(diǎn)v0鄰接到頂點(diǎn)v1，頂點(diǎn)v1鄰接自頂點(diǎn)v0；同時稱邊<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)的度、入度和出度對于無向圖，頂點(diǎn)v的度是指與頂點(diǎn)v相關(guān)聯(lián)的邊的數(shù)目，記作TD(v)。對于有向圖，頂點(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)用中，圖的邊往往具有一定意義且會被賦予相應(yīng)的數(shù)值，該數(shù)值稱為該邊的權(quán)（也稱為權(quán)值）。這種帶權(quán)的圖稱為網(wǎng)。例如，在交通網(wǎng)中用頂點(diǎn)表示城市時，邊的權(quán)可以表示兩個城市之間的距離，如下圖所示。7.1圖概述7．路徑和路徑長度8．回路或環(huán)若一條路徑中的開始頂點(diǎn)和結(jié)束頂點(diǎn)相同，則稱該路徑為回路或環(huán)。對于圖G=(V,E)，從頂點(diǎn)v出發(fā)到達(dá)頂點(diǎn)v'的一條路徑是一個頂點(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．連通、連通圖和連通分量對于無向圖G=(V,E)，如果從頂點(diǎn)v0到頂點(diǎn)v1有路徑，則稱頂點(diǎn)v0和頂點(diǎn)v1是連通的。如果圖G中任意兩個頂點(diǎn)都是連通的，則稱圖G為連通圖，否則稱為非連通圖。無向圖中的極大連通子圖稱為無向圖的連通分量。7.1圖概述提示在無向圖中，若某一個連通子圖不包含在其他連通子圖內(nèi)，則稱該連通子圖為極大連通子圖。也就是說，與該連通子圖中某頂點(diǎn)連通的所有頂點(diǎn)必包含在該連通子圖中。顯然，連通圖的極大連通子圖只有其自身一個，而非連通圖的極大連通子圖有多個。7.1圖概述11．強(qiáng)連通圖和強(qiáng)連通分量對于有向圖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．連通圖的生成樹一個連通圖的生成樹是指該連通圖的一個極小連通子圖，它含有圖中的全部頂點(diǎn)（頂點(diǎn)個數(shù)為n），但只有足以構(gòu)成一棵樹的n-1條邊。7.1圖概述提示極小連通子圖既要保證圖的流暢，又要使圖的邊數(shù)最少。如果一個無向圖有n個頂點(diǎn)和少于n-1條邊，則該圖是非連通圖；如果一個無向圖有n個頂點(diǎn)和多于n-1條邊，則該圖中一定有回路。值得注意的是，有n個頂點(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是圖中的某個頂點(diǎn)，返回v的值putVex(v,value)已知圖存在，v是圖中的某個頂點(diǎn)，將value值賦給vfirstAdjVex(v)已知圖存在，v是圖中的某個頂點(diǎn)，返回v的第一個鄰接點(diǎn)；若v無鄰接點(diǎn)，則返回NonenextAdjVex(v,w)已知圖存在，v是圖中的某個頂點(diǎn)，w是v的鄰接點(diǎn)，返回v的相對于w的下一個鄰接點(diǎn)；若w是v的最后一個鄰接點(diǎn)，則返回NoneinsertVex(v)已知圖存在，在圖中插入一個新頂點(diǎn)vdeleteVex(v)已知圖存在，v是圖中的某個頂點(diǎn)，刪除頂點(diǎn)v及與其相關(guān)聯(lián)的邊insertArc(v,w)已知圖存在，v和w是圖中的兩個頂點(diǎn)，在圖中增加一條從頂點(diǎn)v到頂點(diǎn)w的邊deleteArc(v,w)已知圖存在，v和w是圖中的兩個頂點(diǎn)，刪除圖中從頂點(diǎn)v到頂點(diǎn)w的邊dfsTraverse()已知圖存在，對圖進(jìn)行深度優(yōu)先遍歷bfsTraverse()已知圖存在，對圖進(jìn)行廣度優(yōu)先遍歷表7-1圖基本操作的定義7.2圖的存儲結(jié)構(gòu)第7章圖7.2圖的存儲結(jié)構(gòu)7.2.1鄰接矩陣1．鄰接矩陣表示法鄰接矩陣表示法也稱數(shù)組表示法，通常采用二維數(shù)組存儲圖中各頂點(diǎn)之間的鄰接關(guān)系。（1）假設(shè)G=(V,E)是具有n個頂點(diǎn)的圖，則它的鄰接矩陣是一個n×n的方陣，定義如下。7.2圖的存儲結(jié)構(gòu)例如，鄰接矩陣如下圖所示。（2）假設(shè)G=(V,E)是具有n個頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是一個n×n的方陣，定義如下。7.2圖的存儲結(jié)構(gòu)其中，表示頂點(diǎn)i和頂點(diǎn)j之間邊的權(quán)值。圖的鄰接矩陣類的定義如下。classALGraph: #圖的鄰接矩陣類

GRAPHKIND_UDG='UDG' #無向圖7.2圖的存儲結(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圖的存儲結(jié)構(gòu)鄰接矩陣表示法的特點(diǎn)如下。（1）圖的鄰接矩陣是唯一的。（2）根據(jù)鄰接矩陣很容易判斷任意兩個頂點(diǎn)之間是否有邊，且時間復(fù)雜度為O(1)。（3）對于無向圖，鄰接矩陣第i（0≤i≤n-1）行非零元素（或非∞元素）的個數(shù)是頂點(diǎn)vi的度；對于有向圖，第i（0≤i≤n-1）行非零元素（或非∞元素）的個數(shù)是頂點(diǎn)vi的出度，第i（0≤i≤n-1）列非零元素（或非∞元素）的個數(shù)是頂點(diǎn)vi的入度。7.2圖的存儲結(jié)構(gòu)（4）鄰接矩陣中增加和刪除頂點(diǎn)的操作不易實(shí)現(xiàn)。（5）要統(tǒng)計圖中邊的總數(shù)，需要掃描鄰接矩陣中的所有元素，其時間復(fù)雜度為O(n2)。（6）如果是有向圖，n個頂點(diǎn)需要n2個存儲單元存儲邊；如果是無向圖，因其鄰接矩陣是一個對稱矩陣，因此在頂點(diǎn)數(shù)n很大時，可以采用對稱矩陣的壓縮存儲方法，僅存儲下三角（或上三角）的元素［需要n(n-1)/2個存儲單元］，從而減小存儲空間。但無論以什么方式存儲，鄰接矩陣表示法的空間復(fù)雜度均為O(n2)，因此更適合存儲稠密圖。7.2圖的存儲結(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圖的存儲結(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)值，確定兩個頂點(diǎn)在圖中的位置后，為邊賦相應(yīng)的權(quán)值，同時為其對稱邊也賦相同的權(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圖的存儲結(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若要建立無向圖，只需對上述算法進(jìn)行如下兩處修改。（1）初始化鄰接矩陣時，將每條邊的權(quán)值初始化為0。（2）構(gòu)造鄰接矩陣時，將每條邊的權(quán)值賦值為1。同樣，創(chuàng)建有向網(wǎng)或有向圖時，也可通過對上述算法進(jìn)行簡單修改實(shí)現(xiàn)，感興趣的讀者可自行完成。高手點(diǎn)撥7.2圖的存儲結(jié)構(gòu)7.2圖的存儲結(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圖的存儲結(jié)構(gòu)7.2.2鄰接表1．鄰接表表示法鄰接表表示法是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接表中，對圖中的每個頂點(diǎn)建立一個單鏈表，將與該頂點(diǎn)相鄰的頂點(diǎn)鏈接到該單鏈表中。也就是說，具有n個頂點(diǎn)的圖，頂點(diǎn)間的鄰接關(guān)系可構(gòu)成n個單鏈表，其中第i（0≤i≤n-1）個單鏈表由所有鄰接于頂點(diǎn)vi的頂點(diǎn)鏈接而成。鄰接表中每個單鏈表的第一個結(jié)點(diǎn)（表頭結(jié)點(diǎn)）存放有關(guān)頂點(diǎn)的信息，以便于隨機(jī)訪問任一頂點(diǎn)的單鏈表，其余結(jié)點(diǎn)存放有關(guān)邊的信息。7.2圖的存儲結(jié)構(gòu)（1）表頭結(jié)點(diǎn)的結(jié)構(gòu)如下圖所示。其中，data域用于存儲頂點(diǎn)vi的名稱或其他信息，firstarc域用于指向單鏈表中除表頭結(jié)點(diǎn)外的第一個結(jié)點(diǎn)（即與頂點(diǎn)vi相鄰接的第一個頂點(diǎn)）。在鄰接表中，假設(shè)表頭結(jié)點(diǎn)為HNode類對象，則表頭結(jié)點(diǎn)的定義如下。classHNode:def__init__(self,data):self.data=data #頂點(diǎn)的名稱或其他信息

self.firstarc=None#指向單鏈表中除表頭結(jié)點(diǎn)外的第一個結(jié)點(diǎn)7.2圖的存儲結(jié)構(gòu)（2）邊結(jié)點(diǎn)的結(jié)構(gòu)如下圖所示。無權(quán)圖的邊結(jié)點(diǎn)包括兩部分。其中，adjvex域用于存儲與頂點(diǎn)vi相鄰接的頂點(diǎn)在頂點(diǎn)數(shù)組中的下標(biāo)，nextarc域用于指向與頂點(diǎn)vi相鄰接的下一個頂點(diǎn)。相較于無權(quán)圖，有權(quán)圖的邊結(jié)點(diǎn)需要額外增加一個info域存儲邊相關(guān)的信息，如權(quán)值。假設(shè)邊結(jié)點(diǎn)為ArcNode類對象，則邊結(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)相鄰接的下一個頂點(diǎn)7.2圖的存儲結(jié)構(gòu)為此，可以對每個頂點(diǎn)vi建立一個逆鄰接表，即對每個頂點(diǎn)vi建立一個以頂點(diǎn)vi為弧頭的單鏈表。這樣，在逆鄰接表中第i（0≤i≤n-1）個單鏈表中邊結(jié)點(diǎn)的個數(shù)就是頂點(diǎn)vi的入度。對于無向圖，鄰接表中第i（0≤i≤n-1）個單鏈表中邊結(jié)點(diǎn)的個數(shù)是頂點(diǎn)vi的度。對于有向圖，鄰接表中第i（0≤i≤n-1）個單鏈表中邊結(jié)點(diǎn)的個數(shù)是頂點(diǎn)vi的出度，但要求頂點(diǎn)vi的入度必須遍歷整個鄰接表。7.2圖的存儲結(jié)構(gòu)鄰接表表示法的特點(diǎn)如下。（1）圖的鄰接表是不唯一的。（2）在鄰接表中，無法很快判斷任意兩個頂點(diǎn)之間是否有邊，且最壞時間復(fù)雜度為O(n)。（3）鄰接表中增加和刪除頂點(diǎn)的操作很容易實(shí)現(xiàn)。（4）要統(tǒng)計圖中邊的總數(shù)，按單鏈表順序掃描所有邊即可，其時間復(fù)雜度為O(n+e)。（5）對n個頂點(diǎn)e條邊的圖，若該圖為無向圖，則在其鄰接表表示中有n個表頭結(jié)點(diǎn)和2e個邊結(jié)點(diǎn)；若該圖為有向圖，則在其鄰接表表示中有n個表頭結(jié)點(diǎn)和e個邊結(jié)點(diǎn)。因此，鄰接表表示法的空間復(fù)雜度為O(n+e)，更適合存儲稀疏圖。7.2圖的存儲結(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圖的存儲結(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)建鄰接表。依次輸入每條邊依附的兩個頂點(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]) #生成一個新的結(jié)點(diǎn)表7.2圖的存儲結(jié)構(gòu)foriinrange(self.eNum):a,b=self.e[i] #輸入每條邊依附的兩個頂點(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) #插入另一個對稱的邊結(jié)點(diǎn)若要創(chuàng)建有向圖，只需對上述算法進(jìn)行簡單修改，即僅需生成一個邊結(jié)點(diǎn)，并將其插入表頭結(jié)點(diǎn)后面。高手點(diǎn)撥7.2圖的存儲結(jié)構(gòu)3）插入邊結(jié)點(diǎn)該算法是指在單鏈表中插入一個頂點(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）從圖中某個頂點(diǎn)v出發(fā)，訪問該頂點(diǎn)。（2）找出剛訪問過的頂點(diǎn)的第一個未被訪問的鄰接點(diǎn)，訪問該鄰接點(diǎn)。以該鄰接點(diǎn)為新頂點(diǎn)，重復(fù)步驟（2），直到剛訪問過的頂點(diǎn)沒有未被訪問的鄰接點(diǎn)。（3）退回到上一個訪問過且還有未被訪問的鄰接點(diǎn)的頂點(diǎn)，繼續(xù)訪問該頂點(diǎn)的下一個未被訪問的鄰接點(diǎn)。（4）重復(fù)步驟（2）和步驟（3），直到圖中所有頂點(diǎn)均被訪問。提示上述深度優(yōu)先遍歷步驟是針對連通圖的。若是非連通圖，執(zhí)行上述遍歷步驟后，圖中一定還有未訪問過的頂點(diǎn)，此時，需要從圖中選擇一個未訪問過的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述深度優(yōu)先遍歷步驟，直到圖中所有頂點(diǎn)均被訪問。7.3圖的遍歷defdfsTraverse(g): globalvisited #定義全局變量

visited=[False]*g.getVNum() #創(chuàng)建訪問標(biāo)記數(shù)組，并賦初值False'''以每個頂點(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 #對訪問過的頂點(diǎn)進(jìn)行標(biāo)記

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

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

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

v=g.nextAdj(i,v) #否則訪問頂點(diǎn)的下一個鄰接點(diǎn)提示為了在遍歷過程中區(qū)分頂點(diǎn)是否已經(jīng)被訪問，可設(shè)置一個訪問標(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的另一個未被訪問過的鄰接點(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的另一個未被訪問過的鄰接點(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)先遍歷時，如果一個頂點(diǎn)有多個鄰接點(diǎn)，可以任選其一，故圖的深度優(yōu)先遍歷序列不是唯一的。也就是說，對于如圖7-18所示的無向圖，其深度優(yōu)先遍歷序列也可以為A、B、C、D、G、F、E。7.3圖的遍歷7.3.2廣度優(yōu)先遍歷圖的廣度優(yōu)先遍歷類似于二叉樹的層次遍歷，其步驟如下。（1）從圖中的某個頂點(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'''以每個頂點(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 #對訪問過的頂點(diǎn)進(jìn)行標(biāo)記

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

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

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

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

v=g.nextAdj(u,v) #否則訪問頂點(diǎn)的下一個鄰接點(diǎn)提示上述廣度優(yōu)先遍歷步驟是針對連通圖的。若是非連通圖，執(zhí)行上述遍歷步驟后，圖中一定還有未訪問過的頂點(diǎn)，此時，需要從圖中選擇一個未訪問過的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述廣度優(yōu)先遍歷步驟，直到圖中所有頂點(diǎn)均被訪問。在廣度優(yōu)先遍歷中，先被訪問的頂點(diǎn)的鄰接點(diǎn)也先被訪問，因此，在算法中需記錄頂點(diǎn)的訪問順序，以便后續(xù)按此順序訪問各頂點(diǎn)的鄰接點(diǎn)。為此，可以利用一個隊(duì)列來記錄頂點(diǎn)的訪問順序，即將訪問的每個頂點(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圖的遍歷在對無向連通圖進(jìn)行遍歷時，由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹，由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。無論是哪種生成樹，都是由相應(yīng)遍歷中經(jīng)過的邊構(gòu)成的。例如，無向圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹如下圖所示。需要注意的是，由于圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列不是唯一的，故其對應(yīng)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹也不是唯一的。7.4最小生成樹第7章圖7.4最小生成樹在一個無向連通網(wǎng)的所有生成樹中，各條邊權(quán)值之和最小的生成樹稱為該無向連通網(wǎng)的最小生成樹。構(gòu)造最小生成樹時，需要遵循如下3條原則。常用的構(gòu)造最小生成樹的算法有Prim算法和Kruskal算法。（1）盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路。（2）最小生成樹應(yīng)具有n個頂點(diǎn)和n-1條邊。（3）最小生成樹一定是連通的。7.4最小生成樹7.4.1Prim算法假設(shè)N=(V,E)是一個無向連通網(wǎng)，其中V為頂點(diǎn)集，E為邊集。另設(shè)置兩個集合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中，同時將頂點(diǎn)v0加入U中。（3）重復(fù)步驟（2），直到U=V。此時，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，用于存儲從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)的序號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)是一個無向連通網(wǎng)，其中V為頂點(diǎn)集，E為邊集，則使用Kruskal算法求最小生成樹T的步驟如下。（1）令N的最小生成樹T的初始狀態(tài)為T=(V,{})，即T由V中的n個頂點(diǎn)構(gòu)成，頂點(diǎn)之間不存在邊。（2）在E中選擇權(quán)值最小的邊(u,v)，若該條邊未使最小生成樹T形成回路，則將其加入T中，否則舍去該條邊。（3）重復(fù)步驟（2），直到T中所有頂點(diǎn)構(gòu)成一個連通分量（或者包含n-1條邊）。Kruskal算法的關(guān)鍵是判斷選擇一條權(quán)值最小的邊后最小生成樹是否會形成回路，這可以通過判斷該條邊的兩個頂點(diǎn)所在的連通分量是否相同來解決。7.4最小生成樹defKruskal(g):

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

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

foriinrange(g.n):

forjinrange(i+1,g.n): #無向圖的上三角部分的邊【算法描述】判斷規(guī)則為，每個連通分量用其中一個頂點(diǎn)的編號來標(biāo)識（稱為連通分量編號），同一個連通分量中所有頂點(diǎn)的連通分量編號相同，不同連通分量中兩個頂點(diǎn)的連通分量編號不相同。如果選擇的邊的兩個頂點(diǎn)的連通分量編號相同，則一定會形成回路，此時，須舍棄該條邊。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)

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

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

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

'''將加入最小生成樹的邊的兩個頂點(diǎn)所屬的連通分量編號改為一致'''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)是一個有向網(wǎng)，其中，V為頂點(diǎn)集，E為邊集。如果用S表示已求得最短路徑的頂點(diǎn)集，用U表示尚未求得最短路徑的頂點(diǎn)集，則使用Dijkstra算法求最短路徑的步驟如下。（1）初始時，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)，此時從源點(diǎn)v0到某個頂點(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):#存儲最短路徑，p[v][k]表示從v0到v的最短路徑中經(jīng)過的第k個頂點(diǎn)

p=[([-1]*g.getVNum())foriinrange(g.getVNum())]#存儲當(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: #若兩個頂點(diǎn)之間存在邊

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

v=-1 #若兩個頂點(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)中任意兩個頂點(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)的順序依次計算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ù)

#存儲最短路徑長度

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

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 #返回兩個頂點(diǎn)之間的最短路徑長度與路徑矩陣

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

foruinrange(vNum):forvinrange(vNum):ifu==v: #同一個頂點(diǎn)的最短路徑為本身print('%s->%s的最短路徑為:%s'%(g.getVex(u),g.getVex(v),g.getVex(u)))7.5最短路徑continue '''兩個不同頂點(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)用最少的路線【問題描述】已知下圖為一個城市交通網(wǎng)，其中各頂點(diǎn)表示城市，邊的權(quán)值表示從一個城市到另一個城市的交通費(fèi)用?，F(xiàn)有一位旅客要從城市A到其他城市，設(shè)計算法找出一條路線，使得這位旅客從城市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)外的第一個結(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)相鄰接的下一個頂點(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個結(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個結(jié)點(diǎn)不存在'%u)ifv<0orv>=self.vNum:raiseException('第%s個結(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):

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

p=[([-1]*g.getVNum())foriinrange(g.getVNum())]#存儲當(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: #若兩個頂點(diǎn)之間存在邊

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

v=-1 #若兩個頂點(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,