數(shù)據(jù)結(jié)構(gòu)第六章-圖課件

第六章

圖數(shù)據(jù)結(jié)構(gòu)第六章圖數(shù)據(jù)結(jié)構(gòu)16.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)方式6.3圖的遍歷 6.4圖與最小生成樹 6.5AOV網(wǎng)與拓?fù)渑判?6.6AOE網(wǎng)與關(guān)鍵路徑 6.7最短路徑 6.8本章實(shí)戰(zhàn)練習(xí) 6.9小結(jié) 第六章6.1圖的定義和基本術(shù)語第六章26.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)方式6.3圖的遍歷 6.4圖與最小生成樹 6.5AOV網(wǎng)與拓?fù)渑判?6.6AOE網(wǎng)與關(guān)鍵路徑 6.7最短路徑 6.8本章實(shí)戰(zhàn)練習(xí) 6.9小結(jié) 第六章6.1圖的定義和基本術(shù)語第六章36.1圖的定義和基本術(shù)語圖形結(jié)構(gòu)是一種比線性表和樹形結(jié)構(gòu)更復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)中，數(shù)據(jù)元素之間具有單一的線性關(guān)系；樹形結(jié)構(gòu)中，節(jié)點(diǎn)間具有一對(duì)多的分支層次關(guān)系。在圖形結(jié)構(gòu)中，任意兩個(gè)結(jié)點(diǎn)間可能有關(guān)系也可能根本不存在任何關(guān)聯(lián)，結(jié)點(diǎn)間是多對(duì)多的復(fù)雜關(guān)系。可以說，樹是圖的特例，線性表是樹的特例。在現(xiàn)實(shí)中有很多問題可以抽象成為圖的形式，因此借助圖的結(jié)構(gòu)和技術(shù)可以解決很多實(shí)際應(yīng)用問題。圖有著雄厚的理論基礎(chǔ)，離散數(shù)學(xué)中，我們已經(jīng)學(xué)過有關(guān)圖的一些理論，關(guān)系代數(shù)和圖論中也詳細(xì)介紹了圖的基本理論知識(shí)。本章重點(diǎn)介紹圖在計(jì)算機(jī)中的存儲(chǔ)表示和它的基本操作的實(shí)現(xiàn)。6.1圖的定義和基本術(shù)語圖形結(jié)構(gòu)是一種比線性表和樹形結(jié)構(gòu)46.1.1圖的定義圖（Graph）是由有窮非空定點(diǎn)集合和邊（或弧）構(gòu)成的。采用形式化的定義，圖是由兩個(gè)集合V（Vertex）和E（Edge）組成，記作G=（V,E）。其中V是頂點(diǎn)的有限集合，記為V（G），E是連接V中兩個(gè)不同定點(diǎn)（即頂點(diǎn)對(duì)）的邊的有限集合，記為E（G）。圖的抽象數(shù)據(jù)類型定義如下：ADTGraph{

數(shù)據(jù)對(duì)象：D={ai|1≤i≤n,n≥0,ai

屬于ElemType類型}/*ElemType是C/C++中自定義的類型標(biāo)識(shí)符*/

6.1.1圖的定義圖（Graph）是由有窮非空定點(diǎn)集合和56.1.1圖的定義

6.1.1圖的定義

66.1.1圖的定義（2）對(duì)頂點(diǎn)的操作 LocateVex(G,x);/*查找頂點(diǎn)即在圖G中查找頂點(diǎn)x并返回該頂點(diǎn)在圖中的位置*/ GetVex(G,x);/*在圖G中查找到頂點(diǎn)x并返回x的值*/PutVex(&G,v,value);/*為頂點(diǎn)v賦值*/ InsertVex(&G,x);/*在圖G中增加頂點(diǎn)v*/ DeleteVex(&G,v);/*在圖G中刪除頂點(diǎn)v*/

6.1.1圖的定義（2）對(duì)頂點(diǎn)的操作76.1.1圖的定義（3）對(duì)邊的操作 InsertArc(&G,v,w);/*若G是有向圖，則增加弧<v,w>；若G是無向圖，則增加弧<v,w>和<w,v>*/ DeleteArc(&G,v,w);/*若G是有向圖，則刪除弧<v,w>；若G是無向圖，則刪除弧<v,w>和<w,v>*/（4）對(duì)鄰接點(diǎn)的操作 FirstAdjVex(G,v);/*返回v的第一個(gè)鄰接頂點(diǎn)，若v沒有鄰接頂點(diǎn)則返回“空”*/ NextAdjVex(G,x,w);/*返回v的（相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)。若w是v的最后一個(gè)鄰接頂點(diǎn)，則返回“空”*/6.1.1圖的定義（3）對(duì)邊的操作86.1.1圖的定義（5）圖的遍歷 DFSTra(g);/*深度優(yōu)先遍歷圖*/ BFSTra(g);/*廣度優(yōu)先遍歷圖*/

…}ADTGraphV（G）是頂點(diǎn)的有限集合，通常用字母或者自然數(shù)（頂點(diǎn)編號(hào)）來標(biāo)識(shí)圖中頂點(diǎn)。規(guī)定第i個(gè)頂點(diǎn)，即編號(hào)為i的頂點(diǎn)用vi表示；E（G）是圖中邊的集合，它確定了圖G的數(shù)據(jù)元素的關(guān)系，E（G）可以為空集，此時(shí)表示圖G只有頂點(diǎn)沒有邊，也就是說，頂點(diǎn)和頂點(diǎn)之間沒有任何關(guān)系。6.1.1圖的定義（5）圖的遍歷96.1.2圖的基本術(shù)語

圖6.1無向圖G1

圖6.2有向圖G26.1.2圖的基本術(shù)語

圖6.1無向圖G1圖6.2106.1.2圖的基本術(shù)語

6.1.2圖的基本術(shù)語

116.1.2圖的基本術(shù)語完全圖（Completedgraph）：如果無向圖中任意兩個(gè)頂點(diǎn)間都存在邊，則稱之為無向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的無向完全圖中，邊數(shù)為n(n-1)/2條。如果有向圖中任意兩個(gè)頂點(diǎn)間都存在方向互為相反的兩條弧，則稱之為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，邊數(shù)為n(n-1)條。稠密圖、稀疏圖：有很少條便或者弧的圖成為稀疏圖（Sparsegraph），反之稱為稠密圖（Densegraph）。度：頂點(diǎn)v的度是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)。有向圖中，以頂點(diǎn)v為頭的弧的數(shù)目稱為v的入度（InDegree），記為ID(v)。以頂點(diǎn)v為尾的弧的數(shù)目稱為v的出度（OutDegree），記為OD(v)。TD(v)=ID(v)+OD(v)。無向圖不區(qū)分入度和出度。6.1.2圖的基本術(shù)語完全圖（Completedgra126.1.2圖的基本術(shù)語權(quán)、網(wǎng)：在邊或者弧上的數(shù)據(jù)信息稱為權(quán)（Weight）。權(quán)值可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或者耗費(fèi)。帶權(quán)的圖稱為網(wǎng)（Network）。路徑、路徑長(zhǎng)度：頂點(diǎn)vi到頂點(diǎn)vj的路徑（Path）是指從頂點(diǎn)vi到頂點(diǎn)vj之間所經(jīng)歷的頂點(diǎn)序列vi，vi，1…vi,m，vj，其中（vi，vi,1）（vi，m，vj）和（vi，j，vi,j+1）∈E，1≤j≤m-1都是圖中的邊。路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目。回路、簡(jiǎn)單路徑、簡(jiǎn)單回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)（Cycle）。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路或者簡(jiǎn)單環(huán)。6.1.2圖的基本術(shù)語權(quán)、網(wǎng)：在邊或者弧上的數(shù)據(jù)信息稱為136.1.2圖的基本術(shù)語連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量：無向圖G中，，如果從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱vi和vj是連通的。如果對(duì)于圖中任意兩個(gè)頂點(diǎn)vi、vj∈V，vi和vj都是連通的，則稱圖G的連通圖（ConnectedGraph）。無向圖中的極大連通子圖稱為連通分量（ConnectedComponent）。例如：圖6.3中的G3就是一個(gè)連通圖。而G4就是非連通圖，但有2個(gè)連通分量，如圖6.4所示。

非連通圖G4

G4的兩個(gè)連通分量

圖6.46.1.2圖的基本術(shù)語連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通146.1.2圖的基本術(shù)語有向圖G中，如果從vi到vj并且從vj到vi都有路徑，則稱圖G是強(qiáng)連通圖。有向圖中的極大連通子圖稱作有向圖的強(qiáng)連通分量。例如：圖6.5中的G5就是一個(gè)強(qiáng)連通圖。而G6就是非強(qiáng)連通圖，但有2個(gè)強(qiáng)連通分量，如圖6.6所示。

圖6.5強(qiáng)連通圖G5

非強(qiáng)連通圖G6

G6的兩個(gè)強(qiáng)連通分量

圖6.66.1.2圖的基本術(shù)語有向圖G中，如果從vi到vj并且從156.1.2圖的基本術(shù)語生成樹：連通圖G的生成樹，是包含G的全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖，該極小連通子圖有（n-1）條邊。如圖6.7所示，是連通圖G3的生成樹。如果在一棵生成樹上添加一條邊，必定構(gòu)成一個(gè)環(huán)，因?yàn)檫@條邊的出現(xiàn)使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。一棵有n個(gè)頂點(diǎn)的生成樹有且僅有（n-1）條邊。如果一個(gè)圖有n個(gè)頂點(diǎn)和小于（n-1）條邊，則是非連通圖。如果它多于（n-1）條邊，則一定有環(huán)。但需要大家注意的是，有（n-1）條邊的圖不一定是生成樹。右圖6.76.1.2圖的基本術(shù)語生成樹：連通圖G的生成樹，是包含G166.1.2圖的基本術(shù)語生成森林：如果一個(gè)有向圖有且僅有一個(gè)頂點(diǎn)的入度為0，其他頂點(diǎn)的入度均為1，則這個(gè)圖是一棵有向樹。當(dāng)一個(gè)有向圖有多個(gè)頂點(diǎn)的入度為0時(shí)，它的生成森林是由多棵有向樹構(gòu)成。其中，這個(gè)生成森林含有圖中全部頂點(diǎn)和相應(yīng)的弧。如圖6.8所示是有向圖G7及其生成森林。

有向圖G7G7的生成森林圖6.86.1.2圖的基本術(shù)語生成森林：如果一個(gè)有向圖有且僅有一176.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)方式6.3圖的遍歷 6.4圖與最小生成樹 6.5AOV網(wǎng)與拓?fù)渑判?6.6AOE網(wǎng)與關(guān)鍵路徑 6.7最短路徑 6.8本章實(shí)戰(zhàn)練習(xí) 6.9小結(jié) 第六章6.1圖的定義和基本術(shù)語第六章186.2圖的存儲(chǔ)方式圖是一種結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，圖的信息包括頂點(diǎn)和邊兩部分。由于任意的兩個(gè)頂點(diǎn)之間可能存在聯(lián)系，因此不能用數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來表示元素之間的關(guān)系，即圖不能用順序映像的存儲(chǔ)結(jié)構(gòu)。但是可以借助數(shù)組的數(shù)據(jù)類型表示元素之間的關(guān)系。多重鏈表是一種最簡(jiǎn)單的鏈?zhǔn)接诚窠Y(jié)構(gòu)，以一個(gè)由數(shù)據(jù)域和指針域組成的結(jié)點(diǎn)表示圖的一個(gè)頂點(diǎn)。其中，數(shù)據(jù)域存儲(chǔ)頂點(diǎn)信息，指針域可以有多個(gè)用來存儲(chǔ)指向其鄰接點(diǎn)的指針。如圖6.9所示為圖6.1無向圖G1、圖6.2有向圖G2的多重鏈表。6.2圖的存儲(chǔ)方式圖是一種結(jié)構(gòu)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，圖的信息包19

無向圖G1多重鏈表有向圖G2的多重鏈表圖6.96.2圖的存儲(chǔ)方式由于每個(gè)頂點(diǎn)的度不一定相同，因此在設(shè)計(jì)結(jié)點(diǎn)結(jié)構(gòu)時(shí)應(yīng)該根據(jù)實(shí)際需要進(jìn)行操作，設(shè)計(jì)恰當(dāng)?shù)慕Y(jié)點(diǎn)結(jié)構(gòu)和表結(jié)構(gòu)以獲得相對(duì)較好的存儲(chǔ)單元的利用率。常用的有數(shù)組表示法、鄰接表表示法、鄰接多重表表示法和十字鏈表表示法。無向圖G1多重鏈表有向圖206.2.1鄰接矩陣圖的鄰接矩陣（AdiacencyMatrix）存儲(chǔ)結(jié)構(gòu)又稱為數(shù)組表示法。其用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)的信息和頂點(diǎn)之間的關(guān)系（邊或?。┑男畔?。例如圖6.3無向圖G3和圖6.8有向圖G7的鄰接矩陣如圖6.10所示。用二維數(shù)組表示有n個(gè)頂點(diǎn)的圖時(shí)，需要存儲(chǔ)n個(gè)頂點(diǎn)的信息以及n2個(gè)邊的信息。

無向圖G3的鄰接矩陣

有向圖G7的鄰接矩陣圖6.106.2.1鄰接矩陣圖的鄰接矩陣（AdiacencyMa216.2.1鄰接矩陣網(wǎng)的鄰接矩陣定義如下：

圖的數(shù)組表示法具有以下特點(diǎn)：因?yàn)闊o向圖的鄰接矩陣具有對(duì)稱性，所以可以采取我們之前講過的壓縮存儲(chǔ)的方式只存儲(chǔ)矩陣的上三角（或下三角）元素。無向圖（網(wǎng)）的鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)是第i個(gè)頂點(diǎn)的度TD(vi)。有向圖（網(wǎng)）的鄰接矩陣的第i行非零元素（或非∞元素）的個(gè)數(shù)是第i個(gè)頂點(diǎn)的出度OD(vi)。6.2.1鄰接矩陣網(wǎng)的鄰接矩陣定義如下：圖的數(shù)組表226.2.1鄰接矩陣4.有向圖（網(wǎng)）的鄰接矩陣的第i列非零元素（或非∞元素）的個(gè)數(shù)是第i個(gè)頂點(diǎn)的出入ID(vi).5.顯然我們可以通過鄰接矩陣很快的看出任意兩個(gè)頂點(diǎn)之間是否有關(guān)系；但是，如果我們想確定這個(gè)圖（或網(wǎng)）中有多少條邊（或弧），就必須遍歷整個(gè)二維數(shù)組，對(duì)非零元素（或非無窮元素）計(jì)數(shù)。時(shí)間復(fù)雜度是O(n2)并不是理想的時(shí)間開銷，這是鄰接矩陣存儲(chǔ)方式的局限。6.2.1鄰接矩陣4.有向圖（網(wǎng)）的鄰接矩陣的第i列236.2.1鄰接矩陣//圖的鄰接矩陣存儲(chǔ)表示#defineMaxVerNum10

//最大頂點(diǎn)數(shù)typedefenum{DG,DN,UDG,UDN}GraphType;//枚舉{有向圖，有向網(wǎng)，無向圖，無向網(wǎng)}typedefstruct{ VerTypevexs[MaxVerNum];//頂點(diǎn)表 ArcTypearcs[MaxVerNum][MaxVerNum];//鄰接矩陣

int

vexnum,arcnum;//頂點(diǎn)數(shù)和邊數(shù) GraphTypetype;

//圖的類型標(biāo)識(shí)}MGraph;6.2.1鄰接矩陣//圖的鄰接矩陣存儲(chǔ)表示24voidCreateDN(MGraph&G)//算法6.1用數(shù)組表示法構(gòu)造有向網(wǎng)G{

scanf(&G.vexnum,&G.arcnum);

for(i=0;i<G.vexnum;i++) scanf(&G.vexs[i]);//構(gòu)造頂點(diǎn)表

for(i=0;i<G.vexnum;i++) {

for(j=0;j<G.vexnum;j++) G.arcs[i][j]={-1};//初始化鄰接矩陣權(quán)值均為-1，用-1表示鄰接矩陣中的∞元素 } for(k=0;k<G.vexnum;k++) { Scanf{&v1,&v2,&w};//接受用戶輸入與邊相連的兩個(gè)頂點(diǎn)及邊的權(quán)值 n=LocateVex(G,v1);//確定v1在圖中的位置 m=LocateVex(G,v2); G.arcs[n][m]=w; }}//endofCreateDNvoidCreateDN(MGraph&G)//算法6256.2.1鄰接矩陣顯然，算法6.1的時(shí)間復(fù)雜度只與途中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無關(guān)。因此鄰接矩陣存儲(chǔ)方式比較適合存儲(chǔ)稠密圖。數(shù)組表示法的空間復(fù)雜度是O(n+n2)，其中n表示頂點(diǎn)所占的空間，n2表示鄰接矩陣所占的空間。6.2.1鄰接矩陣顯然，算法6.1的時(shí)間復(fù)雜度只與途中頂266.2.2鄰接表鄰接表（AdiacencyList）也是圖的存儲(chǔ)方式，它是將順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)相結(jié)合而形成的一種存儲(chǔ)方法。鄰接表為圖的每一個(gè)頂點(diǎn)建立一個(gè)單鏈表，將圖中的每個(gè)頂點(diǎn)vi的所有臨結(jié)點(diǎn)都放在以vi為表頭的鏈表里，再將所有定點(diǎn)的鄰接表表頭放到一個(gè)一維數(shù)組里，顯然一維數(shù)組是順序存儲(chǔ)結(jié)構(gòu)，由一維數(shù)組和多個(gè)單鏈表構(gòu)成圖的鄰接表結(jié)構(gòu)。鄰接表包括頂點(diǎn)表和邊表，對(duì)應(yīng)的結(jié)點(diǎn)結(jié)構(gòu)如下圖6.11所示。

頭結(jié)點(diǎn)

表結(jié)點(diǎn)圖6.116.2.2鄰接表鄰接表（AdiacencyList）也276.2.2鄰接表

6.2.2鄰接表

28//圖的鄰接表存儲(chǔ)表示#defineMaxVerNum10//最大頂點(diǎn)數(shù)typedefenum{DG,DN,UDG,UDN}GraphType;//枚舉{有向圖，有向網(wǎng)，無向圖，無向網(wǎng)}typedefstructArcNode{intadjvex; //鄰接頂點(diǎn)的位置ArcNode*nextarc; //標(biāo)記下一個(gè)vi的鄰接結(jié)點(diǎn)的指針chardata; //標(biāo)記和邊（或?。┑南嚓P(guān)信息}ArcNode;typedefstructVexNode{VexInfovex; //頂點(diǎn)的信息ArcNode*firstarc; //標(biāo)記第一個(gè)vi的鄰接結(jié)點(diǎn)的指針}VexNodeVexList[MaxVerNum];typedefstructALGraph{VexListvexs;intvexnum,arcnum; //頂點(diǎn)數(shù)和邊數(shù)GraphTypetype; //圖的類型標(biāo)識(shí)}ALGraph;//圖的鄰接表存儲(chǔ)表示296.2.2鄰接表圖的鄰接表表示法具有以下特點(diǎn)：在無向圖的鄰接表中，第i個(gè)鏈表的結(jié)點(diǎn)數(shù)目等于頂點(diǎn)vi的度。在有向圖的鄰接表中，第i個(gè)鏈表的結(jié)點(diǎn)數(shù)目是頂點(diǎn)vi的出度。在鄰接表中可以快速找到某一頂點(diǎn)的鄰接點(diǎn)，但是要確定任意兩個(gè)頂點(diǎn)（vi和vj）之間是否有邊（或?。?，就必須搜索第i個(gè)或者第j個(gè)鏈表，在這個(gè)方面遠(yuǎn)不及鄰接矩陣方便快捷。

有向圖的鄰接表不方便查找以vi為弧頭的結(jié)點(diǎn)數(shù)，為此我們可以建立一個(gè)逆鄰接表，為每一個(gè)頂點(diǎn)建立一個(gè)以vi為弧頭的表。例如圖6.12c所示如果在建立鄰接表時(shí)，僅以頂點(diǎn)編號(hào)作為頂點(diǎn)信息輸入，則其時(shí)間復(fù)雜度為O(n+e)。6.2.2鄰接表圖的鄰接表表示法具有以下特點(diǎn)：30(a)無向圖G1的鄰接表(b)有向圖G2的鄰接表(c)有向圖G2的逆鄰接表圖6.12鄰接表和逆鄰接表6.2.2鄰接表(a)無向圖G1的鄰接表(b)有向圖G2的鄰接表(c)有316.2.3十字鏈表十字鏈表（OrthogonalList）是針對(duì)有向圖的另一種鏈?zhǔn)酱鎯?chǔ)方式。它綜合了鄰接表和逆鄰接表。在十字鏈表中，有向圖的每一個(gè)頂點(diǎn)有一個(gè)結(jié)點(diǎn)，每一條弧也有一個(gè)結(jié)點(diǎn)。結(jié)點(diǎn)結(jié)構(gòu)如圖6.13所示。頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)圖6.13十字鏈表頂點(diǎn)結(jié)點(diǎn)和弧結(jié)點(diǎn)頂點(diǎn)域指針域指針域弧尾結(jié)點(diǎn)弧頭結(jié)點(diǎn)弧信息指針域指針域6.2.3十字鏈表十字鏈表（OrthogonalLis326.2.3十字鏈表頂點(diǎn)結(jié)點(diǎn)中，vex是頂點(diǎn)vi的數(shù)據(jù)域，用來存儲(chǔ)頂點(diǎn)的信息；firstin指向第一個(gè)以vi為弧頭的弧結(jié)點(diǎn)，firstout指向第一個(gè)以vi為弧尾的弧結(jié)點(diǎn)。弧結(jié)點(diǎn)中，tailvex表示弧尾結(jié)點(diǎn)在圖中的存儲(chǔ)位置；headvex表示弧頭結(jié)點(diǎn)在圖中的存儲(chǔ)位置；hlink指向弧頭相同的下一個(gè)弧結(jié)點(diǎn)；tlink指向弧尾相同的下一個(gè)弧結(jié)點(diǎn)。data記錄這條弧的信息，例如權(quán)值等。6.2.3十字鏈表頂點(diǎn)結(jié)點(diǎn)中，vex是頂點(diǎn)vi的數(shù)據(jù)域，33//圖的十字鏈表存儲(chǔ)表示#defineMaxVerNum10//最大頂點(diǎn)數(shù)typedefstructArcNode{int

tailvex,headvex;

ArcNode*hlink,*tlink; chardata;

//標(biāo)記和邊（或弧）的相關(guān)信息}ArcNode;typedefstructVexNode{VexInfovex; //頂點(diǎn)的信息ArcNode*firstin,*firstout; //標(biāo)記第一個(gè)vi的鄰接結(jié)點(diǎn)的指針}VexNodeVexList[MaxVerNum];typedefstructOLGraph{VexListvexs;intvexnum,arcnum;

//頂點(diǎn)數(shù)和邊數(shù)}OLGraph;//圖的十字鏈表存儲(chǔ)表示34//下面算法6.2是建立有向圖的十字鏈表。voidCreateOLGraph(OLGraph&G){

scanf(&G.vexnum,&G.arcnum);//接受用戶輸入頂點(diǎn)數(shù)和弧數(shù)

for(i=0;i<G.vexnum;i++)

{

scanf(&G.vexs[i].vex);//接受用戶輸入頂點(diǎn)信息 G.vexs[i].firstin=NULL;

//初始化指針 G.vexs[i].firstout=NULL;}

for(j=0;j<G.arcnum;j++)

{

scanf(&v1,&v2);//接受用戶輸入弧頭和弧尾 n=LocateVex(G,v1); //確定v1在圖中的位置 m=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode));//為弧結(jié)點(diǎn)分配空間 *p={n,m,G.vexs[m].firstin,G.vexs[n].firstout};//初始化弧結(jié)點(diǎn) G.vexs[m].firstin=p;//將p連入十字鏈表中 G.vexs[n].firstout=p;

}}//endofCreateOLGraph//下面算法6.2是建立有向圖的十字鏈表。356.2.3十字鏈表通過算法6.2可以看出，我們只需要輸入n個(gè)頂點(diǎn)和e條弧的信息就可以建立十字鏈表。十字鏈表中，我們可以輕易找到以vi為弧頭或弧尾的弧，因此很容易算出頂點(diǎn)vi的出度和入度。建立十字鏈表的時(shí)間復(fù)雜度是O(n+e)，和建立鄰接表的時(shí)間復(fù)雜度相同。6.2.3十字鏈表通過算法6.2可以看出，我們只需要輸入366.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)方式6.3圖的遍歷 6.4圖與最小生成樹 6.5AOV網(wǎng)與拓?fù)渑判?6.6AOE網(wǎng)與關(guān)鍵路徑 6.7最短路徑 6.8本章實(shí)戰(zhàn)練習(xí) 6.9小結(jié) 第六章6.1圖的定義和基本術(shù)語第六章376.3圖的遍歷圖的遍歷與樹的遍歷類似，從圖中的任意頂點(diǎn)出發(fā)，訪問其余定點(diǎn)，并且保證所有頂點(diǎn)只被訪問一次，這一過程被稱為圖的遍歷（TraversingGraph）。判斷圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵路徑都以圖的遍歷為基礎(chǔ)。圖的遍歷操作復(fù)雜，在遍歷過程中應(yīng)該注意以下問題。1.如何選取起始結(jié)點(diǎn)。在無向圖中，我們可以任意選取起始結(jié)點(diǎn)。在有向圖中,我們應(yīng)當(dāng)盡量選取入度為0的結(jié)點(diǎn)為起始結(jié)點(diǎn)，這可以使我們的遍歷更加清晰。6.3圖的遍歷圖的遍歷與樹的遍歷類似，從圖中的任意頂點(diǎn)出386.3圖的遍歷2.當(dāng)遍歷的圖是非連通圖時(shí)，那么從一個(gè)結(jié)點(diǎn)出發(fā)只能訪問它所在的連通分量上的所有結(jié)點(diǎn)，并不能訪問圖的所有結(jié)點(diǎn)。因此，遍歷還需要考慮不同連通分量的起始結(jié)點(diǎn)的選取問題。3.圖中一個(gè)結(jié)點(diǎn)可能和多個(gè)結(jié)點(diǎn)相鄰接，我們?nèi)绾芜x取下一個(gè)鄰接點(diǎn)。4.無向圖和有向圖中都有可能存在回路，那么在一個(gè)結(jié)點(diǎn)被訪問之后有可能因?yàn)榛芈返拇嬖诙俅伪辉L問，我們?nèi)绾伪苊庖粋€(gè)結(jié)點(diǎn)被多次訪問。一般我們采用深度優(yōu)先搜索遍歷（DepthFirstSearch，DFS）和廣度優(yōu)先遍歷（BreadthFirstSearch，BFS）兩種方式進(jìn)行圖的遍歷。6.3圖的遍歷2.當(dāng)遍歷的圖是非連通圖時(shí)，那么從一個(gè)結(jié)點(diǎn)396.3.1深度優(yōu)先遍歷算法深度優(yōu)先搜索遍歷類似于樹的先根遍歷，是樹的先根遍歷的拓展。假設(shè)初始狀態(tài)是圖中所有定點(diǎn)都未被訪問過，那么深度優(yōu)先搜索可以從圖中某個(gè)結(jié)點(diǎn)v出發(fā)，首先訪問此結(jié)點(diǎn)，然后從v的未曾訪問的鄰接點(diǎn)中選擇一個(gè)v/進(jìn)行訪問，然后再?gòu)膙/的鄰接點(diǎn)中選擇一個(gè)進(jìn)行訪問，依此類推，直到圖中所有和v有路徑相通的結(jié)點(diǎn)都被訪問過為止；如果此時(shí)圖中還有結(jié)點(diǎn)沒有被訪問，那么選擇一個(gè)未被訪問的結(jié)點(diǎn)作為新起始結(jié)點(diǎn)，重復(fù)上述操作，直到圖中所有結(jié)點(diǎn)都被訪問完。深度優(yōu)先遍歷是通過探索圖的最大深度的方式來訪問所有結(jié)點(diǎn)。6.3.1深度優(yōu)先遍歷算法深度優(yōu)先搜索遍歷類似于樹的先根40下面以圖6.14的無向圖G8為例，進(jìn)行圖的深度優(yōu)先遍歷。圖6.14無向圖G86.3.1深度優(yōu)先遍歷算法下面以圖6.14的無向圖G8為例，進(jìn)行圖的深度優(yōu)先遍歷。圖6416.3.1深度優(yōu)先遍歷算法假設(shè)從頂點(diǎn)v1為起始結(jié)點(diǎn)，在訪問v1之后，選擇鄰接結(jié)點(diǎn)v2。因?yàn)関2未被訪問過，所以可以從v2出發(fā)進(jìn)行搜索。在訪問v2之后，選擇鄰接結(jié)點(diǎn)v5。因?yàn)関5未被訪問過，所以可以從v5出發(fā)進(jìn)行搜索。依次類推，從v4和v8出發(fā)進(jìn)行搜索。在訪問了v8之后，由于v8的鄰接點(diǎn)都被訪問過，因此搜索退回到v4，因?yàn)橄嗤脑颍阉魍嘶氐絭5、v2，直到v1。此時(shí)由于v1的另一個(gè)鄰接點(diǎn)v3尚未被訪問，則搜索繼續(xù)從v3開始，重復(fù)上述遍歷過程。由此，得到的結(jié)點(diǎn)訪問序列如下：V1，V2，V5，V4，V8，V3，V7，V66.3.1深度優(yōu)先遍歷算法假設(shè)從頂點(diǎn)v1為起始結(jié)點(diǎn)，在訪426.3.1深度優(yōu)先遍歷算法顯然，圖的深度優(yōu)先遍歷是一個(gè)遞歸的過程。在遞歸過程中，我們就遇到了本節(jié)開頭提出的問題（4），我們可以通過輻射一個(gè)訪問標(biāo)記數(shù)組visited[0…n-1]，初始值均為false，一旦某個(gè)結(jié)點(diǎn)被訪問，立即對(duì)其相應(yīng)分量置true，由此可以區(qū)別圖中結(jié)點(diǎn)是否被訪問過，并最終遍歷所有結(jié)點(diǎn)也避免了結(jié)點(diǎn)重復(fù)訪問。下面算法6.3是從圖的某一結(jié)點(diǎn)出發(fā)，遞歸地進(jìn)行深度優(yōu)先搜索。6.3.1深度優(yōu)先遍歷算法顯然，圖的深度優(yōu)先遍歷是一個(gè)遞43voidDFS(GraphG,intv){for(inti=0;i<G.vexnum;i++)//初始化標(biāo)記數(shù)組{ visited[i]=false;} visited[v]=true; visit(v);//訪問結(jié)點(diǎn)v并置標(biāo)記數(shù)組中v的對(duì)應(yīng)位置為true x=FirstAdjvex(G,v);

while(x!=NULL) {

if(visited[x]==false) DFS(G,x);//對(duì)結(jié)點(diǎn)x遞歸調(diào)用DFS x=NextAdjvex(G,v,x); }}//endofDFSvoidDFS(GraphG,intv)44//下面算法6.4是深度優(yōu)先搜索以鄰接表存儲(chǔ)的非連通圖G。voidDFSTraversALGraph(ALGraph&G){for(inti=0;i<G.vexnum;i++){ visited[i]=false;//初始化標(biāo)識(shí)數(shù)組}for(intk=0;k<G.vexnum;k++){

if(visited[k]==false) DFSALGraph(G,k);}}//endofDFSTraversALGraph//下面算法6.4是深度優(yōu)先搜索以鄰接表存儲(chǔ)的非連通圖G。45//下面算法6.5是如何遍歷以鄰接表存儲(chǔ)的連通圖G。voidDFSALGraph(MGraph&G,intk){ ArcNode*p=NULL; visited[k]=true; p=G.vexs[k].firstarc;//取頭結(jié)點(diǎn)是k的邊表的頭指針

while(p) {

intq=p.adjvex;

if(visited[q]==false) {

DFSALGraph(G,q);//若結(jié)點(diǎn)q未被訪問，則以q為新的起始結(jié)點(diǎn)繼續(xù)深度優(yōu)先遍歷

} p=p.nextarc;//頂點(diǎn)k的下一個(gè)鄰接點(diǎn) }}//endofDFSALGraph//下面算法6.5是如何遍歷以鄰接表存儲(chǔ)的連通圖G。46//下面算法6.6是深度優(yōu)先搜索以鄰接矩陣存儲(chǔ)的連通圖G。voidDFSMGraph(MGraphG,intv)//從頂點(diǎn)V出發(fā)遍歷{ for(inti=0;i<G.vexnum;i++)//初始化標(biāo)記數(shù)組 { visited[i]=false; }visit(v);visited[v]=true;

for(intw=0;w<G.vexnum;w++)

if((G.arcs[v][w]==1)&&(visited[w]==false))DFSMGraph(w);}//endofDFSMGraph//下面算法6.6是深度優(yōu)先搜索以鄰接矩陣存儲(chǔ)的連通圖G。476.3.1深度優(yōu)先遍歷算法在深度優(yōu)先遍歷時(shí)，對(duì)圖中的每個(gè)頂點(diǎn)有且只有一次調(diào)用DFS函數(shù)，因?yàn)関isited[n-1]數(shù)組在不斷的被更新，某個(gè)頂點(diǎn)visited[i]一旦被標(biāo)記成true，則其將不再被訪問。因此深度優(yōu)先遍歷的過程可以看作是對(duì)圖中結(jié)點(diǎn)查找其鄰接點(diǎn)的過程。不同的存儲(chǔ)方式似的查找鄰接點(diǎn)的時(shí)間復(fù)雜度不盡相同。當(dāng)圖采用鄰接矩陣的存儲(chǔ)方式時(shí)，查找每個(gè)結(jié)點(diǎn)的鄰接點(diǎn)的時(shí)間復(fù)雜度為O(n2)。當(dāng)采用鄰接表的存儲(chǔ)方式時(shí)，先要找到每個(gè)頂點(diǎn)，其時(shí)間復(fù)雜度為O(n)，再找到每個(gè)頂點(diǎn)的鄰接點(diǎn)，其時(shí)間復(fù)雜度為O(e)。因此總的時(shí)間復(fù)雜度為O(n+e)。6.3.1深度優(yōu)先遍歷算法在深度優(yōu)先遍歷時(shí)，對(duì)圖中的每個(gè)486.3.2廣度優(yōu)先遍歷算法廣度優(yōu)先搜索（BreadthFirstSearch）遍歷類似于樹的層次遍歷過程。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G中任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是：首先訪問頂點(diǎn)vi，并將其訪問標(biāo)志置為已被訪問，即visited[i]=true；接著依次訪問與頂點(diǎn)vi有邊相連的所有頂點(diǎn)W1，W2，…，Wt；然后再按順序訪問與W1，W2，…，Wt有邊相連又未曾訪問過的頂點(diǎn)；依此類推，直到圖中所有頂點(diǎn)都被訪問完為止。需要注意的是先被訪問的頂點(diǎn)的鄰接點(diǎn)會(huì)排在后被訪問的頂點(diǎn)的鄰接點(diǎn)。6.3.2廣度優(yōu)先遍歷算法廣度優(yōu)先搜索（Breadth496.3.2廣度優(yōu)先遍歷算法無向圖G9的中，從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索遍歷序列舉三種為：v1,v2,v3,v4,v5,v6,v7,v8v1,v3,v2,v7,v6,v5,v4,v8v1,v2,v3,v5,v4,v7,v6,v8圖6.15

無向圖G96.3.2廣度優(yōu)先遍歷算法無向圖G9的中，從頂點(diǎn)v1出發(fā)506.3.2廣度優(yōu)先遍歷算法和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個(gè)訪問標(biāo)記數(shù)組。并且，為了順次訪問路徑長(zhǎng)度為2、3、…的頂點(diǎn)，需附設(shè)隊(duì)列以存儲(chǔ)已被訪問的路徑長(zhǎng)度為1，2，…的頂點(diǎn)。算法6.7是從圖的某一結(jié)點(diǎn)出發(fā)，非遞歸地進(jìn)行廣度優(yōu)先遍歷。6.3.2廣度優(yōu)先遍歷算法和深度優(yōu)先搜索類似，在遍歷的過51voidBFS(GraphG,intv）{

visit(v);

visited[v]=true;InitQueue(Q);

//初始化隊(duì)列EnQueue(Q,v);//起始頂點(diǎn)v入隊(duì)while(!Empty(Q)){

DelQueue(Q,u);//隊(duì)頭元素出隊(duì)并用v保存 w=FirstAdjvex(G,u);

//求v的鄰接點(diǎn)

while(w!=0)

{

if

(!visited[w])

{visit(w);visited[w]=true;EnQueue(Q,w);

}

w=NextAdjvex(G,u,w);//求下一鄰接點(diǎn) } } }//endofBFSvoidBFS(GraphG,intv）52算法6.8是廣度優(yōu)先遍歷用鄰接矩陣存儲(chǔ)的圖G。voidBFSMGraph(MGraphG,intv)//從頂點(diǎn)v出發(fā)遍歷{InitQueue(Q); //Q為隊(duì)列visit(v); //輸出訪問頂點(diǎn)visited[v]=true; //全局?jǐn)?shù)組標(biāo)記置v已訪問EnQueue(v); //入隊(duì)列

while

(!Empty(Q))

{ DelQueue(Q,u);//隊(duì)頭元素出隊(duì)并用u保存

for

(w=0;w<G.vexnum;w++)

if

((A[u][w]==1)&&(visited[w]==false))

{ visit(w); visited[w]=true; EnQueue(w); }

}}//endofBFSMGraph算法6.8是廣度優(yōu)先遍歷用鄰接矩陣存儲(chǔ)的圖G。53算法6.9是廣度優(yōu)先遍歷用鄰接表存儲(chǔ)的圖G。voidBFSALGraph(ALGraphG,intv){InitQueue(Q); //Q為隊(duì)列visit(v); //輸出訪問頂點(diǎn)visited[v]=true; //全局?jǐn)?shù)組標(biāo)記置v已訪問EnQueue(v); //入隊(duì)列while

(!Empty(Q))

{DelQueue(Q,u);p=G.vexs[u].firstarc;//取頭結(jié)點(diǎn)是u的邊表的頭指針

while(p)

{

int

q=p.adjvex;

if(visited[q]==false)

{ visit(q); EnQueue(q);//入隊(duì)列

}

p=p.nextarc;//頂點(diǎn)k的下一個(gè)鄰接點(diǎn),結(jié)點(diǎn)繼續(xù)深度優(yōu)先遍歷

}

}}//endofBFSALGraph算法6.9是廣度優(yōu)先遍歷用鄰接表存儲(chǔ)的圖G。546.3.2廣度優(yōu)先遍歷算法通過對(duì)算法6.3~6.9的比較和分析可以看出,圖中每個(gè)頂點(diǎn)最多進(jìn)隊(duì)一次。圖的遍歷的過程實(shí)際上是通過邊或弧找鄰接頂點(diǎn)的過程。因此圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的時(shí)間復(fù)雜度相同，唯一的不同點(diǎn)是對(duì)頂點(diǎn)的訪問順序有差別。6.3.2廣度優(yōu)先遍歷算法通過對(duì)算法6.3~6.9的比較556.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)方式6.3圖的遍歷

6.4圖與最小生成樹

6.5AOV網(wǎng)與拓?fù)渑判?6.6AOE網(wǎng)與關(guān)鍵路徑 6.7最短路徑 6.8本章實(shí)戰(zhàn)練習(xí) 6.9小結(jié) 第六章6.1圖的定義和基本術(shù)語第六章566.4圖與最小生成樹若圖是連通的或強(qiáng)連通的，則從圖中某一個(gè)頂點(diǎn)出發(fā)可以訪問到圖中所有頂點(diǎn)；若圖是非連通的或非強(qiáng)連通圖，則需從圖中多個(gè)頂點(diǎn)出發(fā)搜索訪問，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為每個(gè)連通分量中的頂點(diǎn)集。6.4.1生成樹和森林的算法6.4圖與最小生成樹若圖是連通的或強(qiáng)連通的，則從圖中某一57深度優(yōu)先搜索遍歷算法及廣度優(yōu)先搜索遍歷算法中遍歷圖過程中歷經(jīng)邊的集合和頂點(diǎn)集合一起構(gòu)成連通圖的極小連通子圖。它是連通圖的一顆生成樹。它含有圖中全部頂點(diǎn)，但只有n-1條邊。由深度優(yōu)先搜索遍歷得到的生成樹，稱為深度優(yōu)先生成樹，由廣度優(yōu)先搜索遍歷得到的生成樹，稱為廣度優(yōu)先生成樹。如圖6.16是無向圖G9的兩種生成樹示意圖。

無向圖G9

深度優(yōu)先生成樹

廣度優(yōu)先生成樹圖6.16無向圖及其生成樹6.4.1生成樹和森林的算法深度優(yōu)先搜索遍歷算法及廣度優(yōu)先搜索遍歷算法中遍歷圖過程中歷經(jīng)58下面算法6.10是通過深度優(yōu)先遍歷圖G，建立以T為根的生成樹。voidDFSCreateTree(GraphG,intv,Tree&T){visited[v]=true;

int

firstchild=0;for(int

w=FirstAdjvex(G,v);w<=G.vexnum;w=NextAdjvex(G,v,w);){if(visited[w]==false)

{ p=(Tree*)malloc(sizeof(TNode));//為孩子結(jié)點(diǎn)p分配空間*p={GetVex(G,w),NULL,NULL};

if(firstchild==0)

{

T.lchild=p;

firstchild=1;

}

else

q->nextBrother=p;

q=p;

DFSCreateTree(G,w,q);

}

}}//endofDFSCreateTree下面算法6.10是通過深度優(yōu)先遍歷圖G，建立以T為根的生成樹59若一個(gè)圖是非連通圖或非強(qiáng)連通圖，但有若干個(gè)連通分量或若干個(gè)強(qiáng)連通分量，則通過深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，不能得到生成樹，但可以得到生成森林，且若非連通圖有n個(gè)頂點(diǎn)，m個(gè)連通分量或強(qiáng)連通分量，則可以遍歷得到m棵生成樹，合起來為生成森林，森林中包含n-m條樹邊。生成森林可以利用非連通圖的深度優(yōu)先搜索遍歷或非連通圖的廣度優(yōu)先搜索遍歷算法得到。

非連通圖G10

G10的生成森林6.4.1生成樹和森林的算法若一個(gè)圖是非連通圖或非強(qiáng)連通圖，但有若干個(gè)連通分量或若干個(gè)強(qiáng)60下面算法6.11是通過深度優(yōu)先遍歷非連通圖G，建立以T為根的生成森林。void

DFSCreateForest(GraphG,Tree&T){ T=NULL;//初始化T為空樹

for(inti=0;i<G.vexnum;i++)//初始化標(biāo)記數(shù)組 visited[i]=false; for(inti=0;i<G.vexnum;i++)//初始化標(biāo)記數(shù)組 {

if(visited[i]=false)

{

p=(Tree*)malloc(sizeof(TNode));//為孩子結(jié)點(diǎn)p分配空間

*p={GetVex(G,w),NULL,NULL};//為結(jié)點(diǎn)p賦值：結(jié)點(diǎn)信息，左右孩子為空

if(T==NULL) T=p;

else q->nextBrother=p;

q=p;

DFSCreateTree(G,v,p); } }}下面算法6.11是通過深度優(yōu)先遍歷非連通圖G，建立以T為根的61以上內(nèi)容介紹的是如何得到無向圖的生成樹和生成森林及其算法，下面我們以采用十字鏈表存儲(chǔ)方式的圖為例，介紹如何求強(qiáng)連通分量的頂點(diǎn)集。具體步驟如下：1.在有向圖G中，首先從頂點(diǎn)v出發(fā)沿以v為弧尾的弧進(jìn)行深度優(yōu)先遍歷，并按訪問順序?qū)㈨旤c(diǎn)依次編號(hào)排列起來。2.從序列的編號(hào)最大的頂點(diǎn)w出發(fā)，沿以w為弧頭的弧進(jìn)行逆向深度優(yōu)先遍歷，如果一次遍歷到圖中所有頂點(diǎn)，則圖G是強(qiáng)連通圖；如果不能訪問到所有頂點(diǎn)，則從剩余定點(diǎn)中編號(hào)最大的定點(diǎn)出發(fā)，繼續(xù)做逆向深度優(yōu)先遍歷，直至圖中所有頂點(diǎn)均被訪問。此時(shí)得到圖G的所有強(qiáng)連通分量。每次逆向深度優(yōu)先遍歷得到的頂點(diǎn)集是圖G的一個(gè)強(qiáng)連通分量的頂點(diǎn)集。6.4.1生成樹和森林的算法以上內(nèi)容介紹的是如何得到無向圖的生成樹和生成森林及其算法，下626.4.2最小生成樹當(dāng)我們對(duì)圖G用不同的遍歷方法時(shí)，可以得到不同的生成樹，并且用相同的遍歷方法但從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹有n個(gè)頂點(diǎn)、n-1條邊。若無向連通圖是一個(gè)帶權(quán)圖，則它必有一棵生成樹的所有邊的權(quán)值之和最小，這樣的生成樹稱為該圖的最小生成樹(MSTMinimumcostSpanningTree)。構(gòu)造最小生成樹的準(zhǔn)則：1.必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；2.必須使用且僅使用n-1條邊來連接網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；3.不能使用產(chǎn)生回路的邊。6.4.2最小生成樹當(dāng)我們對(duì)圖G用不同的遍歷方法時(shí)，可以636.4.2最小生成樹當(dāng)帶權(quán)圖中有邊具有相同的權(quán)值時(shí)，由于選擇的隨意性，產(chǎn)生的最小生成樹可能不唯一。但是當(dāng)各邊的權(quán)值不相同時(shí)，產(chǎn)生的最小生成樹必然唯一?，F(xiàn)實(shí)生活中，我們經(jīng)常遇到需要用最小生成樹來解決的問題。比如，我們?cè)谌舾沙鞘兄g鋪設(shè)公路，鋪設(shè)道路有對(duì)應(yīng)的經(jīng)濟(jì)成本，我們?nèi)绾伪ＷC城市連通的同時(shí)把總成本降到最低。鋪設(shè)公路的造價(jià)一般依據(jù)城市間的距離設(shè)定，我們?cè)诳疾炝藢?shí)際地形之后進(jìn)行距離的測(cè)量，至此可以用一個(gè)帶權(quán)無向圖G來表示城市和公路直接的關(guān)系。頂點(diǎn)表示城市，邊表示城市間的公路。我們想使總成本降到最低等價(jià)于尋找圖G的最小生成樹。6.4.2最小生成樹當(dāng)帶權(quán)圖中有邊具有相同的權(quán)值時(shí)，由于646.4.2最小生成樹如何構(gòu)造最小生成樹，典型代表算法是普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法，下面分別予以介紹。1.普里姆（Prim）算法生成最小生成樹普里姆算法的基本思想:設(shè)G=（V，E）是帶權(quán)圖，V是圖G的頂點(diǎn)集，E是邊集。（1）在圖中任取一個(gè)頂點(diǎn)K作為開始點(diǎn)，令U={k}，W=V-U，其中W為圖中剩余頂點(diǎn)集。（2）找一個(gè)頂點(diǎn)在U中，另一個(gè)頂點(diǎn)在W中的邊中最短的一條。找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點(diǎn)加入U(xiǎn)集合中，并從W中刪去這些頂點(diǎn)。（3）重復(fù)（2），直到W為空集止。6.4.2最小生成樹如何構(gòu)造最小生成樹，典型代表算法是普656.4.2最小生成樹普里姆算法是從最小生成樹中頂點(diǎn)的角度出發(fā)來考慮的，因?yàn)閳D中有n個(gè)頂點(diǎn)，按照生成樹的定義，所有的頂點(diǎn)都必須加入到最小生成樹中，所以除去最初選定的頂點(diǎn)剩余的n-1個(gè)頂點(diǎn)在加入到最小生成樹的過程中可以選擇n-1條邊加入到最小生成樹的邊集中，至此，我們就得到了圖G的最小生成樹。圖6.18展示了運(yùn)用普里姆算法構(gòu)造最小生成樹的過程。6.4.2最小生成樹普里姆算法是從最小生成樹中頂點(diǎn)的角度66

(a)

(b)

(c)

(d)(e)

(f)(g)6.4.2最小生成樹(a)(676.4.2最小生成樹記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊需要設(shè)置一個(gè)輔助數(shù)組MinEdge，定義如下：struct{VerTypevex;//U中的頂點(diǎn)ArcTypelowcost;//邊的權(quán)值}MinEdge[MaxVerNum];6.4.2最小生成樹記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊68下面算法6.12是用Prim算法從頂點(diǎn)V出發(fā)構(gòu)造圖G的最小生成樹。（注：圖G采用鄰接矩陣的存儲(chǔ)方式。）voidPrimCreateMinTree(GraphG,intv){for(k=0;k<G.vexnum;k++)

if(k!=v)

MinEdge[k]={v,G.arcs[k][v]}; MinEdge[v].lowcost=0; for(i=0;i<G.vexnum;i++) {

m=minCost(MinEdge[i]);//cost賦值被加入到生成樹中的下一個(gè)頂點(diǎn)其中，minCost方法是選取邊集中權(quán)值最小的并且確定其頂點(diǎn)

printf(MinEdge[m].adjvex,G.vexs[m]);//輸出打印生成樹的一條邊

MinEdge[m].lowcost=0;//將頂點(diǎn)m加入到U中

for(j=0;j<G.vexnum;j++)

if(G.arcs[m][j]j<MinEdge[j].lowcost)//新頂點(diǎn)并入U(xiǎn)中重新選擇權(quán)值最小邊 MinEdge[j]={G.vexs[m],G.arcs[m][j]} }}//endofPrimCreateMinTree下面算法6.12是用Prim算法從頂點(diǎn)V出發(fā)構(gòu)造圖G的最小生696.4.2最小生成樹普里姆算法中，我們用到了嵌套for循環(huán)，其中外層for循環(huán)用于尋找當(dāng)前權(quán)值最小的邊的頂點(diǎn)，內(nèi)層for循環(huán)是修改頂點(diǎn)的最小邊。我們可以看出普里姆算法的時(shí)間復(fù)雜度為O(n2)。顯然其時(shí)間復(fù)雜度只與圖的頂點(diǎn)數(shù)目有關(guān)，與邊數(shù)無關(guān)。因此，普里姆算法適用于求邊比較多的稠密圖的最小生成樹。表6.1給出了在用算法6.12構(gòu)造圖6.18的圖G11的最小生成樹的過程中，數(shù)組MinEdge的vex和lowcost、集合U和W的變化情況。6.4.2最小生成樹普里姆算法中，我們用到了嵌套for循70vi

MinEdgev2v3v4v5v6v7UV-Uminlengthvexlowcostv118000v12v14{v1}{v2，v3，v4，v5，v6，v7}2vexlowcostv11800v690v14{v1，v6}{v2，v3，v4，v5，v7}4vexlowcostv71300v6900{v1，v6，v7}{v2，v3，v4，v5}9vexlowcostv7130v51000{v1，v5，v6，v7}{v2，v3，v4}1vexlowcostv713v450000{v1,v4，v5，v6，v7}{v2

，v3}5vexlowcostv71300000{v1，v3，v4，v5，v6，v7}{v2}13vexlowcost000000{v1，v2，v3，v4，v5，v6，v7}{}\viv2v3v4v5v6v7UV-Umin716.4.2最小生成樹2.克魯斯卡爾（Kruskal）算法生成最小生成樹普里姆算法的時(shí)間復(fù)雜度是O（n2），只與網(wǎng)的頂點(diǎn)數(shù)有關(guān)。而克魯斯卡爾算法的時(shí)間復(fù)雜度是O（eloge），其中e為網(wǎng)的邊數(shù)。因此，相比較而言，普里姆算法適用于稠密圖，克魯斯卡爾算法適用于稀疏圖。從時(shí)間復(fù)雜度可以看出，克魯斯卡爾算法是從邊的角度求網(wǎng)的最小生成樹。克魯斯卡爾算法的基本思想:(1)將圖中所有邊按權(quán)值遞增順序排列；(2)依次選取權(quán)值較小的邊，但要求后面選取的邊不能與前面選取的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，再去選后面權(quán)值較大的邊；n個(gè)頂點(diǎn)的圖中，選夠n-1條邊即可。6.4.2最小生成樹2.克魯斯卡爾（Kruskal）算法726.4.2最小生成樹下圖6.19是圖6.18(a)帶權(quán)無向圖的克魯斯卡爾算法構(gòu)造最小生成樹的過程。

(a)(b)

(c)

(d)

(e)(f)6.4.2最小生成樹下圖6.19是圖6.18(a)帶權(quán)736.4.2最小生成樹為了實(shí)現(xiàn)克魯斯卡爾算法，我們?cè)O(shè)置一個(gè)結(jié)構(gòu)數(shù)組來存儲(chǔ)圖中所有的邊，具體定義如下：#defineMaxArcNum20//定義圖的最大邊數(shù)#defineMaxVerNum10//定義圖的最大頂點(diǎn)數(shù)typedefstruct{ VerTypevexhead;//定義一條邊的一個(gè)頂點(diǎn) VerTypevexTail;//定義一條邊的另一個(gè)頂點(diǎn) intweight;//該邊的權(quán)值}ArcType,totalArc[MaxArcNum];6.4.2最小生成樹為了實(shí)現(xiàn)克魯斯卡爾算法，我們?cè)O(shè)置一個(gè)746.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)方式6.3圖的遍歷

6.4圖與最小生成樹 6.5AOV網(wǎng)與拓?fù)渑判?/p>

6.6AOE網(wǎng)與關(guān)鍵路徑 6.7最短路徑 6.8本章實(shí)戰(zhàn)練習(xí) 6.9小結(jié) 第六章6.1圖的定義和基本術(shù)語第六章756.4.2最小生成樹數(shù)組totalArc中，每個(gè)分量totalArc[i]表示圖中的一條邊，它包含的信息有這條邊依附的兩個(gè)頂點(diǎn)以及該邊的權(quán)值?？唆斔箍査惴看味家业綑?quán)值最小的邊，因此我們可以按照權(quán)值大小先對(duì)數(shù)組totalArc進(jìn)行排序。為了避免最小生成樹中出現(xiàn)環(huán)，我們選取的符合條件的邊應(yīng)當(dāng)在不同的連通分量中。關(guān)于普里姆算法和克魯斯卡爾算法，我們應(yīng)當(dāng)重點(diǎn)掌握其最小生成樹的生成過程，會(huì)繪制過程圖，理解兩種算法求最小生成樹的思考角度，知道其時(shí)間復(fù)雜度。6.4.2最小生成樹數(shù)組totalArc中，每個(gè)分量to766.5AOV網(wǎng)與拓?fù)渑判蛞粋€(gè)無環(huán)的有向圖稱為有向無環(huán)圖（DirectedAcyclineGraph），簡(jiǎn)記DAG圖。DAG圖可作為描述任務(wù)的進(jìn)行過程的有效工具?，F(xiàn)實(shí)生活中，我們遇到的很多工程都可以分解為若干個(gè)活動(dòng)，這些活動(dòng)通常受一定條件的制約，比如有些活動(dòng)必須以另一些活動(dòng)的完成為前提條件。6.5AOV網(wǎng)與拓?fù)渑判蛞粋€(gè)無環(huán)的有向圖稱為有向無環(huán)圖（77在一個(gè)有向圖中，若用頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)間先后關(guān)系，稱該有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(ActivityOnVertexnetwork)簡(jiǎn)稱為AOV網(wǎng)。在AOV網(wǎng)中，若從頂點(diǎn)i到頂點(diǎn)j之間存在一條有向路徑，稱頂點(diǎn)i是頂點(diǎn)j的前驅(qū)，或者稱頂點(diǎn)j是頂點(diǎn)i的后繼。若<i,j>是圖中的邊，則稱頂點(diǎn)i是頂點(diǎn)j的直接前驅(qū)，頂點(diǎn)j是頂點(diǎn)i的直接后繼。現(xiàn)代化管理中,通常我們把計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都當(dāng)成一個(gè)工程，一個(gè)大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動(dòng)。在整個(gè)工程實(shí)施過程中，有些活動(dòng)開始是以它的所有前序活動(dòng)的結(jié)束為先決條件的，必須在其它有關(guān)活動(dòng)完成之后才能開始，有些活動(dòng)沒有先決條件，可以安排在任意時(shí)間開始。6.5.1AOV網(wǎng)在一個(gè)有向圖中，若用頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)間先后關(guān)系，786.5.1AOV網(wǎng)AOV網(wǎng)就是一種可以形象地反映出整個(gè)工程中各個(gè)活動(dòng)之間前后關(guān)系的有向圖。例如，計(jì)算機(jī)專業(yè)學(xué)生的課程開設(shè)可看成是一個(gè)工程，每一門課程就是工程中的活動(dòng)，表6.2給出了若干門所開設(shè)的課程，其中有些課程的開設(shè)有先后關(guān)系，有些則沒有先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開設(shè)。6.5.1AOV網(wǎng)AOV網(wǎng)就是一種可以形象地反映出整個(gè)工796.5.1AOV網(wǎng)課程課程名稱先修課程C1高等數(shù)學(xué)

無C2程序設(shè)計(jì)基礎(chǔ)無C3離散數(shù)學(xué)C1,C2C4數(shù)據(jù)結(jié)構(gòu)C2,C3C5高級(jí)語言程序設(shè)計(jì)C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普遍物理C1C9計(jì)算機(jī)原理C8表6.26.5.1AOV網(wǎng)課程課程名稱先修課程C1高等數(shù)學(xué)無806.5.1AOV網(wǎng)左圖6.20就是我們用AOV網(wǎng)來表示課程開設(shè)的先后關(guān)系。圖6.206.5.1AOV網(wǎng)左圖6.20就是我們用AOV網(wǎng)來表示課816.5.2拓?fù)渑判蚪o出有向圖G=(V,E)，對(duì)于V中的頂點(diǎn)的線性序列(v1,v-2,...,vk)，如果滿足如下條件：若在G中從頂點(diǎn)vi

到vj有一條路徑，則在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前；則稱該序列為G的一個(gè)拓?fù)湫蛄?。?gòu)造有向圖的一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。關(guān)于拓?fù)渑判蛭覀冃枰⒁庖韵聨c(diǎn)：1.在AOV網(wǎng)中,若不存在回路,則所有活動(dòng)可排成一個(gè)線性序列,使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面,那么該序列為拓?fù)湫蛄小?.拓?fù)湫蛄胁皇俏ㄒ坏摹?.對(duì)AOV網(wǎng)不一定都有拓?fù)湫蛄小?.5.2拓?fù)渑判蚪o出有向圖G=(V,E)，對(duì)于V中的頂826.5.2拓?fù)渑判驈那膀?qū)和后繼的傳遞性和反自反性來看，AOV網(wǎng)中不能出現(xiàn)有向回路(或稱有向環(huán))。在AOV網(wǎng)中如果出現(xiàn)了有向環(huán)，則意味著某項(xiàng)活動(dòng)應(yīng)以自己作為先決條件，這是不對(duì)的，工程將無法進(jìn)行。對(duì)程序流程而言，將出現(xiàn)死循環(huán)。因此，對(duì)給定的AOV網(wǎng)，應(yīng)先判斷它是否存在有向環(huán)。判斷AOV網(wǎng)是否有有向環(huán)的方法是對(duì)該AOV網(wǎng)進(jìn)行拓?fù)渑判?，將AOV網(wǎng)中頂點(diǎn)排列成一個(gè)線性有序序列，若該線性序列中包含AOV網(wǎng)全部頂點(diǎn)，則AOV網(wǎng)無環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該網(wǎng)所代表的工程是不可行的。6.5.2拓?fù)渑判驈那膀?qū)和后繼的傳遞性和反自反性來看，A836.5.2拓?fù)渑判?.拓?fù)湫蛄械膶?shí)際意義是:如果按照拓?fù)湫蛄兄械捻旤c(diǎn)次序進(jìn)行每一項(xiàng)活動(dòng)，就能夠保證在開始每一項(xiàng)活動(dòng)時(shí)，他的所有前驅(qū)活動(dòng)均已完成，從而使整個(gè)工程順序執(zhí)行。對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判虻幕静襟E步驟如下：(1)在AOV網(wǎng)中選一個(gè)入度為0的頂點(diǎn)（沒有前驅(qū)）且輸出之；(2)從AOV網(wǎng)中刪除此頂點(diǎn)及該頂點(diǎn)發(fā)出來的所有有向邊；(3)重復(fù)（1）、（2）兩步，直到AOV網(wǎng)中所有頂點(diǎn)都被輸出或網(wǎng)中不存在入度為0的頂點(diǎn)。6.5.2拓?fù)渑判?.拓?fù)湫蛄械膶?shí)際意義是:如果按照拓?fù)?4從拓?fù)渑判虿襟E可知，若在第3步中，網(wǎng)中所有頂點(diǎn)都被輸出，則表明網(wǎng)中無有向環(huán)，拓?fù)渑判虺晒?，若按照拓?fù)渑判虻捻樞蜷_展活動(dòng)則此工程能夠順利完成；若僅輸出部分頂點(diǎn)，網(wǎng)中已不存在入度為0的頂點(diǎn)，則表明網(wǎng)中有有向環(huán)，拓?fù)渑判虿怀晒?，則此工程不能順利完成。在此我們列舉兩種對(duì)圖6.20進(jìn)行拓?fù)渑判虻玫降耐負(fù)溆行蛐蛄校篊1，C8，C9，C2，C3，C4，C7，C5，C6或C1，C8，C9，C2，C5，C6，C3，C4，C7由此，我們證明了對(duì)AOV網(wǎng)進(jìn)行拓?fù)渑判虻玫降挠行蛐蛄胁晃ㄒ弧?.5.2拓?fù)渑判驈耐負(fù)渑判虿襟E可知，若在第3步中，網(wǎng)中所有頂點(diǎn)都被輸出，則表856.5.2拓?fù)渑判駻OV網(wǎng)一般采用鄰接表的存儲(chǔ)方式，為了標(biāo)記某個(gè)頂點(diǎn)是否有前驅(qū)結(jié)點(diǎn)，可以在鄰接表的頭結(jié)點(diǎn)中增加一個(gè)記錄頂點(diǎn)入度的數(shù)據(jù)域，頭結(jié)點(diǎn)的示意圖如下：

圖6.21頭結(jié)點(diǎn)結(jié)構(gòu)體定義為：typedefstructVexNode{

intinnum;

//頂點(diǎn)的入度值 VexInfovex; //頂點(diǎn)的信息 ArcNode*firstarc;//標(biāo)記第一個(gè)vi的鄰接結(jié)點(diǎn)的指針}VexNodeVexList[MaxVerNum];6.5.2拓?fù)渑判駻OV網(wǎng)一般采用鄰接表的存儲(chǔ)方式，為了86此外，我們還需要一個(gè)棧來保存拓?fù)渑判蜻^程中入度為0的頂點(diǎn)。拓?fù)渑判蛩惴ㄈ缦拢簐oidTopologicalOrder(ALGraphG){ InitStack(stack); intcount=0; for(i=0;i<G.vexnum;i++) if(VexList[i].innum==0) Push(stack,i); while(!EmptyStack(stack)) { Pop(stack,i); count++; for(p=G.vexs[i].firstarc;p!=NULL;p=p->nextarc) { k=p->adjvex; VexList[k].innum--; if(VexList[k].innum==0) Push(stack,k); } } if(count==G.vexnum) printf(“拓?fù)渑判蚴。W(wǎng)中存在回路?！?; else printf(“拓?fù)渑判虺晒ΓW(wǎng)中不存在回路?！?;}//endofTopologicalOrder算法6.13此外，我們還需要一個(gè)棧來保存拓?fù)渑判蜻^程中入度為0的頂點(diǎn)。算876.5.2拓?fù)渑判蛲ㄟ^對(duì)算法6.13的分析，可以看出，對(duì)有n個(gè)頂點(diǎn)和e條邊的有向圖來說，求各個(gè)頂點(diǎn)的入度的時(shí)間復(fù)雜度為O(e)，建立輔助棧的時(shí)間復(fù)雜度為O(n)。當(dāng)一個(gè)圖拓?fù)渑判虺晒r(shí)，所有頂點(diǎn)入度減一的操作進(jìn)行了e次，因此拓?fù)渑判虻臅r(shí)間復(fù)雜度為O(n+e)。有向無環(huán)圖可以采用深度優(yōu)先遍歷的方法進(jìn)行拓?fù)渑判颉膱D中某一頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時(shí)最先退出DFS函數(shù)的頂點(diǎn)即為出度為0的頂點(diǎn)，它是拓?fù)溆行蛐蛄兄凶詈笠粋€(gè)頂點(diǎn)。我們用一個(gè)臨時(shí)數(shù)組按照先后順序保存退出DFS函數(shù)的頂點(diǎn)，然后逆向輸入該數(shù)組得到的就是拓?fù)溆行蛐蛄?。拓?fù)渑判蚴乔蠼怅P(guān)鍵路徑的基礎(chǔ)，下一節(jié)我們將介紹AOE網(wǎng)與關(guān)鍵路徑。6.5.2拓?fù)渑判蛲ㄟ^對(duì)算法6.13的分析，可以看出，對(duì)886.1圖的定義和基本術(shù)語6.2圖的存儲(chǔ)方式6.3圖的遍歷

6.4圖與最小生成樹 6.5AOV網(wǎng)與拓?fù)渑判?6.6AOE網(wǎng)與關(guān)鍵路徑

6.7最短路徑 6.8本章實(shí)戰(zhàn)練習(xí) 6.9小結(jié) 第六章6.1圖的定義和基本術(shù)語第六章896.6.1AOE網(wǎng)若在帶權(quán)的有向圖中，以頂點(diǎn)表示事件，有向邊表示活動(dòng)，邊上的權(quán)值表示完成該活動(dòng)的開銷(如該活動(dòng)所需的時(shí)間)，則稱此帶權(quán)的有向圖為用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱AOE(ActivityOnEdge)網(wǎng)。AOV網(wǎng)與AOE網(wǎng)有密切關(guān)系又有不同。AOV網(wǎng)是針對(duì)無權(quán)有向圖，AOE網(wǎng)是帶權(quán)有向圖。如果用他們表示工程，AOV網(wǎng)表示各個(gè)子工程之間的優(yōu)先關(guān)系，是定性關(guān)系；在AOE網(wǎng)中還要體現(xiàn)完成各個(gè)子工程的確切時(shí)間，是定量關(guān)系。我們用從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑表示整個(gè)工程完成的時(shí)間。AOV網(wǎng)和AOE網(wǎng)都可采用鄰接表的存儲(chǔ)方式，只是AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)中在邊結(jié)點(diǎn)的數(shù)據(jù)域里存放的是權(quán)值，也就是某項(xiàng)活動(dòng)完成需要的時(shí)間。6.6.1AOE網(wǎng)若在帶權(quán)的有向圖中，以頂點(diǎn)表示事件，有906.6.1AOE網(wǎng)對(duì)于AOE網(wǎng)，我們關(guān)心的問題是：完成整個(gè)工程至少需要多少時(shí)間和哪些活動(dòng)是關(guān)鍵活動(dòng)：哪些活動(dòng)的進(jìn)度是影響整個(gè)工程進(jìn)度的關(guān)鍵。在AOE網(wǎng)中，只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊所代表的活動(dòng)