第8章數(shù)據(jù)結(jié)構(gòu) 圖

9.1圖的基本概念第8章圖9.2圖的存儲結(jié)構(gòu)9.3圖的遍歷9.4生成樹和最小生成樹9.5最短路徑9.6拓?fù)渑判虮菊滦〗Y(jié)9.7AOE網(wǎng)與關(guān)鍵路徑

(3)圖形結(jié)構(gòu)

結(jié)點(diǎn)之間關(guān)系：N：M，多對多。

特點(diǎn)：沒有開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，所有結(jié)點(diǎn)都可能有多個(gè)前驅(qū)結(jié)點(diǎn)和多個(gè)后繼結(jié)點(diǎn)。abcdfe9.1圖的基本概念9.1.1圖的定義

圖(Graph)G由兩個(gè)集合V(Vertex)和E(Edge)組成,記為G=(V,E),其中V是頂點(diǎn)的有限集合,記為V(G),E是連接V中兩個(gè)不同頂點(diǎn)(頂點(diǎn)對)的邊的有限集合,記為E(G)。

在圖G中,如果代表邊的頂點(diǎn)對是無序的,則稱G為無向圖,無向圖中代表邊的無序頂點(diǎn)對通常用圓括號括起來,用以表示一條無向邊，如（i，j）。如果表示邊的頂點(diǎn)對是有序的,則稱G為有向圖,在有向圖中代表邊的頂點(diǎn)對通常用尖括號括起來,如<i，j>。9.1.2圖的基本術(shù)語

1.端點(diǎn)和鄰接點(diǎn)在一個(gè)無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個(gè)端點(diǎn),并稱它們互為鄰接點(diǎn)。在一個(gè)有向圖中,若存在一條邊<vi,vj>,則稱此邊是頂點(diǎn)vi的一條出邊,同時(shí)也是頂點(diǎn)vj的一條入邊；稱vi和vj分別為此邊的起始端點(diǎn)(簡稱為起點(diǎn))和終止端點(diǎn)(簡稱終點(diǎn))；稱vi和vj互為鄰接點(diǎn)。2.頂點(diǎn)的度、入度和出度在無向圖中,頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。在有向圖中,以頂點(diǎn)vi為終點(diǎn)的入邊的數(shù)目,稱為該頂點(diǎn)的入度。以頂點(diǎn)vi為始點(diǎn)的出邊的數(shù)目,稱為該頂點(diǎn)的出度。一個(gè)頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。若一個(gè)圖中有n個(gè)頂點(diǎn)和e條邊,每個(gè)頂點(diǎn)的度為di(1≤i≤n),則有：3.完全圖若無向圖中的每兩個(gè)頂點(diǎn)之間都存在著一條邊,有向圖中的每兩個(gè)頂點(diǎn)之間都存在著方向相反的兩條邊,則稱此圖為完全圖。顯然,完全無向圖包含有n(n-1)/2條邊,完全有向圖包含有n(n-1)條邊。例如,圖(a)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全無向圖,共有6條邊。圖(b)所示的圖是一個(gè)具有4個(gè)頂點(diǎn)的完全有向圖,共有12條邊。

4.稠密圖、稀疏圖當(dāng)一個(gè)圖接近完全圖時(shí),則稱為稠密圖。相反,當(dāng)一個(gè)圖含有較少的邊數(shù)(即當(dāng)e<<n(n-1))時(shí),則稱為稀疏圖。

5.子圖設(shè)有兩個(gè)圖G=(V,E)和G’=(V’,E’),若V’是V的子集,即V’V,且E’是E的子集,即E’E,則稱G’是G的子圖。例如圖(b)是圖(a)的子圖,而圖(c)不是圖(a)的子圖。6.路徑和路徑長度在一個(gè)圖G=(V,E)中,從頂點(diǎn)vi到頂點(diǎn)vj的一條路徑是一個(gè)頂點(diǎn)序列(vi,vi1,vi2,…,vim,vj),若此圖G是無向圖,則邊(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)屬于E(G)；若此圖是有向圖,則<vi,vi1>,<vi1,vi2>,…,<vim-1,vim>,<vim,vj>屬于E(G)。

路徑長度是指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除開始點(diǎn)和結(jié)束點(diǎn)可以相同外,其余頂點(diǎn)均不相同,則稱此路徑為簡單路徑。例如,有圖中,(v0,v2,v1)就是一條簡單路徑,其長度為2。7.回路或環(huán)若一條路徑上的開始點(diǎn)與結(jié)束點(diǎn)為同一個(gè)頂點(diǎn),則此路徑被稱為回路或環(huán)。開始點(diǎn)與結(jié)束點(diǎn)相同的簡單路徑被稱為簡單回路或簡單環(huán)。例如,右圖中,(v0,v2,v1,v0)就是一條簡單回路,其長度為3。8.連通、連通圖和連通分量在無向圖G中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱vi和vj是連通的。若圖G中任意兩個(gè)頂點(diǎn)都連通,則稱G為連通圖,否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然,任何連通圖的連通分量只有一個(gè),即本身,而非連通圖有多個(gè)連通分量。9.強(qiáng)連通圖和強(qiáng)連通分量在有向圖G中,若從頂點(diǎn)vi到頂點(diǎn)vj有路徑,則稱從vi到vj是連通的。若圖G中的任意兩個(gè)頂點(diǎn)vi和vj都連通,即從vi到vj和從vj到vi都存在路徑,則稱圖G是強(qiáng)連通圖。例如,右邊兩個(gè)圖都是強(qiáng)連通圖。有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。顯然,強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量,即本身,非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。10.權(quán)和網(wǎng)圖中每一條邊都可以附有一個(gè)對應(yīng)的數(shù)值,這種與邊相關(guān)的數(shù)值稱為權(quán)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或花費(fèi)的代價(jià)。邊上帶有權(quán)的圖稱為帶權(quán)圖,也稱作網(wǎng)。

例9.1有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多需要多少條邊？最少需要多少條邊？

答：有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有n(n-1)條邊(構(gòu)成一個(gè)有向完全圖的情況)；最少有n條邊(n個(gè)頂點(diǎn)依次首尾相接構(gòu)成一個(gè)環(huán)的情況)。

9.2圖的存儲結(jié)構(gòu)

9.2.1鄰接矩陣存儲方法

鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n＞0)個(gè)頂點(diǎn)的圖,頂點(diǎn)的順序依次為(v0,v1,…,vn-1),則G的鄰接矩陣A是n階方陣,其定義如下：

(1)如果G是無向圖,則：

A[i][j]=1:若(vi,vj)∈E(G)0:其他

(2)如果G是有向圖,則：

A[i][j]=1:若<vi,vj>∈E(G)0:其他(3)如果G是帶權(quán)無向圖,則：

A[i][j]=wij:若vi≠vj且(vi,vj)∈E(G)0:i=j∞:其他(4)如果G是帶權(quán)有向圖,則：

A[i][j]=wij:若vi≠vj且<vi,vj>∈E(G)0:i=j∞:其他鄰接矩陣的特點(diǎn)如下：

(1)圖的鄰接矩陣表示是惟一的。

(2)無向圖的鄰接矩陣一定是一個(gè)對稱矩陣。因此,按照壓縮存儲的思想,在具體存放鄰接矩陣時(shí)只需存放上(或下)三角形陣的元素即可。

(3)不帶權(quán)的有向圖的鄰接矩陣一般來說是一個(gè)稀疏矩陣,因此,當(dāng)圖的頂點(diǎn)較多時(shí),可以采用三元組表的方法存儲鄰接矩陣。

(4)對于無向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)vi的度。

(5)對于有向圖,鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)vi的出度(或入度)。

(6)用鄰接矩陣方法存儲圖,很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連。但是,要確定圖中有多少條邊,則必須按行、按列對每個(gè)元素進(jìn)行檢測,所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲圖的局限性。鄰接矩陣的數(shù)據(jù)類型定義如下：#defineMAXV<最大頂點(diǎn)個(gè)數(shù)> typedefstruct{intno; /*頂點(diǎn)編號*/InfoTypeinfo; /*頂點(diǎn)其他信息*/}VertexType; /*頂點(diǎn)類型*/typedefstruct /*圖的定義*/{intedges[MAXV][MAXV]; /*鄰接矩陣*/intvexnum,arcnum; /*頂點(diǎn)數(shù),弧數(shù)*/VertexTypevexs[MAXV]; /*存放頂點(diǎn)信息*/}MGraph;9.2.2鄰接表存儲方法

圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲方法。在鄰接表中,對圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊(對有向圖是以頂點(diǎn)vi為尾的弧)。每個(gè)單鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)。表結(jié)點(diǎn)和表頭結(jié)點(diǎn)的結(jié)構(gòu)如下：

adjvex指與頂點(diǎn)vi鄰接的頂點(diǎn)的編號nextarc指向下一條邊或弧的結(jié)點(diǎn),info存儲與邊或弧相關(guān)的信息,如權(quán)值等。data存儲頂點(diǎn)vi的名稱或其他信息,firstarc指向鏈表中第一個(gè)結(jié)點(diǎn)。adjvexnextarcinfodatafirstarc表結(jié)點(diǎn)表頭結(jié)點(diǎn)鄰接表的特點(diǎn)如下：

(1)鄰接表表示不惟一。這是因?yàn)樵诿總€(gè)頂點(diǎn)對應(yīng)的單鏈表中,各邊結(jié)點(diǎn)的鏈接次序可以是任意的,取決于建立鄰接表的算法以及邊的輸入次序。

(2)對于有n個(gè)頂點(diǎn)和e條邊的無向圖,其鄰接表有n個(gè)表頭結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)。顯然,在總的邊數(shù)小于n(n-1)/2的情況下,鄰接表比鄰接矩陣要節(jié)省空間。

(3)對于無向圖,鄰接表的頂點(diǎn)vi對應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目正好是頂點(diǎn)vi的度。

(4)對于有向圖,鄰接表的頂點(diǎn)vi對應(yīng)的第i個(gè)鏈表的邊結(jié)點(diǎn)數(shù)目僅僅是vi的出度。其入度為鄰接表中所有adjvex域值為i的邊結(jié)點(diǎn)數(shù)目。鄰接表存儲結(jié)構(gòu)的定義如下：typedefstructANode /*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*/{ intadjvex;/*該弧的終點(diǎn)位置*/ structANode*nextarc;/*指向下一條弧的指針*/ InfoTypeinfo; /*該弧的相關(guān)信息*/}ArcNode;typedefstructVnode/*鄰接表頭結(jié)點(diǎn)的類型*/{ Vertexdata; /*頂點(diǎn)信息*/ ArcNode*firstarc;/*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist; /*鄰接表*/intn,e; /*圖中頂點(diǎn)數(shù)n和邊數(shù)e*/}ALGraph; /*圖的類型*/

例9.2給定一個(gè)具有n個(gè)結(jié)點(diǎn)的無向圖的鄰接矩陣和鄰接表。

(1)設(shè)計(jì)一個(gè)將鄰接矩陣轉(zhuǎn)換為鄰接表的算法；

(2)設(shè)計(jì)一個(gè)將鄰接表轉(zhuǎn)換為鄰接矩陣的算法；

(3)分析上述兩個(gè)算法的時(shí)間復(fù)雜度。解：(1)在鄰接矩陣上查找值不為0的元素,找到這樣的元素后創(chuàng)建一個(gè)表結(jié)點(diǎn)并在鄰接表對應(yīng)的單鏈表中采用前插法插入該結(jié)點(diǎn)。算法如下：voidMatToList(MGraphg,ALGraph*&G)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/{inti,j,n=g.vexnum;ArcNode*p; /*n為頂點(diǎn)數(shù)*/G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)/*給所有頭結(jié)點(diǎn)的指針域置初值*/G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++) /*檢查鄰接矩陣中每個(gè)元素*/

for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0) {p=(ArcNode*)malloc(sizeof(ArcNode));/*創(chuàng)建結(jié)點(diǎn)*p*/ p->adjvex=j; p->nextarc=G->adjlist[i].firstarc;/*將*p鏈到鏈表后*/ G->adjlist[i].firstarc=p; } G->n=n;G->e=g.arcnum;}

(2)在鄰接表上查找相鄰結(jié)點(diǎn),找到后修改相應(yīng)鄰接矩陣元素的值。算法如下：

voidListToMat(ALGraph*G,MGraph&g){inti,j,n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL) {g.edges[i][p->adjvex]=1; p=p->nextarc; }}g.vexnum=n;g.arcnum=G->e;}

(3)算法1的時(shí)間復(fù)雜度均為O(n2)。算法2的時(shí)間復(fù)雜度為O(n+e),其中e為圖的邊數(shù)。9.3圖的遍歷9.3.1圖的遍歷的概念

從給定圖中任意指定的頂點(diǎn)(稱為初始點(diǎn))出發(fā),按照某種搜索方法沿著圖的邊訪問圖中的所有頂點(diǎn),使每個(gè)頂點(diǎn)僅被訪問一次,這個(gè)過程稱為圖的遍歷。

如果給定圖是連通的無向圖或者是強(qiáng)連通的有向圖,則遍歷過程一次就能完成,并可按訪問的先后順序得到由該圖所有頂點(diǎn)組成的一個(gè)序列。根據(jù)搜索方法的不同,圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法(DFS)；另一種叫做廣度優(yōu)先搜索法(BFS)。

9.3.2深度優(yōu)先搜索遍歷

深度優(yōu)先搜索遍歷的過程是：從圖中某個(gè)初始頂點(diǎn)v出發(fā),首先訪問初始頂點(diǎn)v,然后選擇一個(gè)與頂點(diǎn)v相鄰且沒被訪問過的頂點(diǎn)w為初始頂點(diǎn),再從w出發(fā)進(jìn)行深度優(yōu)先搜索,直到圖中與當(dāng)前頂點(diǎn)v鄰接的所有頂點(diǎn)都被訪問過為止。

例如,以上圖的鄰接表為例調(diào)用DFS()函數(shù),假設(shè)初始頂點(diǎn)編號v=2,見教材205。9.3.2深度優(yōu)先搜索遍歷以鄰接表為存儲結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法如下(其中,v是初始頂點(diǎn)編號,visited[]是一個(gè)全局?jǐn)?shù)組,初始時(shí)所有元素均為0表示所有頂點(diǎn)尚未訪問過)：

voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1; /*置已訪問標(biāo)記*/printf("%d",v); /*輸出被訪問頂點(diǎn)的編號*/p=G->adjlist[v].firstarc; /*p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)*/while(p!=NULL){if(visited[p->adjvex]==0)DFS(G,p->adjvex);/*若p->adjvex頂點(diǎn)未訪問,遞歸訪問它*/ p=p->nextarc; /*p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)*/}}9.3.3廣度優(yōu)先搜索遍歷

廣度優(yōu)先搜索遍歷的過程是：首先訪問初始點(diǎn)vi,接著訪問vi的所有未被訪問過的鄰接點(diǎn)vi1,vi2,…,vit,然后再按照vi1,vi2,…,vit的次序,訪問每一個(gè)頂點(diǎn)的所有未被訪問過的鄰接點(diǎn),依次類推,直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問過為止。

例如,以上圖的鄰接表為例調(diào)用BFS()函數(shù),假設(shè)初始頂點(diǎn)編號v=2,見教材206。9.3.3廣度優(yōu)先搜索遍歷以鄰接表為存儲結(jié)構(gòu),用廣度優(yōu)先搜索遍歷圖時(shí),需要使用一個(gè)隊(duì)列,以類似于按層次遍歷二叉樹遍歷圖。對應(yīng)的算法如下(其中,v是初始頂點(diǎn)編號)：

voidBFS(ALGraph*G,intv){ArcNode*p;intw,i;intqueue[MAXV],front=0,rear=0; /*定義循環(huán)隊(duì)列*/intvisited[MAXV];/*定義存放結(jié)點(diǎn)的訪問標(biāo)志的數(shù)組*/for(i=0;i<G->n;i++)visited[i]=0;/*訪問標(biāo)志數(shù)組初始化*/printf("%2d",v);/*輸出被訪問頂點(diǎn)的編號*/visited[v]=1;/*置已訪問標(biāo)記*/rear=(rear+1)%MAXV;queue[rear]=v; /*v進(jìn)隊(duì)*/

while(front!=rear) /*若隊(duì)列不空時(shí)循環(huán)*/ {front=(front+1)%MAXV; w=queue[front];/*出隊(duì)并賦給w*/ p=G->adjlist[w].firstarc;/*找w的第一個(gè)的鄰接點(diǎn)*/ while(p!=NULL) { if(visited[p->adjvex]==0) { printf(“%2d”,p->adjvex); /*訪問之*/ visited[p->adjvex]=1; rear=(rear+1)%MAXV;/*該頂點(diǎn)進(jìn)隊(duì)*/ queue[rear]=p->adjvex; } p=p->nextarc;/*找下一個(gè)鄰接頂點(diǎn)*/ } } printf("\n");}9.3.4非連通圖的遍歷

對于無向圖來說,若無向圖是連通圖,則一次遍歷能夠訪問到圖中的所有頂點(diǎn)；但若無向圖是非連通圖,則只能訪問到初始點(diǎn)所在連通分量中的所有頂點(diǎn),其他連通分量中的頂點(diǎn)是不可能訪問到的。為此需要從其他每個(gè)連通分量中選擇初始點(diǎn),分別進(jìn)行遍歷,才能夠訪問到圖中的所有頂點(diǎn)；

對于有向圖來說,若從初始點(diǎn)到圖中的每個(gè)頂點(diǎn)都有路徑,則能夠訪問到圖中的所有頂點(diǎn)；否則不能訪問到所有頂點(diǎn),為此同樣需要再選初始點(diǎn),繼續(xù)進(jìn)行遍歷,直到圖中的所有頂點(diǎn)都被訪問過為止。采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下：DFS1(ALGraph*g){inti;for(i=0;i<g->n;i+)/*遍歷所有未訪問過的頂點(diǎn)*/if(visited[i]==0)DFS(g,i);}采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下：BFS1(ALGraph*g){inti;for(i=0;i<g->n;i+)/*遍歷所有未訪問過的頂點(diǎn)*/if(visited[i]==0)BFS(g,i);}9.4生成樹和最小生成樹9.4.1生成樹的概念

一個(gè)連通圖的生成樹是一個(gè)極小連通子圖,它含有圖中全部頂點(diǎn),但只有構(gòu)成一棵樹的(n-1)條邊。如果在一棵生成樹上添加一條邊,必定構(gòu)成一個(gè)環(huán)：因?yàn)檫@條邊使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。

一棵有n個(gè)頂點(diǎn)的生成樹(連通無回路圖)有且僅有(n-1)條邊,如果一個(gè)圖有n個(gè)頂點(diǎn)和小于(n-1)條邊,則是非連通圖。如果它多于(n-1)條邊,則一定有回路。但是,有(n-1)條邊的圖不一定都是生成樹。

對于一個(gè)帶權(quán)(假定每條邊上的權(quán)均為大于零的實(shí)數(shù))連通無向圖G中的不同生成樹,其每棵樹的所有邊上的權(quán)值之和也可能不同；圖的所有生成樹中具有邊上的權(quán)值之和最小的樹稱為圖的最小生成樹。按照生成樹的定義,n個(gè)頂點(diǎn)的連通圖的生成樹有n個(gè)頂點(diǎn)、n-1條邊。因此,構(gòu)造最小生成樹的準(zhǔn)則有三條：

(1)必須只使用該圖中的邊來構(gòu)造最小生成樹；

(2)必須使用且僅使用n-1條邊來連接圖中的n個(gè)頂點(diǎn)；

(3)不能使用產(chǎn)生回路的邊。9.4.2無向圖的連通分量和生成樹

在對無向圖進(jìn)行遍歷時(shí),對于連通圖,僅需調(diào)用遍歷過程(DFS或BFS)一次,從圖中任一頂點(diǎn)出發(fā),便可以遍歷圖中的各個(gè)頂點(diǎn)。對非連通圖,則需多次調(diào)用遍歷過程,每次調(diào)用得到的頂點(diǎn)集連同相關(guān)的邊就構(gòu)成圖的一個(gè)連通分量。設(shè)G=(V,E)為連通圖,則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí),必定將E(G)分成兩個(gè)集合T和B,其中T是遍歷圖過程中走過的邊的集合,B是剩余的邊的集合：T∩B=Φ,T∪B=E(G)。顯然,G'=(V,T)是G的極小連通子圖,即G'是G的一棵生成樹。

由深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；由廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。這樣的生成樹是由遍歷時(shí)訪問過的n個(gè)頂點(diǎn)和遍歷時(shí)經(jīng)歷的n-1條邊組成。對于非連通圖,每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過的邊一起構(gòu)成一棵生成樹,各個(gè)連通分量的生成樹組成非連通圖的生成森林。9.4.4普里姆算法

普里姆(Prim)算法是一種構(gòu)造性算法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖,T=(U,TE)是G的最小生成樹,其中U是T的頂點(diǎn)集,TE是T的邊集,則由G構(gòu)造最小生成樹T的步驟如下：(1)初始化U={v0}。v0到其他頂點(diǎn)的所有邊為候選邊；

(2)重復(fù)以下步驟n-1次,使得其他n-1個(gè)頂點(diǎn)被加入到U中：①從候選邊中挑選權(quán)值最小的邊輸出,設(shè)該邊在V-U中的頂點(diǎn)是v,將v加入U(xiǎn)中；②考察當(dāng)前V-U中的所有頂點(diǎn)vi,修改候選邊：若(v,vi)的權(quán)值小于原來和vi關(guān)聯(lián)的候選邊,則用(v,vi)取代后者作為候選邊。普里姆算法求解最小生成樹的過程9.4.5克魯斯卡爾算法

克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖,T=(U,TE)是G的最小生成樹,則構(gòu)造最小生成樹的步驟如下：

(1)置U的初值等于V(即包含有G中的全部頂點(diǎn)),TE的初值為空集(即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。

(2)將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路,則加入TE；否則舍棄,直到TE中包含(n-1)條邊為止?？唆斔箍査惴ㄇ蠼庾钚∩蓸涞倪^程9.5最短路徑9.5.1路徑的概念

在一個(gè)無權(quán)的圖中,若從一頂點(diǎn)到另一頂點(diǎn)存在著一條路徑,則稱該路徑長度為該路徑上所經(jīng)過的邊的數(shù)目,它等于該路徑上的頂點(diǎn)數(shù)減1。由于從一頂點(diǎn)到另一頂點(diǎn)可能存在著多條路徑,每條路徑上所經(jīng)過的邊數(shù)可能不同,即路徑長度不同,我們把路徑長度最短(即經(jīng)過的邊數(shù)最少)的那條路徑叫做最短路徑,其路徑長度叫做最短路徑長度或最短距離。

對于帶權(quán)的圖,考慮路徑上各邊上的權(quán)值,則通常把一條路徑上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長度或稱帶權(quán)路徑長度。從源點(diǎn)到終點(diǎn)可能不止一條路徑,把帶權(quán)路徑長度最短的那條路徑稱為最短路徑,其路徑長度(權(quán)值之和)稱為最短路徑長度或者最短距離。8.5.2從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑

問題：給定一個(gè)帶權(quán)有向圖G與源點(diǎn)v,求從v到G中其他頂點(diǎn)的最短路徑,并限定各邊上的權(quán)值大于或等于0。

采用狄克斯特拉(Dijkstra)算法求解基本思想是：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖,把圖中頂點(diǎn)集合V分成兩組：第一組為已求出最短路徑的頂點(diǎn)集合(用S表示,初始時(shí)S中只有一個(gè)源點(diǎn),以后每求得一條最短路徑v,…vk,就將vk加入到集合S中,直到全部頂點(diǎn)都加入到S中,算法就結(jié)束了)

第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示)。

按最短路徑長度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過程中,總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長度。此外,每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離,S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長度,U中的頂點(diǎn)的距離從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長度。

狄克斯特拉算法的具體步驟如下：

(1)初始時(shí),S只包含源點(diǎn),即S={v},v的距離為0。U包含除v外的其他頂點(diǎn),U中頂點(diǎn)u距離為邊上的權(quán)(若v與u有邊<v,u>)或∞(若u不是v的出邊鄰接點(diǎn))。

(2)從U中選取一個(gè)距離v最小的頂點(diǎn)k,把k加入S中(該選定的距離就是v到k的最短路徑長度cvk)。

(3)以k為新考慮的中間點(diǎn),修改U中各頂點(diǎn)的距離：若從源點(diǎn)v到頂點(diǎn)u(u∈U)的距離(經(jīng)過頂點(diǎn)k,cvk+wku)比原來距離(不經(jīng)過頂點(diǎn)k，cvu)短,則修改頂點(diǎn)u的距離值為cvk+wku

。

(4)重復(fù)步驟(2)和(3)直到所有頂點(diǎn)都包含在S中。V到j(luò)的最小距離＝MIN(cvk+wkj,cvj)S U dist[]path[]01234560123456{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,0,0,0,-1,-1,-1}{0,1}{2,3,4,5,6}{0,4,5,6,11,∞,∞}{0,0,1,0,1,-1,-1}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,∞}{0,0,1,0,1,2,-1}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,0,1,0,5,2,5}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}{0,0,1,0,5,2,4}8.5.3每對頂點(diǎn)之間的最短路徑

問題：對于一個(gè)各邊權(quán)值均大于零的有向圖,對每一對頂點(diǎn)vi≠vj,求出vi與vj之間的最短路徑和最短路徑長度。可以通過以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對頂點(diǎn)之間的最短路徑。除此之外,弗洛伊德(Floyd)算法也可用于求兩頂點(diǎn)之間最短路徑。

假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲,另外設(shè)置一個(gè)二維數(shù)組A用于存放當(dāng)前頂點(diǎn)之間的最短路徑長度,分量A[i][j]表示當(dāng)前頂點(diǎn)vi到頂點(diǎn)vj的最短路徑長度。弗洛伊德算法的基本思想是遞推產(chǎn)生一個(gè)矩陣序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k的最短路徑長度。

初始時(shí),有A-1[i][j]=cost[i][j]。當(dāng)求從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k+1的最短路徑長度時(shí),要分兩種情況考慮：一種情況是該路徑不經(jīng)過頂點(diǎn)編號為k+1的頂點(diǎn),此時(shí)該路徑長度與從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k的最短路徑長度相同；另一種情況是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑上經(jīng)過編號為k+1的頂點(diǎn)。Ak+1[i,j]=MIN(Ak[i,j],Ak[i,k+1]+Ak[k+1,j]

那么,該路徑可分為兩段:(1)從頂點(diǎn)vi到頂點(diǎn)vk+1的最短路徑;(2)從頂點(diǎn)vk+1到頂點(diǎn)vj的最短路徑。此時(shí)最短路徑長度等于這兩段路徑長度之和。這兩種情況中的較小值,就是所要求的從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過的頂點(diǎn)編號不大于k+1的最短路徑。

弗洛伊德思想可用如下的表達(dá)式來描述：

A-1[i][j]=cost[i][j]Ak+1[i][j]=MIN{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1)

采用弗洛伊德算法求解過程

考慮頂點(diǎn)v0,A0[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v0的最短路徑。只有從v2到v1經(jīng)過v0的路徑和從v2到v3經(jīng)過v0的路徑,不影響v2到v1和v2到v3的路徑長度,因此,有：

考慮頂點(diǎn)v1,A1[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v1的最短路徑。存在路徑v0-v1-v2,路徑長度為9,將A[0][2]改為9,path[0][2]改為1,因此,有：

考慮頂點(diǎn)v2,A2[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v2的最短路徑。存在路徑v3-v2-v0,長度為4,將A[3][0]改為4；存在路徑v3-v2-v1,長度為4,將A[3][1]改為4。存在路徑v1-v2-v0,長度為7,將A[1][0]改為7。將path[3][0]、path[3][1]和path[1][0]均改為2。因此,有：

考慮頂點(diǎn)v3,A3[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v3的最短路徑。存在路徑v0-v3-v2,長度為8比原長度短,將A[0][2]改為8；存在路徑v1-v3-v2-v0,長度為6(A[1][3]+A[3][0]=2+4=6)比原長度短,將A[1][0]改為6；存在路徑v1-v3-v2,長度為3,比原長度短,將A[1][2]改為3；將path[0][2]、path[1][0]后path[1][2]均改為3。因此,有：

從0到0路徑為：0,0 路徑長度為：0從0到1路徑為：0,1 路徑長度為：5從0到2路徑為：0,3,2 路徑長度為：8從0到3路徑為：0,3 路徑長度為：7從1到0路徑為：1,3,2,0 路徑長度為：6從1到1路徑為：1,1 路徑長度為：0從1到2路徑為：1,3,2 路徑長度為：3從1到3路徑為：1,3 路徑長度為：2A=Path=從2到0路徑為：2,0 路徑長度為：3從2到1路徑為：2,1 路徑長度為：3從2到2路徑為：2,2 路徑長度為：0從2到3路徑為：2,3 路徑長度為：2從3到0路徑為：3,2,0 路徑長度為：4從3到1路徑為：3,2,1 路徑長度為：4從3到2路徑為：3,2 路徑長度為：1從3到3路徑為：3,3 路徑長度為：09.6拓?fù)渑判?/p>

設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖,V中頂點(diǎn)序列v1,v2,…,vn稱為一個(gè)拓?fù)湫蛄?當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足下列條件：

若<vi,vj>是圖中的邊(即從頂點(diǎn)vi到vj有一條路徑),則在序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。在一個(gè)有向圖中找一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。課程代號課程名稱先修課程C1高等數(shù)學(xué)無C2程序設(shè)計(jì)無C3離散數(shù)學(xué)C1C4數(shù)據(jù)結(jié)構(gòu)C2,C3C5編譯原理C2,C4C6操作系統(tǒng)C4,C7C7計(jì)算機(jī)組成原理C2

例如,計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè),假設(shè)這些課程的名稱與相應(yīng)代號有如下關(guān)系：課程之間的先后關(guān)系可用有向圖表示：

對這個(gè)有向圖進(jìn)行拓?fù)渑判蚩傻玫揭粋€(gè)拓?fù)湫蛄校篊1-C3-C2-C4-C7-C6-C5。也可得到另一個(gè)拓?fù)湫蛄校篊2-C7-C1-C3-C4-C5-C6,還可以得到其他的拓?fù)湫蛄?。學(xué)生按照任何一個(gè)拓?fù)湫蛄卸伎梢皂樞虻剡M(jìn)行課程學(xué)習(xí)。

拓?fù)渑判蚍椒ㄈ缦拢?/p>

(1)從有向圖中選擇一個(gè)沒有前驅(qū)(即入度為0)的頂點(diǎn)并且輸出它。

(2)從網(wǎng)中刪去該頂點(diǎn),并且刪去從該頂點(diǎn)發(fā)出的全部有向邊。

(3)重復(fù)上述兩步,直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點(diǎn)為止。

為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?對于給定的有向圖,采用鄰接表作為存儲結(jié)構(gòu),為每個(gè)頂點(diǎn)設(shè)立一個(gè)鏈表,每個(gè)鏈表有一個(gè)表頭結(jié)點(diǎn),這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組,