《數(shù)據(jù)結構Python 語言描述》 第7章

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

第7章圖知識目標

第7章 理解圖的定義、基本術語和基本操作。 掌握圖的兩種存儲結構，包括鄰接矩陣和鄰接表。 掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷方法。 掌握圖的應用，包括最小生成樹、最短路徑、拓撲排序和關鍵路徑。圖技能目標

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

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

GRAPHKIND_UDG='UDG' #無向圖7.2圖的存儲結構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 #圖的頂點數(shù)

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

self.v=v #頂點列表

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

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

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

self.vNum=vNum #圖的頂點數(shù)【算法描述】7.2圖的存儲結構self.eNum=eNum #圖的邊數(shù)

self.v=[None]*vNum #構造頂點集

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

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

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

a,b,w=e[i] #輸入每條邊依附的頂點及權值

#返回頂點在圖中的位置

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

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

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

else: #輸出權值

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

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

=info #邊的權值

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

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

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

v=self.vself.v=[None]*self.vNum #構造表頭結點

foriinrange(self.vNum):self.v[i]=HNode(v[i]) #生成一個新的結點表7.2圖的存儲結構foriinrange(self.eNum):a,b=self.e[i] #輸入每條邊依附的兩個頂點

#返回頂點在圖中的位置

u,v=self.locateVex(a),self.locateVex(b)self.addArc(u,v,1) #插入邊結點

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

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

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

dFS(g,i) #訪問頂點并進行遍歷

defdFS(g,i):

visited[i]=True #對訪問過的頂點進行標記

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

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

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

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

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

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

q.inQueue(i) #將開始頂點插入隊尾

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

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

visited[u]=True #對訪問過的頂點進行標記

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

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

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

q.inQueue(v) #將頂點插入隊尾

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

self.lowCost=lowCost #到U中各頂點邊的權值的最小值

classMiniSpanTree:

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

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

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

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

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

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

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

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

#判斷權值的大小，將權值最小的邊加入最小生成樹

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

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

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

foriinrange(g.n):

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

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

j=0 #E中邊的下標

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

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

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

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

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

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

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

ifD[v]<sys.maxsize: #若兩個頂點之間存在邊

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

v=-1 #若兩個頂點之間不存在邊，初值為-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)過頂點v后的路徑小于不經(jīng)過頂點v的路徑，則經(jīng)過頂點v的路徑的權值之和為最短路徑長度'''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 #返回源點到其他頂點的最短路徑長度與路徑矩陣7.5最短路徑

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

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

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

#存儲最短路徑長度

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

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

#如果u不等于v，D[u][v]等于邊<u,v>的權值，否則為0D[u][v]=g.getArcs(u,v)ifu!=velse0ifu!=vandD[u][v]<sys.maxsize:p[u][v]=u #頂點v的前驅為uforkinrange(vNum):foriinrange(vNum):forjinrange(vNum)'''若利用中轉點后路徑變短，則修改最短路徑及其長度'''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 #返回兩個頂點之間的最短路徑長度與路徑矩陣

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

foruinrange(vNum):forvinrange(vNum):ifu==v: #同一個頂點的最短路徑為本身print('%s->%s的最短路徑為:%s'%(g.getVex(u),g.getVex(v),g.getVex(u)))7.5最短路徑continue '''兩個不同頂點之間的最短路徑'''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()同步訓練求城市之間交通費用最少的路線【問題描述】已知下圖為一個城市交通網(wǎng)，其中各頂點表示城市，邊的權值表示從一個城市到另一個城市的交通費用?，F(xiàn)有一位旅客要從城市A到其他城市，設計算法找出一條路線，使得這位旅客從城市A到其他城市所花費的交通費用最少。同步訓練求城市之間交通費用最少的路線【問題分析】該問題反映在圖上就是要找從頂點A到其他頂點的最短路徑，因此可以使用Dijkstra算法求解該問題，并用從頂點A到其他頂點的最短路徑及最短路徑長度表示從城市A到其他城市在交通費用最少情況下的路線及花銷。【代碼實現(xiàn)】importsysclassHNode: #表頭結點類

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

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

self.weight=weight #邊的權值

self.nextarc=None #與頂點相鄰接的下一個頂點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):同步訓練求城市之間交通費用最少的路線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])同步訓練求城市之間交通費用最少的路線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): #插入邊結點

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

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

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

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

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

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

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

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

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

ifD[v]<sys.maxsize: #若兩個頂點之間存在邊

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

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

forwinrange(g.getVNum()):

'''如果經(jīng)過頂點v后的路徑小于不經(jīng)過頂點v的路徑，則經(jīng)過頂點v的路徑的權值之和為最短路徑長度'''同步訓練求城市之間交通費用最少的路線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 #返回源點到其他頂點的最短路徑長度與路徑矩陣同步訓練求城市之間交通費用最少的路線'''輸出源點到其他頂點的最短路徑'''defprintDjikstraPath(g,v0,p):u=v0v0=g.locateVex(v0) #返回源點的位置

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

print('城市%s->城市%s:'%(u,v),end='')'''輸出最短路徑中經(jīng)過的各頂點'''ifp[i][0]!=-1:print(g.getVex(p[v0][0]),end='')同步訓練求城市之間交通費用最少的路線forkinrange(1,g.getVNum()):ifp[i][k]==-1:breakprint('->%s'%g.getVex(p[i][k]),end='')print()v=['A','B','C','D','E','F'] #頂點集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,