非線性數(shù)據(jù)結(jié)構(gòu)1本章導(dǎo)讀圖是又一種非線性數(shù)據(jù)結(jié)構(gòu)。在圖結(jié)構(gòu)中，數(shù)據(jù)元素之間的關(guān)系是多對多的，即如果任選一個(gè)頂點(diǎn)作為初始頂點(diǎn)，則圖中任意一個(gè)頂點(diǎn)有多個(gè)前驅(qū)頂點(diǎn)和多個(gè)后記頂點(diǎn)。本章主要討論圖的一些基本概念和基本操作，圖的存儲(chǔ)結(jié)構(gòu)及圖基本操作的算法實(shí)現(xiàn)，最后討論圖的最小生成樹問題和最短路徑問題。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第1頁。非線性數(shù)據(jù)結(jié)構(gòu)2第8章圖圖的基本概念和抽象數(shù)據(jù)類型圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣圖類圖的遍歷最小生成樹最短路徑主要知識(shí)點(diǎn)非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第2頁。非線性數(shù)據(jù)結(jié)構(gòu)38.1圖的基本概念和抽象數(shù)據(jù)類型1.圖的基本概念圖是由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。圖G的定義是：

G=（V，E）其中，V={x|x∈某個(gè)數(shù)據(jù)元素集合}E={(x，y)|x，y∈V}或E={＜x，y＞|x，y∈V并且Path(x，y)}其中，（x，y）表示從x到y(tǒng)的一條雙向通路，即（x，y）是無方向的；Path（x，y）表示從x到y(tǒng)的一條單向通路，即Path（x，y）是有方向的。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第3頁。非線性數(shù)據(jù)結(jié)構(gòu)4基本術(shù)語：（1）頂點(diǎn)和邊：圖中的結(jié)點(diǎn)稱作頂點(diǎn)，圖中的第i個(gè)頂點(diǎn)記做vi。兩個(gè)頂點(diǎn)vi和vj相關(guān)聯(lián)稱作頂點(diǎn)vi和vj之間有一條邊，圖中的第k條邊記做ek，ek=（vi,vj）或＜vi,vj＞。（2）有向圖和無向圖：在有向圖中，頂點(diǎn)對＜x,y＞是有序的，頂點(diǎn)對＜x,y＞稱為從頂點(diǎn)x到頂點(diǎn)y的一條有向邊，有向圖中的邊也稱作??；在無向圖中，頂點(diǎn)對（x,y）是無序的，頂點(diǎn)對（x,y）稱為與頂點(diǎn)x和頂點(diǎn)y相關(guān)聯(lián)的一條邊。（3）完全圖：在有n個(gè)頂點(diǎn)的無向圖中，若有n(n-1)/2條邊，即任意兩個(gè)頂點(diǎn)之間有且只有一條邊，則稱此圖為無向完全圖；在有n個(gè)頂點(diǎn)的有向圖中，若有n(n-1)條邊，即任意兩個(gè)頂點(diǎn)之間有且只有方向相反的兩條邊，則稱此圖為有向完全圖。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第4頁。非線性數(shù)據(jù)結(jié)構(gòu)521342145G23G1例如：下圖G1是有向圖，G2是無向圖非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第5頁。非線性數(shù)據(jù)結(jié)構(gòu)6（4）鄰接頂點(diǎn)：在無向圖G中，若（u,v）是E(G)中的一條邊，則稱u和v互為鄰接頂點(diǎn)，并稱邊（u,v）依附于頂點(diǎn)u和v；在有向圖G中，若＜u,v＞是E(G)中的一條邊，則稱頂點(diǎn)u鄰接到頂點(diǎn)v，頂點(diǎn)v鄰接自頂點(diǎn)u，并稱邊＜u,v＞和頂點(diǎn)u和頂點(diǎn)v相關(guān)聯(lián)。013201234560120123(a)無向完全圖(b)無向圖(c)有向圖(d)有向完全圖非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第6頁。非線性數(shù)據(jù)結(jié)構(gòu)7（5）頂點(diǎn)的度：頂點(diǎn)v的度是與它相關(guān)聯(lián)的邊的條數(shù)，記作TD(v)。（6）路徑：在圖G=(V,E)中，若從頂點(diǎn)vi出發(fā)有一組邊使可到達(dá)頂點(diǎn)vj，則稱頂點(diǎn)vi到頂點(diǎn)vj的頂點(diǎn)序列為從頂點(diǎn)vi到頂點(diǎn)vj的路徑。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第7頁。非線性數(shù)據(jù)結(jié)構(gòu)8（7）權(quán)：有些圖的邊附帶有數(shù)據(jù)信息，這些附帶的數(shù)據(jù)信息稱為權(quán)。帶權(quán)的圖也稱作網(wǎng)絡(luò)或網(wǎng)。2135467879610612715163BACDE60304575804035施工進(jìn)度圖

交通網(wǎng)絡(luò)圖

非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第8頁。非線性數(shù)據(jù)結(jié)構(gòu)9（8）路徑長度：對于不帶權(quán)的圖，一條路徑的路徑長度是指該路徑上的邊的條數(shù)；對于帶權(quán)的圖，一條路徑的路徑長度是指該路徑上各個(gè)邊權(quán)值的總和。（9）子圖：設(shè)有圖G1={V1,E1}和圖G2={V2,E2}，若V2V1且E2E1，則稱圖G2是圖G1的子圖。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第9頁。非線性數(shù)據(jù)結(jié)構(gòu)10（10）連通圖和強(qiáng)連通圖：在無向圖中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱頂點(diǎn)vi和頂點(diǎn)vj是連通的。如果圖中任意一對頂點(diǎn)都是連通的，則稱該圖是連通圖。圖中的無向圖a和b都是連通圖。在有向圖中，若對于任意一對頂點(diǎn)vi和頂點(diǎn)vj（vi≠vj）都存在路徑，則稱圖G是強(qiáng)連通圖。圖中的有向圖d是強(qiáng)連通圖。（11）生成樹：一個(gè)連通圖的最小連通子圖稱作該圖的生成樹。有n個(gè)頂點(diǎn)的連通圖的生成樹有n個(gè)頂點(diǎn)和n-1條邊。（12）簡單路徑和回路：若路徑上各頂點(diǎn)v1,v2,…,vm,互不重復(fù)，則稱這樣的路徑為簡單路徑；若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合，則稱這樣的路徑為回路或環(huán)。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第10頁。非線性數(shù)據(jù)結(jié)構(gòu)11數(shù)據(jù)集合：由一組頂點(diǎn)集合｛vi

｝和一組邊集合{ej}組成。當(dāng)為帶權(quán)圖時(shí)每條邊上權(quán)wj構(gòu)成權(quán)集合{wi}。操作集合：(1)初始化Initiate(G,n)(2)插入頂點(diǎn)InsertVertex(G,vertex)(3)插入邊InsertEdge(G,v1,v2,weight)(4)刪除邊DeleteEdge（G,v1,v2)(5)刪除頂點(diǎn)DeleteVertex(G,vertex)(6)第一個(gè)鄰接結(jié)點(diǎn)GetFirstVex(G,v)(7)下一個(gè)鄰接結(jié)點(diǎn)GetNextVex(G,intv1,v2)(8)遍歷DepthFirstSearch(G)2.圖的抽象數(shù)據(jù)類型非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第11頁。非線性數(shù)據(jù)結(jié)構(gòu)128.2圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)主要有鄰接矩陣和鄰接表兩種。1.圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)假設(shè)圖G=(V,E)有n個(gè)頂點(diǎn)，即V={v0,v1,…,vn-1}，E可用如下形式的矩陣A描述，對于A中的每一個(gè)元素aij，滿足：由于矩陣A中的元素aij表示了頂點(diǎn)vi和頂點(diǎn)vj之間邊的關(guān)系，或者說，A中的元素aij表示了頂點(diǎn)vi和頂點(diǎn)vj（0≤j≤n-1）的鄰接關(guān)系，所以矩陣A稱作鄰接矩陣。?íì>?<?=否則或若0,),(1EvvEvvajijiij非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第12頁。非線性數(shù)據(jù)結(jié)構(gòu)13無向圖的鄰接矩陣一定是對稱矩陣有向圖的鄰接矩陣一般是非對稱矩陣其中V表示了圖的頂點(diǎn)集合，A表示了圖的鄰接矩陣21435úúúúúú?ùêêêêêê?é=54321Vúúúúúú?ùêêêêêê?é=0010100011100010100111110A(b)(a)BADCEúúúúúú?ùêêêêêê?é=EDCBAVúúúúúú?ùêêêêêê?é=0000000010100000000011110A(b)(a)非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第13頁。非線性數(shù)據(jù)結(jié)構(gòu)14帶權(quán)圖及其鄰接矩陣其中V表示了圖的頂點(diǎn)集合，A表示了圖的鄰接矩陣。對于帶權(quán)圖，鄰接矩陣第i行中所有0<aij<∞的元素個(gè)數(shù)等于第i個(gè)頂點(diǎn)的出度，鄰接矩陣第j列中所有0<aij<∞的元素個(gè)數(shù)等于第j個(gè)頂點(diǎn)的入度。214356úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥=080070807005040500304002030200Aúúúúúúúú?ùêêêêêêêê?é=654321V(a)(b)402030507080非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第14頁。非線性數(shù)據(jù)結(jié)構(gòu)152.圖的鄰接表存儲(chǔ)結(jié)構(gòu)當(dāng)圖的邊數(shù)少于頂點(diǎn)個(gè)數(shù)且頂點(diǎn)個(gè)數(shù)值較大時(shí)，圖的鄰接n×n矩陣的存儲(chǔ)問題就變成了稀疏矩陣的存儲(chǔ)問題，此時(shí)，鄰接表就是一種較鄰接矩陣更為有效的存儲(chǔ)結(jié)構(gòu)。BADCE(a)01234ABCDE0datasorce1432adjdestnext23411∧

∧

∧

∧

(b)4∧

非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第15頁。非線性數(shù)據(jù)結(jié)構(gòu)16數(shù)組的data域存儲(chǔ)圖的頂點(diǎn)信息，sorce域存儲(chǔ)該頂點(diǎn)在數(shù)組中的下標(biāo)序號(hào)，adj域?yàn)樵擁旤c(diǎn)的鄰接頂點(diǎn)單鏈表的頭指針。第i行單鏈表中的dest域存儲(chǔ)所有起始頂點(diǎn)為vi的鄰接頂點(diǎn)vj在數(shù)組中的下標(biāo)序號(hào)，next域?yàn)閱捂湵碇邢乱粋€(gè)鄰接頂點(diǎn)的指針域。如果是帶權(quán)圖，單鏈表中需再增加cost域，用來存儲(chǔ)邊<vi,vj>的權(quán)值wij。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第16頁。非線性數(shù)據(jù)結(jié)構(gòu)17存儲(chǔ)空間：對于有n個(gè)頂點(diǎn)，e條邊的無向圖而言，若采取鄰接表作為存儲(chǔ)結(jié)構(gòu)，則需要n個(gè)表頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。

無向圖的度：在無向圖的鄰接表中，頂點(diǎn)vi的度恰好就是第i個(gè)邊鏈表上結(jié)點(diǎn)的個(gè)數(shù)。

有向圖的度：在有向圖中，第i個(gè)邊鏈表上頂點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的出度。要想求得該頂點(diǎn)的入度，則必須遍歷整個(gè)鄰接表。在所有單鏈表中查找鄰接點(diǎn)域的值為i的結(jié)點(diǎn)并計(jì)數(shù)求和。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第17頁。非線性數(shù)據(jù)結(jié)構(gòu)18由此可見，對于用鄰接表方式存儲(chǔ)的有向圖，求頂點(diǎn)的入度并不方便，因此需要有一種解決的方法－逆鄰接表法。對圖中的每一頂點(diǎn)vi建立一個(gè)遞鄰接表，即對每個(gè)頂點(diǎn)vi建立一個(gè)所有以頂點(diǎn)vi為弧頭的弧的表，這樣求頂點(diǎn)vi的入度即是計(jì)算逆鄰接表中第i個(gè)頂點(diǎn)的邊鏈表中結(jié)點(diǎn)個(gè)數(shù)。

非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第18頁。非線性數(shù)據(jù)結(jié)構(gòu)198.3鄰接矩陣圖類1.鄰接矩陣圖類的設(shè)計(jì)和實(shí)現(xiàn)鄰接矩陣圖類實(shí)現(xiàn)如下：#include"SeqList.h" //包含動(dòng)態(tài)數(shù)組結(jié)構(gòu)的順序表類

classAdjMWGraph{private: SeqListVertices; //頂點(diǎn)順序表

intEdge[MaxVertices][MaxVertices]; //邊權(quán)值數(shù)組

intnumOfEdges; //邊的個(gè)數(shù)

voidDepthFirstSearch(constintv,intvisited[],voidVisit(VerTitem)); voidBroadFirstSearch(constintv,intvisited[],voidVisit(VerTitem));非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第19頁。非線性數(shù)據(jù)結(jié)構(gòu)20public: AdjMWGraph(constintsz=MaxVertices); //構(gòu)造函數(shù) ~AdjMWGraph(void){}; //析構(gòu)函數(shù)

intNumOfVertices(void) //取頂點(diǎn)個(gè)數(shù) {returnVertices.Size();} intNumOfEdges(void) //取邊的個(gè)數(shù) {returnnumOfEdges;} VerTGetValue(constintv); //取頂點(diǎn)數(shù)值

intGetWeight(constintv1,constintv2); //取邊的權(quán)值

voidInsertVertex(constVerT&vertex); //插入頂點(diǎn)

voidInsertEdge(constintv1,constintv2,intweight);//插入邊

voidDeleteVertex(constintv); //刪除頂點(diǎn)

voidDeleteEdge(constintv1,constintv2); //刪除邊非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第20頁。非線性數(shù)據(jù)結(jié)構(gòu)21intGetFirstNeighbor(constintv); //取第一個(gè)鄰接頂點(diǎn)intGetNextNeighbor(constintv1,constintv2);//取下一個(gè)鄰接頂點(diǎn)

voidDepthFirstSearch(voidVisit(VerTitem)); //深度優(yōu)先遍歷voidBroadFirstSearch(voidVisit(VerTitem)); //廣度優(yōu)先遍歷};非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第21頁。非線性數(shù)據(jù)結(jié)構(gòu)22AdjMWGraph::AdjMWGraph(constintsz):Vertices(sz)//構(gòu)造函數(shù){

for(inti=0;i<sz;i++) for(intj=0;j<sz;j++) { if(i==j)Edge[i][j]=0; elseEdge[i][j]=MaxWeight; } numOfEdges=0;}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第22頁。非線性數(shù)據(jù)結(jié)構(gòu)23VerTAdjMWGraph::GetValue(constintv)//取頂點(diǎn)v的數(shù)值{

if(v<0||v>Vertices.Size()) { cout<<"參數(shù)v越界出錯(cuò)!"<<endl; exit(0); } returnVertices.GetData(v);}22非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第23頁。非線性數(shù)據(jù)結(jié)構(gòu)24intAdjMWGraph::GetWeight(constintv1,constintv2)//取起始頂點(diǎn)為v1、終止頂點(diǎn)為v2的邊的權(quán)值{

if(v1<0||v1>Vertices.Size()||v2<0||v2>Vertices.Size()) { cout<<"參數(shù)v1或v2越界出錯(cuò)!"<<endl; exit(0); } returnEdge[v1][v2];}voidAdjMWGraph::InsertVertex(constVerT&vertex)//插入頂點(diǎn)vertex{ //把頂點(diǎn)vertex插入到順序表的當(dāng)前表尾位置

Vertices.Insert(vertex,Vertices.Size());}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第24頁。非線性數(shù)據(jù)結(jié)構(gòu)25voidAdjMWGraph::InsertEdge(constintv1,constintv2,intweight)//插入一條起始頂點(diǎn)為v1、終止頂點(diǎn)為v2、權(quán)值為weight的邊{

if(v1<0||v1>Vertices.Size()||v2<0||v2>Vertices.Size()) { cout<<"參數(shù)v1或v2越界出錯(cuò)!"<<endl; exit(0); } Edge[v1][v2]=weight; //插入邊

numOfEdges++; //邊的個(gè)數(shù)加1}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第25頁。非線性數(shù)據(jù)結(jié)構(gòu)26voidAdjMWGraph::DeleteVertex(constintv)//刪除頂點(diǎn)v{ //刪除所有包含頂點(diǎn)v的邊

for(inti=0;i<Vertices.Size();i++) for(intj=0;j<Vertices.Size();j++) if((i==v||j==v)&&i!=j&&Edge[i][j]>0&&Edge[i][j]<MaxWeight) { Edge[i][j]=MaxWeight; //把該邊的權(quán)值置為無窮大

numOfEdges--; //邊的個(gè)數(shù)減1 }

Vertices.Delete(v); //刪除頂點(diǎn)v}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第26頁。非線性數(shù)據(jù)結(jié)構(gòu)27voidAdjMWGraph::DeleteEdge(constintv1,constintv2)//刪除一條起始頂點(diǎn)為v1、終止頂點(diǎn)為v2的邊{

if(v1<0||v1>Vertices.Size()|| v2<0||v2>Vertices.Size()||v1==v2) { cout<<"參數(shù)v1或v2出錯(cuò)!"<<endl; exit(0); }

if(Edge[v1][v2]==MaxWeight||v1==v2) { cout<<"該邊不存在!"<<endl; exit(0); }

Edge[v1][v2]=MaxWeight; //把該邊的權(quán)值置為無窮大

numOfEdges--; //邊的個(gè)數(shù)減1}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第27頁。非線性數(shù)據(jù)結(jié)構(gòu)28intAdjMWGraph::GetFirstNeighbor(constintv)//取頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)。若存在返回該頂點(diǎn)的下標(biāo)序號(hào)，否則返回-1{

if(v<0||v>Vertices.Size()) { cout<<"參數(shù)v1越界出錯(cuò)!"<<endl; exit(0); }

for(intcol=0;col<=Vertices.Size();col++) if(Edge[v][col]>0&&Edge[v][col]<MaxWeight)returncol; return-1;}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第28頁。非線性數(shù)據(jù)結(jié)構(gòu)29intAdjMWGraph::GetNextNeighbor(constintv1,constintv2)//取頂點(diǎn)v1的鄰接頂點(diǎn)v2后的鄰接頂點(diǎn)//若存在返回該頂點(diǎn)的下標(biāo)序號(hào)，否則返回-1{

if(v1<0||v1>Vertices.Size()||v2<0||v2>Vertices.Size()) { cout<<"參數(shù)v1或v2越界出錯(cuò)!"<<endl; exit(0); }

for(intcol=v2+1;col<=Vertices.Size();col++) if(Edge[v1][col]>0&&Edge[v1][col]<MaxWeight)returncol; return-1;}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第29頁。非線性數(shù)據(jù)結(jié)構(gòu)302.鄰接矩陣圖類的測試?yán)?-1以下圖所示的帶權(quán)有向圖為例編寫測試鄰接矩陣圖類的程序。ABCDE1040305020圖的創(chuàng)建函數(shù)設(shè)計(jì)如下：structRowColWeight{ introw; //行下標(biāo)

intcol; //列下標(biāo)

intweight; //權(quán)值};圖8-8非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第30頁。非線性數(shù)據(jù)結(jié)構(gòu)31voidCreatGraph(AdjMWGraph&G,DataTypeV[],intn,RowColWeightE[],inte)//在圖G中插入n個(gè)頂點(diǎn)V和e條邊E{ //在圖G中插入n個(gè)頂點(diǎn)for(inti=0;i<n;i++)G.InsertVertex(V[i]);

//在圖G中插入e條邊

for(intk=0;k<e;k++)G.InsertEdge(E[k].row,E[k].col,E[k].weight);}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第31頁。非線性數(shù)據(jù)結(jié)構(gòu)32測試程序設(shè)計(jì)如下：#include<iostream.h>#include<stdlib.h>

typedefcharVerT; //定義鄰接矩陣圖類中的VerTtypedefcharDataType; //定義順序表類中的DataTypeconstintMaxVertices=100; //定義最大頂點(diǎn)個(gè)數(shù)constintMaxWeight=10000; //定義權(quán)值的無窮大

#include"AdjMWGraph.h" //包含鄰接矩陣的圖類#include"CreatAdjMWGraph.h“//包含鄰接矩陣圖的建函數(shù)非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第32頁。非線性數(shù)據(jù)結(jié)構(gòu)33

voidmain(void){ AdjMWGraphg; chara[]={'A','B','C','D','E'}; RowColWeightrcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}}; intn=5,e=5;

CreatGraph(g,a,n,rcw,e); //創(chuàng)建圖

cout<<"頂點(diǎn)個(gè)數(shù)為："<<g.NumOfVertices()<<endl; cout<<"邊的條數(shù)為："<<g.NumOfEdges()<<endl;

g.DeleteVertex(3); //刪除頂點(diǎn)3

g.DeleteEdge(0,4); //刪除邊<0,4>

cout<<endl<<"頂點(diǎn)個(gè)數(shù)為："<<g.NumOfVertices(); cout<<endl<<"邊的條數(shù)為："<<g.NumOfEdges()<<endl;}測試代碼非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第33頁。非線性數(shù)據(jù)結(jié)構(gòu)348.4圖的遍歷1.圖的深度和廣度優(yōu)先遍歷算法圖的遍歷是訪問圖中的每一個(gè)頂點(diǎn)且每個(gè)頂點(diǎn)只被訪問一次。算法設(shè)計(jì)需要考慮三個(gè)問題：（1）算法的參數(shù)要指定訪問的第一個(gè)頂點(diǎn)；（2）要考慮遍歷路徑可能出現(xiàn)的死循環(huán)問題；（3）要使一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)按照某種次序被訪問。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第34頁。非線性數(shù)據(jù)結(jié)構(gòu)35一、圖的深度優(yōu)先遍歷算法。圖的深度優(yōu)先遍歷算法是遍歷時(shí)深度優(yōu)先的算法，是一個(gè)遞歸算法。連通圖的深度優(yōu)先遍歷遞歸算法為：（1）訪問頂點(diǎn)v并標(biāo)記頂點(diǎn)v為已訪問；（2）查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)w；（3）若頂點(diǎn)v的鄰接頂點(diǎn)w存在，則繼續(xù)執(zhí)行，否則算法結(jié)束；（4）若頂點(diǎn)w尚未被訪問則深度優(yōu)先搜索遞歸訪問頂點(diǎn)w；（5）查找頂點(diǎn)v的w鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)w，轉(zhuǎn)到步驟（3）。上述遞歸算法屬于回溯算法非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第35頁。非線性數(shù)據(jù)結(jié)構(gòu)368ADGBEHCFI1236710114155149131216訪問序列為：A、B、C、F、E、G、D、H、I。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第36頁。非線性數(shù)據(jù)結(jié)構(gòu)37二、圖的廣度優(yōu)先遍歷算法圖的廣度優(yōu)先遍歷算法是一個(gè)分層搜索的過程，需要一個(gè)隊(duì)列以保持訪問過的頂點(diǎn)的順序，以便按訪問過的頂點(diǎn)的順序來訪問這些頂點(diǎn)的鄰接頂點(diǎn)。連通圖的廣度優(yōu)先遍歷算法為：（1）訪問初始頂點(diǎn)v并標(biāo)記頂點(diǎn)v為已訪問；（2）頂點(diǎn)v入隊(duì)列；（3）當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行，否則算法結(jié)束；（4）出隊(duì)列取得隊(duì)頭頂點(diǎn)u；（5）查找頂點(diǎn)u的第一個(gè)鄰接頂點(diǎn)w；（6）若頂點(diǎn)u的鄰接頂點(diǎn)w不存在，則轉(zhuǎn)到步驟（3），否則循環(huán)執(zhí)行，（6.1）若頂點(diǎn)w尚未被訪問則訪問頂點(diǎn)w并標(biāo)記頂點(diǎn)w為已訪問；（6.2）頂點(diǎn)w入隊(duì)列；（6.3）查找頂點(diǎn)u的w鄰接頂點(diǎn)后的下一個(gè)鄰接頂點(diǎn)w，轉(zhuǎn)到步驟（6）。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第37頁。非線性數(shù)據(jù)結(jié)構(gòu)38ADGBEHCFI14657823訪問序列為：A、B、E、D、C、G、F、H、I。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第38頁。非線性數(shù)據(jù)結(jié)構(gòu)39V1V2V3V4V5V6V7V8深到底回退深到底V1V2V4V8V5（V2V8均已訪問）深到底V3V6V7回退訪問非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第39頁。非線性數(shù)據(jù)結(jié)構(gòu)40對圖4廣度優(yōu)先搜索，訪問頂點(diǎn)序列為：

V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第40頁。非線性數(shù)據(jù)結(jié)構(gòu)41三、非連通圖的遍歷對于非連通圖，從圖的任意一個(gè)頂點(diǎn)開始深度或廣度優(yōu)先遍歷并不能訪問圖中的所有頂點(diǎn)。只能訪問和初始頂點(diǎn)連通的所有頂點(diǎn)。但是，每一個(gè)頂點(diǎn)都作為一次初始頂點(diǎn)進(jìn)行深度優(yōu)先遍歷或廣度優(yōu)先遍歷，并根據(jù)頂點(diǎn)的訪問標(biāo)記來判斷是否需要訪問該頂點(diǎn)，就一定可以訪問非連通圖中的所有頂點(diǎn)。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第41頁。非線性數(shù)據(jù)結(jié)構(gòu)42鄰接矩陣存儲(chǔ)結(jié)構(gòu)圖類的深度優(yōu)先遍歷成員函數(shù)如下：voidAdjMWGraph::DepthFirstSearch(constintv,intvisited[],voidVisit(VerTitem))//連通圖G以v為初始頂點(diǎn)序號(hào)、訪問操作為Visit()的深度優(yōu)先遍歷//數(shù)組visited標(biāo)記了相應(yīng)頂點(diǎn)是否已訪問過，0表示未訪問，1表示已訪問{

Visit(GetValue(v)); //訪問該頂點(diǎn)

visited[v]=1; //置已訪問標(biāo)記

intw=GetFirstNeighbor(v); //取第一個(gè)鄰接頂點(diǎn)

while(w!=-1) //當(dāng)鄰接頂點(diǎn)存在時(shí)循環(huán) {

if(!visited[w])DepthFirstSearch(w,visited,Visit);//遞歸

w=GetNextNeighbor(v,w); //取下一個(gè)鄰接頂點(diǎn) }}2.圖的深度和廣度優(yōu)先遍歷函數(shù)實(shí)現(xiàn)一、深度優(yōu)先遍歷非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第42頁。非線性數(shù)據(jù)結(jié)構(gòu)43二、非連通圖的深度優(yōu)先遍歷voidAdjMWGraph::DepthFirstSearch(voidVisit(VerTitem))//非連通圖G訪問操作為Visit()的深度優(yōu)先遍歷{

int*visited=newint[NumOfVertices()];

for(inti=0;i<NumOfVertices();i++)visited[i]=0; //初始化訪問標(biāo)記

for(i=0;i<NumOfVertices();i++) if(!visited[i])DepthFirstSearch(i,visited,Visit); //深度優(yōu)先遍歷

delete[]visited;}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第43頁。非線性數(shù)據(jù)結(jié)構(gòu)44三、廣度優(yōu)先遍歷#include"SeqQueue.h" //包含靜態(tài)數(shù)組結(jié)構(gòu)的順序隊(duì)列類voidAdjMWGraph::BroadFirstSearch(constintv,intvisited[],voidVisit(VerTitem))//連通圖G以v為初始頂點(diǎn)序號(hào)、訪問操作為Visit()的廣度優(yōu)先遍歷//數(shù)組visited標(biāo)記了相應(yīng)頂點(diǎn)是否已訪問過，0表示未訪問，1表示已訪問{

VerTu,w; SeqQueuequeue; //定義隊(duì)列

Visit(GetValue(v)); //訪問該頂點(diǎn)

visited[v]=1; //置已訪問標(biāo)記

queue.Append(v); //頂點(diǎn)v入隊(duì)列

while(queue.NotEmpty()) //隊(duì)列非空時(shí)循環(huán) {

u=queue.Delete(); //出隊(duì)列

w=GetFirstNeighbor(u);//取頂點(diǎn)u的第一個(gè)鄰接頂點(diǎn)非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第44頁。非線性數(shù)據(jù)結(jié)構(gòu)45while(w!=-1) //鄰接頂點(diǎn)存在時(shí) {

if(!visited[w]) //若該頂點(diǎn)沒有訪問過 {

Visit(GetValue(w)); //訪問該頂點(diǎn)

visited[w]=1; //置已訪問標(biāo)記

queue.Append(w); //頂點(diǎn)w入隊(duì)列 } //取頂點(diǎn)u的鄰接頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)

w=GetNextNeighbor(u,w); } }}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第45頁。非線性數(shù)據(jù)結(jié)構(gòu)46四、非連通圖的廣度優(yōu)先遍歷voidAdjMWGraph::BroadFirstSearch(voidVisit(VerTitem))//非連通圖G訪問操作為Visit()的廣度優(yōu)先遍歷{

int*visited=newint[NumOfVertices()];

for(inti=0;i<NumOfVertices();i++)visited[i]=0; for(i=0;i<NumOfVertices();i++) if(!visited[i])BroadFirstSearch(i,visited,Visit);

delete[]visited;}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第46頁。非線性數(shù)據(jù)結(jié)構(gòu)47五、程序舉例例8-2以圖8-8所示的帶權(quán)有向圖為例，編寫測試上述圖的深度優(yōu)先和廣度優(yōu)先遍歷成員函數(shù)的程序。測試程序設(shè)計(jì)如下：#include<iostream.h>#include<stdlib.h>

typedefcharVerT; //定義鄰接矩陣圖類中的VerTtypedefcharDataType; //定義順序表類中的DataTypeconstintMaxVertices=100; //定義最大頂點(diǎn)個(gè)數(shù)constintMaxQueueSize=100; //定義隊(duì)列的最大個(gè)數(shù)constintMaxWeight=10000; //定義權(quán)值的無窮大

#include"AdjMWGraph.h" //包含鄰接矩陣的圖類#include"CreatAdjMWGraph.h" //包含鄰接矩陣圖的創(chuàng)建函數(shù)

voidPrintchar(charitem) //訪問操作函數(shù){

cout<<item<<"";}非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第47頁。非線性數(shù)據(jù)結(jié)構(gòu)48voidmain(void){ AdjMWGraphg; chara[]={'A','B','C','D','E'}; RowColWeightrcw[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}}; intn=5,e=5;

CreatGraph(g,a,n,rcw,e);

cout<<"深度優(yōu)先搜索序列為：";

g.DepthFirstSearch(Printchar); cout<<endl<<"廣度優(yōu)先搜索序列為：";

g.BroadFirstSearch(Printchar);}測試代碼非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第48頁。非線性數(shù)據(jù)結(jié)構(gòu)498.5最小生成樹1.基本概念一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，它包含原圖中的所有n個(gè)頂點(diǎn)，并且有保持圖連通的最少的邊。注意：（1）若在生成樹中刪除一條邊就會(huì)使該生成樹因變成非連通圖而不再滿足生成樹的定義；（2）若在生成樹中增加一條邊就會(huì)使該生成樹中因存在回路而不再滿足生成樹的定義；（3）一個(gè)連通圖的生成樹可能有許多；（4）有n個(gè)頂點(diǎn)的無向連通圖，無論它的生成樹的形狀如何，一定有且只有n-1條邊。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第49頁。非線性數(shù)據(jù)結(jié)構(gòu)501V2V3V4V5V6V1V2V3V4V5V6V1V2V3V4V5V6V(a)(b)(c)無向圖和它的不同的生成樹非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第50頁。非線性數(shù)據(jù)結(jié)構(gòu)51最小生成樹的實(shí)用例子很多例1：N臺(tái)計(jì)算機(jī)之間建立通訊網(wǎng)頂點(diǎn)表示computer邊表示通訊線權(quán)值表示通訊線的代價(jià)（通訊線長度，computer間距離等）要求：①n臺(tái)計(jì)算機(jī)中的任何兩臺(tái)能通過網(wǎng)進(jìn)行通訊；②使總的代價(jià)最小。--求最小生成樹[T]非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第51頁。非線性數(shù)據(jù)結(jié)構(gòu)52

最小生成樹的實(shí)用例子例2：郵遞員送信線路[T]頂點(diǎn)表示投遞點(diǎn)邊表示街道權(quán)值表示街道的長度要求：①完成n個(gè)投遞點(diǎn)的投遞；②使總路徑長度最短,即求最小生成樹[T]非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第52頁。非線性數(shù)據(jù)結(jié)構(gòu)53如果無向連通圖是一個(gè)帶權(quán)圖，那么它的所有生成樹中必有一棵邊的權(quán)值總和最小的生成樹，我們稱這棵生成樹為最小代價(jià)生成樹，簡稱最小生成樹。構(gòu)造有n個(gè)頂點(diǎn)的無向連通帶權(quán)圖的最小生成樹必須滿足以下三條：（1）構(gòu)造的最小生成樹必須包括n個(gè)頂點(diǎn)；（2）構(gòu)造的最小生成樹中有且只有n-1條邊；（3）構(gòu)造的最小生成樹中不存在回路。典型的構(gòu)造方法有兩種，一種稱作普里姆（Prim）算法，另一種稱作克魯斯卡爾（Kruskal）算法。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第53頁。非線性數(shù)據(jù)結(jié)構(gòu)542.普里姆算法一、算法思想假設(shè)G=(V,E)為一個(gè)帶權(quán)圖，其中V為帶權(quán)圖中頂點(diǎn)的集合，E為帶權(quán)圖中邊的權(quán)值集合。設(shè)置兩個(gè)新的集合U和T，其中U用于存放帶權(quán)圖G的最小生成樹的頂點(diǎn)的集合，T用于存放帶權(quán)圖G的最小生成樹的權(quán)值的集合。普里姆算法思想是：令集合U的初值為U={u0}（即假設(shè)構(gòu)造最小生成樹時(shí)從頂點(diǎn)u0開始），集合T的初值為T={}。從所有頂點(diǎn)u∈U和頂點(diǎn)v∈V-U的帶權(quán)邊中選出具有最小權(quán)值的邊(u,v)，將頂點(diǎn)v加入集合U中，將邊(u,v)加入集合T中。如此不斷重復(fù)，當(dāng)U=V時(shí)則最小生成樹構(gòu)造完畢。此時(shí)集合U中存放著最小生成樹頂點(diǎn)的集合，集合T中存放著最小生成樹邊的權(quán)值集合。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第54頁。非線性數(shù)據(jù)結(jié)構(gòu)55ACBGEFD50604552423065504070ACBGEFDACBGEFD50ACBGEFD5040ACBGEFD505040ACBGEFD50305040ACBGEFD5042305040ACBGEFD504542305040(a)(b)(c)(d)(e)(f)(g)(h)圖8-10

普里姆算法構(gòu)造最小生成樹的過程演示非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第55頁。非線性數(shù)據(jù)結(jié)構(gòu)56abcdegf課堂練習(xí)195141827168213ae12dcbgf7148531621所得生成樹權(quán)值和=14+8+3+5+16+21=67非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第56頁。非線性數(shù)據(jù)結(jié)構(gòu)57二、普里姆函數(shù)設(shè)計(jì)普里姆函數(shù)應(yīng)有兩個(gè)參數(shù)，一個(gè)參數(shù)是圖G，定義為鄰接矩陣存儲(chǔ)結(jié)構(gòu)圖類的對象；另一個(gè)參數(shù)是通過函數(shù)得到的最小生成樹的頂點(diǎn)數(shù)據(jù)和相應(yīng)頂點(diǎn)的邊的權(quán)值數(shù)據(jù)closeVertex。其數(shù)據(jù)類型定義為如下結(jié)構(gòu)體：structMinSpanTree{ VerTvertex; intweight;};其中，vertex域用來保存最小生成樹每條邊的弧頭頂點(diǎn)數(shù)據(jù)，weight域用來保存最小生成樹的相應(yīng)邊的權(quán)值。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第57頁。非線性數(shù)據(jù)結(jié)構(gòu)58普里姆函數(shù)設(shè)計(jì)：voidPrim(AdjMWGraph&G,MinSpanTreecloseVertex[])//用普里姆算法建立帶權(quán)圖G的最小生成樹closeVertex{ intn=G.NumOfVertices(),minCost; int*lowCost=newint[n]; inti,j,k;

for(i=1;i<n;i++) //初始化

lowCost[i]=G.GetWeight(0,i);

//從頂點(diǎn)0出發(fā)構(gòu)造最小生成樹

closeVertex[0].vertex=G.GetValue(0); //保存頂點(diǎn)0

lowCost[0]=-1; //標(biāo)記頂點(diǎn)0

for(i=1;i<n;i++) { //尋找當(dāng)前最小權(quán)值的邊所對應(yīng)的弧頭頂點(diǎn)k minCost=MaxWeight;//MaxWeight為定義的最大權(quán)值非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第58頁。非線性數(shù)據(jù)結(jié)構(gòu)59for(j=1;j<n;j++){ if(lowCost[j]<minCost&&lowCost[j]>0) { minCost=lowCost[j]; k=j; }}

closeVertex[i].vertex=G.GetValue(k);//保存弧頭頂點(diǎn)k closeVertex[i].weight=minCost; //保存相應(yīng)的權(quán)值

lowCost[k]=-1; //標(biāo)記頂點(diǎn)k //根據(jù)加入集合U的頂點(diǎn)k修改lowCost中的數(shù)值

for(intj=1;j<n;j++) { if(G.GetWeight(k,j)<lowCost[j]) lowCost[j]=G.GetWeight(k,j); } }非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第59頁。非線性數(shù)據(jù)結(jié)構(gòu)60設(shè)計(jì)說明：（1）函數(shù)中定義一個(gè)臨時(shí)數(shù)組lowCost，數(shù)組元素lowCost[v]中保存了集合U中頂點(diǎn)ui與集合V-U中頂點(diǎn)vj的所有邊中當(dāng)前具有最小權(quán)值的邊(u,v)。（2）集合U的初值為U={序號(hào)為0的頂點(diǎn)}。lowCost的初始值為鄰接矩陣數(shù)組中第0行的值，這樣初始時(shí)lowCost中就存放了從集合U中頂點(diǎn)0到集合V-U中各個(gè)頂點(diǎn)的權(quán)值。（3）每次從lowCost中尋找具有最小權(quán)值的邊，根據(jù)lowCost的定義，這樣的邊其弧頭頂點(diǎn)必然為集合U中的頂點(diǎn)，其弧尾頂點(diǎn)必然為集合V-U中的頂點(diǎn)。當(dāng)選到一條這樣的邊(u,v)，就保存其頂點(diǎn)數(shù)據(jù)和權(quán)值數(shù)據(jù)到參數(shù)closeVertex中，并將lowCost[v]置為-1，表示頂點(diǎn)v加入了集合U中。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第60頁。非線性數(shù)據(jù)結(jié)構(gòu)61（4）當(dāng)頂點(diǎn)v從集合V-U加入到集合U后，若存在一條邊(u,v)，u是集合U的頂點(diǎn)，v是集合V-U的頂點(diǎn)，且邊(u,v)較原先lowCost[v]的代價(jià)更小，則用這樣的權(quán)值修改原先lowCost[v]中的相應(yīng)權(quán)值。（5）以圖8-10（a）所示的無向連通帶權(quán)圖為例，調(diào)用普里姆函數(shù)時(shí)數(shù)組lowCost的動(dòng)態(tài)變化過程如圖示。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第61頁。非線性數(shù)據(jù)結(jié)構(gòu)620-115023456lowCost60∞

∞

∞

∞

0-11-123654405660∞

∞

0-11-123504-1570660∞

0-11-123-14-1530642520-11-123-14-15-1642520-11-123-14-15-16-1450-11-123-14-15-16-1-1(a)(b)(c)(d)(e)(f)(g)lowCostlowCostlowCostlowCostlowCostlowCost非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第62頁。非線性數(shù)據(jù)結(jié)構(gòu)63函數(shù)主要是一個(gè)兩重循環(huán)，其中每一重循環(huán)的次數(shù)均為頂點(diǎn)個(gè)數(shù)n，所以該算法的時(shí)間復(fù)雜度為O(n2)。三、測試程序例8-3以圖8-10（a）所示的無向連通帶權(quán)圖為例設(shè)計(jì)測試上述Prim函數(shù)的程序。測試程序非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第63頁。非線性數(shù)據(jù)結(jié)構(gòu)643.克魯斯卡爾算法克魯斯卡爾算法是一種按照帶權(quán)圖中邊的權(quán)值的遞增順序構(gòu)造最小生成樹的方法?？唆斔箍査惴ㄋ枷胧牵涸O(shè)無向連通帶權(quán)圖G=(V,E)，其中V為頂點(diǎn)的集合，E為邊的集合。設(shè)帶權(quán)圖G的最小生成樹T由頂點(diǎn)集合和邊的集合構(gòu)成，其初值為T=(V,{})，即初始時(shí)最小生成樹T只由帶權(quán)圖G中的頂點(diǎn)集合組成，各頂點(diǎn)之間沒有一條邊。這樣，最小生成樹T中的各個(gè)頂點(diǎn)各自構(gòu)成一個(gè)連通分量。然后，按照邊的權(quán)值遞增的順序考察帶權(quán)圖G中的邊集合E中的各條邊，①若被考察的邊的兩個(gè)頂點(diǎn)屬于T的兩個(gè)不同的連通分量，則將此邊加入到最小生成樹T，同時(shí)把兩個(gè)連通分量連接為一個(gè)連通分量；②若被考察的邊的兩個(gè)頂點(diǎn)屬于T的同一個(gè)連通分量，則將此邊舍去。如此下去，當(dāng)T中的連通分量個(gè)數(shù)為1時(shí)，T中的該連通分量即為帶權(quán)圖G的一棵最小生成樹非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第64頁。非線性數(shù)據(jù)結(jié)構(gòu)65ACBGEFD30ACBGEFD3040ACBGEFD423040ACBGEFD45423040ACBGEFD5045423040ACBGEFD504542305040(a)(b)(c)(d)(e)(f)克魯斯卡爾算法構(gòu)造最小生成樹的過程演示非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第65頁。非線性數(shù)據(jù)結(jié)構(gòu)66abcdegf195141827168213ae12dcbgf7148531621課堂練習(xí)：7121819非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第66頁。非線性數(shù)據(jù)結(jié)構(gòu)67補(bǔ)充:有向無環(huán)圖的應(yīng)用1、拓?fù)渑判颍═opologicalSort）

AOV-網(wǎng)：用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向無環(huán)圖，稱為頂點(diǎn)表示活動(dòng)的網(wǎng)（ActivityOnVertexNetwork），簡稱為AOV-網(wǎng)。

如下：表7-2課程關(guān)系，用頂點(diǎn)表示課程，弧表示先決條件，則表7-2可用一個(gè)有向無環(huán)圖表示。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第67頁。非線性數(shù)據(jù)結(jié)構(gòu)68表7-2課程關(guān)系非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第68頁。非線性數(shù)據(jù)結(jié)構(gòu)69拓?fù)湫蛄校涸谟邢驁DG=（V，{E}）中，

V中頂點(diǎn)的線性序列（vi1,,vi1,,vi3,…，vin）稱為拓?fù)湫蛄?。此序列必須滿足：對序列中任意兩個(gè)頂點(diǎn)vi、vj，在G中有一條從vi到vj的路徑，則在序列中vi必排在vj之前。

如前圖的一個(gè)拓?fù)湫蛄袨椋篊1,C2,C3,C4,C5,C8,C9,C7,C6。

非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第69頁。非線性數(shù)據(jù)結(jié)構(gòu)70AOV-網(wǎng)的特性如下：

若vi為vj的先行活動(dòng)，vj為vk的先行活動(dòng)，則vi必為vk的先行活動(dòng)，即先行關(guān)系具有可傳遞性。AOV-網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹?/p>

對圖7.21的另一個(gè)拓?fù)湫蛄袨椋篊1,C2,C3,C8,C4,C5,C9,C7,C6非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第70頁。非線性數(shù)據(jù)結(jié)構(gòu)71求拓?fù)渑判虻幕舅枷耄海?）從有向圖中選一個(gè)無前驅(qū)的頂點(diǎn)輸出；（2）將此頂點(diǎn)和以它為起點(diǎn)的弧刪除；（3）重復(fù)（1）、（2），直到不存在無前驅(qū)的頂點(diǎn)；（4）若此時(shí)輸出的頂點(diǎn)數(shù)小于有向圖中的頂點(diǎn)數(shù)，則說明有向圖中存在回路，否則輸出的頂點(diǎn)的順序即為一個(gè)拓?fù)湫蛄小?/p>

例如圖7.22所示的AOV－網(wǎng)，其拓?fù)湫蛄袨椋簐1,v6,v4,v3,v2,v5或v1,v3,v2,v6,v4,v5非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第71頁。非線性數(shù)據(jù)結(jié)構(gòu)72

V1

V6

V2

V4

V3

V5圖7.22AOV-網(wǎng)v1,v6,v4,v3,v2,v5v1,v3,v2,v6,v4,v5分析其執(zhí)行過程非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第72頁。非線性數(shù)據(jù)結(jié)構(gòu)73abcghdfeabhcdgfe課堂練習(xí)：求出上圖的一個(gè)拓?fù)湫蛄?。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第73頁。非線性數(shù)據(jù)結(jié)構(gòu)742、關(guān)鍵路徑AOE-網(wǎng)：在有向圖中，用頂點(diǎn)表示事件，用弧表示活動(dòng)，弧的權(quán)值表示活動(dòng)所需要的時(shí)間。我們把用這種方法構(gòu)造的有向無環(huán)圖叫做邊表示活動(dòng)的網(wǎng)（ActivityOnEdgeNetwork）,簡稱AOE-網(wǎng)。

AOE-網(wǎng)用在工程計(jì)劃和管理中，人們最關(guān)心的是：哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？至少需要多長時(shí)間能完成整個(gè)工程？非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第74頁。非線性數(shù)據(jù)結(jié)構(gòu)75源點(diǎn)：存在唯一的、入度為零的頂點(diǎn)，叫源點(diǎn)。匯點(diǎn)：存在唯一的、出度為零的頂點(diǎn)，叫匯點(diǎn)。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長路徑的長度即為完成整個(gè)工程任務(wù)所需的時(shí)間，該路徑叫做關(guān)鍵路徑。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)叫做關(guān)鍵活動(dòng)。

在AOE-網(wǎng)中的基本概念：如圖7.24所示的AOE-網(wǎng)。v0為源點(diǎn)，表示整個(gè)工程可以開始，v8為匯點(diǎn)，表示整個(gè)工程結(jié)束。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第75頁。非線性數(shù)據(jù)結(jié)構(gòu)76410235678a1=6a2=4a3=5a5=1a6=2a9=4a4=1a10=2a11=4a8=7a7=9圖7.24AOE-網(wǎng)v0為源點(diǎn)v8為匯點(diǎn)非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第76頁。非線性數(shù)據(jù)結(jié)構(gòu)77abcdefghk64521187244例如:整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長路徑。源點(diǎn)匯點(diǎn)6174非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第77頁。非線性數(shù)據(jù)結(jié)構(gòu)78幾個(gè)重要的定義：事件vi的最早發(fā)生時(shí)間ve(i)：從源點(diǎn)到頂點(diǎn)vi的最長路徑的長度，叫做事件vi的最早發(fā)生時(shí)間。求ve(i)時(shí)可從源點(diǎn)開始，按拓?fù)漤樞蛳騾R點(diǎn)遞推：ve(0)=0；

ve(i)=Max{ve(k)＋dut(<k,i>)}<k,i>∈T,1≤i≤n-1;其中，T為所有以i為頭的弧<k,i>的集合，dut（<k,i>）表示與弧<k,i>對應(yīng)的活動(dòng)的持續(xù)時(shí)間。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第78頁。非線性數(shù)據(jù)結(jié)構(gòu)79事件vi的最晚發(fā)生時(shí)間vl(i)：在保證匯點(diǎn)按其最早發(fā)生時(shí)間發(fā)生這一前提下，事件vi的最晚發(fā)生時(shí)間。在求出ve(i)的基礎(chǔ)上，可從匯點(diǎn)開始，按逆拓?fù)漤樞蛳蛟袋c(diǎn)遞推，求出vl(i)：vl(n-1)=ve(n-1)；

vl(i)=Min{vl(k)＋dut(<i,k>)}<i,k>∈S,0≤i≤n-2;其中，S為所有以i為尾的弧<i,k>的集合，dut（<i,k>）表示與弧<i,k>對應(yīng)的活動(dòng)的持續(xù)時(shí)間。

非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第79頁。非線性數(shù)據(jù)結(jié)構(gòu)80活動(dòng)ai的最早開始時(shí)間e(i)：如果活動(dòng)ai對應(yīng)的弧為<j,k>，則e(i)等于從源點(diǎn)到頂點(diǎn)j的最長路徑的長度，即：e(i)=ve(j)

活動(dòng)ai的最晚開始時(shí)間l(i)：如果活動(dòng)ai對應(yīng)的弧為<j,k>，其持續(xù)時(shí)間為dut（<j,k>）則有：l(i)=vl(k)-dut（<j,k>）

活動(dòng)ai的松弛時(shí)間（時(shí)間余量）：ai的最晚開始時(shí)間與ai的最早開始時(shí)間之差：l(i)-e(i)。顯然，松弛時(shí)間（時(shí)間余量）為0的活動(dòng)為關(guān)鍵活動(dòng)。

非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第80頁。非線性數(shù)據(jù)結(jié)構(gòu)81求關(guān)鍵路徑的基本步驟：（1）對圖中頂點(diǎn)進(jìn)行拓?fù)渑判?，在排序過程中按拓?fù)湫蛄星蟪雒總€(gè)事件的最早發(fā)生時(shí)間ve(i)；（2）按逆拓?fù)湫蛄星竺總€(gè)事件的最晚發(fā)生時(shí)間vl(i)；（3）求出每個(gè)活動(dòng)ai的最早開始時(shí)間e(i)和最晚發(fā)生時(shí)間l(i)；

(4)找出e(i)=l(i)的活動(dòng)ai，即為關(guān)鍵活動(dòng)。

注意喲非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第81頁。非線性數(shù)據(jù)結(jié)構(gòu)82圖7.24非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第82頁。非線性數(shù)據(jù)結(jié)構(gòu)83計(jì)算結(jié)果非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第83頁。非線性數(shù)據(jù)結(jié)構(gòu)84

0

1

4

8

6

7a1a7a8a11a10a4圖7.25關(guān)鍵路徑課后作業(yè)：教材245頁第3題非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第84頁。非線性數(shù)據(jù)結(jié)構(gòu)858.6最短路徑1.基本概念路徑長度:一條路徑上所經(jīng)過的邊的數(shù)目帶權(quán)路徑長度:路徑上所經(jīng)過邊的權(quán)值之和最短路徑:(帶權(quán))路徑長度(值)最小的那條路徑最短路徑長度或最短距離:其(帶權(quán))路徑長度

圖8-13（a）有向帶權(quán)圖；（b）鄰接矩陣EFDBCA825301810715úúúúúúúú?ùêêêêêêêê?é￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥￥0181004070158023050(a)(b)4非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第85頁。非線性數(shù)據(jù)結(jié)構(gòu)862.從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑一、狄克斯特拉算法思想按路徑長度遞增的順序逐步產(chǎn)生最短路徑，狄克斯特拉算法的思想是：設(shè)置兩個(gè)頂點(diǎn)的集合S和T，集合S中存放已找到最短路徑的頂點(diǎn)，集合T中存放當(dāng)前還未找到最短路徑的頂點(diǎn)。初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)，設(shè)為v0，然后從集合T中選擇到源點(diǎn)v0路徑長度最短的頂點(diǎn)u加入到集合S中，集合S中每加入一個(gè)新的頂點(diǎn)u都要修改源點(diǎn)v0到集合T中剩余頂點(diǎn)的當(dāng)前最短路徑長度值，集合T中各頂點(diǎn)的新的當(dāng)前最短路徑長度值，為原來的當(dāng)前最短路徑長度值與從源點(diǎn)過頂點(diǎn)u到達(dá)該頂點(diǎn)的路徑長度中的較小者。此過程不斷重復(fù)，直到集合T中的頂點(diǎn)全部加入到集合S中為止。非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第86頁。非線性數(shù)據(jù)結(jié)構(gòu)87EFDBCA51810715EFDBCA530(a)EFDBCA530715EFDBCA5301810715EFDBCA851810715EFDBCA8510715(b)(c)(d)(e)(f)狄克斯特拉算法求從頂點(diǎn)A到其余各頂點(diǎn)最短路徑的過程非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第87頁。非線性數(shù)據(jù)結(jié)構(gòu)88源點(diǎn)終點(diǎn)最短路徑路徑長度V0V2V0，V210V3V0，V2，V325V1

V0，V2，V3，V145V4V0，V445V5無最短路徑表7.3v0到其他頂點(diǎn)的最短路徑V150

20

1010

30V0V4V2V3V545

15

353

15

20非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第88頁。非線性數(shù)據(jù)結(jié)構(gòu)89二、狄克斯特拉函數(shù)設(shè)計(jì)參數(shù)設(shè)計(jì)：函數(shù)共有4個(gè)參數(shù)，其中2個(gè)為輸入?yún)?shù)，分別為帶權(quán)圖G和源點(diǎn)序號(hào)v0；2個(gè)為輸出參數(shù)，分別為distance[]和path[]，distance[]用來存放得到的從源點(diǎn)v0到其余各頂點(diǎn)的最短距離數(shù)值，path[]用來存放得到的從源點(diǎn)v0到其余各頂點(diǎn)的最短路徑上到達(dá)目標(biāo)頂點(diǎn)的前一頂點(diǎn)下標(biāo)。狄克斯特拉函數(shù)設(shè)計(jì)：voidDijkstra(AdjMWGraph&G,intv0,intdistance[],intpath[])//帶權(quán)圖G從下標(biāo)v0頂點(diǎn)到其他頂點(diǎn)的最短距離distance//和相應(yīng)的目標(biāo)頂點(diǎn)的前一頂點(diǎn)下標(biāo)path{ intn=G.NumOfVertices(); int*s=newint[n]; //s用來存放n個(gè)頂點(diǎn)的標(biāo)記

intminDis,i,j,u;非線性數(shù)據(jù)結(jié)構(gòu)全文共98頁，當(dāng)前為第89頁。非線性數(shù)據(jù)結(jié)構(gòu)90

//初始化

for(i=0;i<n;i++) { distance[i]=G.GetWeight(v0,i); s[i]=0; //初始均標(biāo)記為0

if(i!=v0&&distance[i]<MaxWeight)path[i]=v0; //初始的目標(biāo)頂點(diǎn)的前一頂點(diǎn)均