數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版）（微課版）第6章 圖

第6章圖教學(xué)要求相關(guān)知識(shí)點(diǎn)圖的常用術(shù)語(yǔ)：有向圖、無(wú)向圖、完全圖、有向完全圖、稀疏圖、稠密圖、網(wǎng)、鄰接點(diǎn)、路徑、簡(jiǎn)單路徑、回路或環(huán)、簡(jiǎn)單回路、連通、連通圖、強(qiáng)連通圖、生成樹(shù)圖的鄰接矩陣存儲(chǔ)表示圖的鄰接表存儲(chǔ)表示圖的深度優(yōu)先遍歷(Depth-FirstSearch,DFS)圖的廣度優(yōu)先遍歷(Breadth-FirstSearch,BFS)最小生成樹(shù)拓?fù)渑判蚝完P(guān)鍵路徑最短路徑教學(xué)要求學(xué)習(xí)重點(diǎn)圖的存儲(chǔ)與操作圖的遍歷、最小生成樹(shù)、最短路徑算法目錄圖的存儲(chǔ)與操作圖的遍歷圖與最小生成樹(shù)3圖的定義和基本術(shù)語(yǔ)124最短路徑5AOV網(wǎng)與拓?fù)渑判駻OE網(wǎng)與關(guān)鍵路徑本章小結(jié)7686.1圖的定義和基本術(shù)語(yǔ)6.1圖的定義和基本術(shù)語(yǔ)圖的定義及基本術(shù)語(yǔ)1.圖的定義在圖中的數(shù)據(jù)元素通常稱(chēng)為頂點(diǎn)，圖G(Graph)是由頂點(diǎn)集合(vertex)及頂點(diǎn)之間的關(guān)系集合（稱(chēng)為邊或?。┙M成的一種數(shù)據(jù)結(jié)構(gòu)。記為G=(V,E)。2.圖的基本術(shù)語(yǔ)(1)無(wú)向邊如果頂點(diǎn)vi和vj間的邊沒(méi)有方向，則稱(chēng)該邊為無(wú)向邊(Edge)。用無(wú)序偶對(duì)表示：(vi，vj)。6.1圖的定義和基本術(shù)語(yǔ)(2)有向邊(弧)如果頂點(diǎn)vi和vj間的邊有方向，則稱(chēng)該邊為有向邊(或稱(chēng)為弧Arc)。用有序偶對(duì)表示：<vi，vj>。(3)無(wú)向圖在一個(gè)圖G中，任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)(vi，vj)∈E都是無(wú)序的，即兩點(diǎn)相連形成的邊都是沒(méi)有方向的，則稱(chēng)該圖為無(wú)向圖(Undigraph)。圖6.1(a)所示是一個(gè)無(wú)向圖G1。圖6.1(a)無(wú)向圖G1

6.1圖的定義和基本術(shù)語(yǔ)(4)有向圖在一個(gè)圖G中，任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)(vi，vj)∈E都是有序的，即兩點(diǎn)相連形成的邊都是有方向的，則稱(chēng)該圖為有向圖(Digraph)。如圖6.1(b)所示是一個(gè)有向圖G2，在該圖中，G2=(V2,E2)，V2={v1,v2,v3}，E2={<v1,v2>,<v2,v1>,<v2,v3>,<v1,v3>}。圖6.1(b)有向圖G26.1圖的定義和基本術(shù)語(yǔ)(5)弧頭、弧尾在無(wú)向圖中，任意兩個(gè)頂點(diǎn)之間的連線(xiàn)稱(chēng)為邊，并且不區(qū)分首尾；在有向圖中，任意兩個(gè)頂點(diǎn)之間的連線(xiàn)稱(chēng)為弧，并且，有向圖的弧需區(qū)分弧頭和弧尾。例如：將頂點(diǎn)vi和vj之間的連線(xiàn)記為有序偶對(duì)<vi，vj>，其中頂點(diǎn)vi稱(chēng)為初始點(diǎn)(弧尾Tail)，即弧的射出端，就是不帶箭頭的一端。頂點(diǎn)vj稱(chēng)為終端點(diǎn)(或弧頭Head)，即弧的射入端，就是帶著箭頭的一端。6.1圖的定義和基本術(shù)語(yǔ)(6)權(quán)、網(wǎng)在邊或者弧上的數(shù)據(jù)信息稱(chēng)為邊的權(quán)(Weight)。權(quán)值可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離、時(shí)間或者價(jià)格等。帶權(quán)的圖稱(chēng)為網(wǎng)(Network)。

圖6.2(a)無(wú)向網(wǎng)G3圖6.2(b)有向網(wǎng)G4。6.1圖的定義和基本術(shù)語(yǔ)(7)完全圖如果無(wú)向圖中任意兩個(gè)頂點(diǎn)間都存在邊，則稱(chēng)之為無(wú)向完全圖(CompletedGraph)。在一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向完全圖中，邊數(shù)為n(n-1)/2條。如果有向圖中任意兩個(gè)頂點(diǎn)間都存在方向互為相反的兩條弧，則稱(chēng)之為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，邊數(shù)為n(n-1)條。(8)稠密圖、稀疏圖當(dāng)一個(gè)圖接近完全圖時(shí)，稱(chēng)之為稠密圖(DenseGraph)；相反地，當(dāng)一個(gè)圖中含有較少的邊或弧時(shí)，則稱(chēng)之為稀疏圖(SparseGraph)。6.1圖的定義和基本術(shù)語(yǔ)(9)子圖若有兩個(gè)圖G1和G2，其中，G1=(V1,E1)，G2=(V2,E2)，且滿(mǎn)足如下條件：V2?V1，E2?E1即V2為V1的子集，E2為E1的子集，則稱(chēng)圖G2為圖G1的子圖。6.1圖的定義和基本術(shù)語(yǔ)(10)鄰接點(diǎn)和度對(duì)于無(wú)向圖，假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱(chēng)頂點(diǎn)v和w互為鄰接點(diǎn)；和頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目定義為v的度。記為ID(v)。無(wú)向圖不區(qū)分入度和出度。對(duì)于有向圖，由于弧有方向性，則有入度和出度之分。頂點(diǎn)的出度(OutDegree)是以頂點(diǎn)v為弧尾的弧的數(shù)目，記為OD(v)；頂點(diǎn)的入度(InDegree)是以頂點(diǎn)v為弧頭的弧的數(shù)目，記為ID(v)；頂點(diǎn)的度記為T(mén)D(v)，有TD(v)=OD(v)+ID(v)。6.1圖的定義和基本術(shù)語(yǔ)(11)路徑、路徑長(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ù)目。(12)簡(jiǎn)單路徑、回路、簡(jiǎn)單回路頂點(diǎn)序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑，稱(chēng)為簡(jiǎn)單路徑；若頂點(diǎn)序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則稱(chēng)該路徑為回路或環(huán)(Cycle)；若頂點(diǎn)序列中除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)，則稱(chēng)該回路為簡(jiǎn)單回路或者簡(jiǎn)單環(huán)。6.1圖的定義和基本術(shù)語(yǔ)(13)連通圖、連通分量無(wú)向圖G中，如果從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱(chēng)頂點(diǎn)vi和vj是連通的。如果對(duì)于圖中任意兩個(gè)頂點(diǎn)vi、vj∈V，vi和vj都是連通的，則稱(chēng)圖G為連通圖(ConnectedGraph)。在無(wú)向圖中，在滿(mǎn)足連通條件時(shí)，盡可能多地包含原圖中的頂點(diǎn)和這些頂點(diǎn)之間的邊的連通子圖稱(chēng)為該圖的連通分量(ConnectedComponent)；連通圖的連通分量是它本身，非連通圖的連通分量可能為多個(gè)。6.1圖的定義和基本術(shù)語(yǔ)例如：圖6.3中的G5就是一個(gè)連通圖。而G6就是非連通圖，但有2個(gè)連通分量，如圖6.4所示。6.3連通圖G5圖6.4非連通圖G6及兩個(gè)連通分量6.1圖的定義和基本術(shù)語(yǔ)(14)強(qiáng)連通圖、強(qiáng)連通分量有向圖G中，如果從vi到vj有路徑，則稱(chēng)頂點(diǎn)vi和頂點(diǎn)vj是連通的；若圖中任意兩個(gè)頂點(diǎn)之間都存在兩條互為反方向的路徑，即從vi到vj及從vj到vi都有路徑，則稱(chēng)此有向圖為強(qiáng)連通圖。有向圖中的極大連通子圖稱(chēng)作該有向圖的強(qiáng)連通分量。6.1圖的定義和基本術(shù)語(yǔ)例如，圖6.5中的G7就是一個(gè)強(qiáng)連通圖。而G8就是非強(qiáng)連通圖，但有2個(gè)強(qiáng)連通分量，如圖6.6所示。圖6.6非強(qiáng)連通圖G8及兩個(gè)連通分量圖6.5強(qiáng)連通圖G76.1圖的定義和基本術(shù)語(yǔ)(15)生成樹(shù)連通圖G的生成樹(shù)，是包含G的全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖，該極小連通子圖有(n-1)條邊。如圖6.7所示，是連通圖G5的生成樹(shù)。如果在一棵生成樹(shù)上添加一條邊，必定構(gòu)成一個(gè)環(huán)，因?yàn)檫@條邊的出現(xiàn)使得它依附的那兩個(gè)頂點(diǎn)之間有了第二條路徑。一棵有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有(n-1)條邊。如果一個(gè)圖有n個(gè)頂點(diǎn)和小于(n-1)條邊，則是非連通圖。如果它多于(n-1)條邊，則一定有環(huán)。但需要大家注意的是，有(n-1)條邊的圖不一定是生成樹(shù)。6.1圖的定義和基本術(shù)語(yǔ)(16)生成森林如果一個(gè)有向圖有且僅有一個(gè)頂點(diǎn)的入度為0，其他頂點(diǎn)的入度均為1，則這個(gè)圖是一棵有向樹(shù)。當(dāng)一個(gè)有向圖有多個(gè)頂點(diǎn)的入度為0時(shí)，它的生成森林則由多棵有向樹(shù)構(gòu)成。這個(gè)生成森林含有圖中全部的頂點(diǎn)和相應(yīng)的弧。如圖6.8所示是有向圖G9及其生成森林。6.1圖的定義和基本術(shù)語(yǔ)連通圖G5及生成樹(shù)有向圖G9及生成森林6.2圖的存儲(chǔ)與操作6.2圖的存儲(chǔ)與操作鄰接矩陣鄰接矩陣（AdjacencyMatrix）是用兩個(gè)數(shù)組來(lái)表示圖，一個(gè)數(shù)組是一維數(shù)組，存儲(chǔ)圖中頂點(diǎn)的信息，另一個(gè)數(shù)組是二維數(shù)組，即矩陣，存儲(chǔ)頂點(diǎn)之間相鄰的信息，也就是邊（或弧）的信息。6.2圖的存儲(chǔ)與操作1.圖的鄰接矩陣存儲(chǔ)法無(wú)向圖G5的鄰接矩陣6.2圖的存儲(chǔ)與操作1.圖的鄰接矩陣存儲(chǔ)法有向圖G9的鄰接矩陣6.2圖的存儲(chǔ)與操作2.網(wǎng)的鄰接矩陣存儲(chǔ)法無(wú)向網(wǎng)的鄰接矩陣6.2圖的存儲(chǔ)與操作2.網(wǎng)的鄰接矩陣存儲(chǔ)法有向網(wǎng)的鄰接矩陣6.2圖的存儲(chǔ)與操作3.鄰接矩陣表示法的特點(diǎn)(1)因?yàn)闊o(wú)向圖的鄰接矩陣具有對(duì)稱(chēng)性，一定是一個(gè)對(duì)稱(chēng)矩陣，所以可以采取壓縮存儲(chǔ)的方式只存儲(chǔ)矩陣的上三角(或下三角)矩陣元素。(2)無(wú)向圖(網(wǎng))的鄰接矩陣的第i行(或第i列)非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度TD(vi)。(3)有向圖(網(wǎng))的鄰接矩陣的第i行非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度OD(vi)。(4)有向圖(網(wǎng))的鄰接矩陣的第i列非零元素(或非∞元素)的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的入度ID(vi)。6.2圖的存儲(chǔ)與操作4.鄰接矩陣表示法的優(yōu)缺點(diǎn)用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連（鄰接），但要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè)，所花費(fèi)的時(shí)間代價(jià)很大，同時(shí)，鄰接矩陣存儲(chǔ)空間為O(n2)，所以適用于稠密圖。6.2圖的存儲(chǔ)與操作5.圖的鄰接矩陣存儲(chǔ)定義/*圖的鄰接矩陣存儲(chǔ)*/#defineMAXSIZE10typedefcharElemType;/*定義頂點(diǎn)數(shù)據(jù)類(lèi)型*/typedefstruct{ElemTypeV[MAXSIZE];/*頂點(diǎn)信息*/

intarcs[MAXSIZE][MAXSIZE];//鄰接矩陣

inte;/*邊數(shù)*/

intn;/*頂點(diǎn)數(shù)*/}Graph;/*圖的鄰接矩陣數(shù)據(jù)類(lèi)型*/6.2圖的存儲(chǔ)與操作6.鄰接矩陣操作(1)在圖中查找頂點(diǎn)在圖G中查找頂點(diǎn)v，找到返回其在頂點(diǎn)數(shù)組中的索引號(hào)；若不存在，返回-1intLocateVex(GraphG,ElemTypev){inti;

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

if(G.V[i]==v)returni;

return-1;}6.2圖的存儲(chǔ)與操作(2)在屏幕上顯示圖G的鄰接矩陣表示算法6.2在屏幕上顯示圖G的鄰接矩陣表示voidDisplayAdjMatrix(GraphG){inti,j;

printf("圖的鄰接矩陣表示：\n");

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

{for(j=0;j<G.n;j++) printf("%3d",G.arcs[i][j]);

printf("\n");

}}6.2圖的存儲(chǔ)與操作(3)無(wú)向圖/無(wú)向網(wǎng)/有向圖/有向網(wǎng)的鄰接矩陣的建立算法6.3創(chuàng)建無(wú)向圖/無(wú)向網(wǎng)/有向圖/有向網(wǎng)的鄰接矩陣voidCreateUndirectedGraphAdj(Graph*pg){

inti,j,k;

ElemTypev1,v2;

for(k=0;k<pg->e;k++)/*邊數(shù)e*/

{scanf("%c%c",&v1,&v2);/*輸入一條邊的兩個(gè)端點(diǎn)(圖)*/

scanf("%c%c%d",&v1,&v2,&w);/*輸入一條邊的兩個(gè)頂點(diǎn)及邊的權(quán)(網(wǎng))*/6.2圖的存儲(chǔ)與操作/*確定兩個(gè)頂點(diǎn)在圖G中的位置*/

i=LocateVex(*pg,v1);j=LocateVex(*pg,v2);/*創(chuàng)建鄰接矩陣*/if(i>=0&&j>=0){pg->arcs[i][j]=1;pg->arcs[j][i]=1;/*創(chuàng)建無(wú)向圖的鄰接矩陣*/

pg->arcs[i][j]=w;pg->arcs[j][i]=w;/*創(chuàng)建無(wú)向網(wǎng)的鄰接矩陣*/

pg->arcs[i][j]=1;/*創(chuàng)建有向圖的鄰接矩陣*/

pg->arcs[i][j]=w;/*創(chuàng)建有向網(wǎng)的鄰接矩陣*/}

}}6.2圖的存儲(chǔ)與操作鄰接表1.圖的鄰接表存儲(chǔ)法鄰接表(AdjacencyList)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法；對(duì)于圖G中的每個(gè)頂點(diǎn)Vi，將所有鄰接于Vi的頂點(diǎn)Vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱(chēng)為頂點(diǎn)Vi的鄰接表；再將所有頂點(diǎn)的鄰接表表頭放到數(shù)組中。6.2圖的存儲(chǔ)與操作在鄰接表表示中，包括兩種結(jié)點(diǎn)結(jié)構(gòu)。

(1)頭節(jié)點(diǎn)：由2個(gè)域構(gòu)成。頂點(diǎn)域vex標(biāo)記頂點(diǎn)vi的信息，鏈域(firstarc)標(biāo)記第一個(gè)鄰接節(jié)點(diǎn)。

(2)表節(jié)點(diǎn)：由3個(gè)域構(gòu)成，鄰接點(diǎn)域(adjvex)標(biāo)記與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置，鏈域(nextarc)標(biāo)記下一個(gè)與vi鄰接的節(jié)點(diǎn)，數(shù)據(jù)域data標(biāo)記和邊(或弧)的相關(guān)信息，例如權(quán)值等。vexfirstarcadjvexnextarcdata圖6.11鄰接表的節(jié)點(diǎn)結(jié)構(gòu)6.2圖的存儲(chǔ)與操作2.圖的逆鄰接表存儲(chǔ)法有向圖的鄰接表不方便查找以vi為弧頭的節(jié)點(diǎn)數(shù)逆鄰接表為每一個(gè)頂點(diǎn)建立一個(gè)以vi為弧頭的表。無(wú)向圖G1的鄰接表(a)無(wú)向圖G1的鄰接表僅以頂點(diǎn)編號(hào)作為信息輸入，時(shí)間復(fù)雜度為O(n+e)。6.2圖的存儲(chǔ)與操作2.圖的逆鄰接表存儲(chǔ)法有向圖G2的鄰接表和逆鄰接表(b)有向圖G2的鄰接表(c)有向圖G2的逆鄰接表僅以頂點(diǎn)編號(hào)作為信息輸入，時(shí)間復(fù)雜度為O(n+e)。6.2圖的存儲(chǔ)與操作3.無(wú)向圖的鄰接表存儲(chǔ)法的特點(diǎn)（1）第i個(gè)鏈表中結(jié)點(diǎn)的數(shù)目為第i個(gè)頂點(diǎn)的度。（2）所有鏈表中結(jié)點(diǎn)的數(shù)目的一半為圖中邊的數(shù)目。（3）占用的存儲(chǔ)單元數(shù)目為n＋2e。（n為頂點(diǎn)數(shù)，e為邊數(shù)）

4.有向圖的鄰接表存儲(chǔ)法的性質(zhì)（1）鄰接表中，第i個(gè)鏈表中結(jié)點(diǎn)的數(shù)目為頂點(diǎn)i的出度。逆鄰接表中，第i個(gè)鏈表中結(jié)點(diǎn)的數(shù)目為頂點(diǎn)i的入度。（2）所有鏈表中結(jié)點(diǎn)的數(shù)目為圖中弧的數(shù)目。（3）占用的存儲(chǔ)單元數(shù)為n＋e。（n為頂點(diǎn)數(shù)，e為弧數(shù)）6.2圖的存儲(chǔ)與操作5.鄰接表存儲(chǔ)法的優(yōu)缺點(diǎn)在鄰接表中可以快速找到某一頂點(diǎn)的鄰接點(diǎn)，但是要確定任意兩個(gè)頂點(diǎn)(vi和vj)間是否有邊(或弧)，就必須搜索第i個(gè)或者第j個(gè)鏈表，在這個(gè)方面遠(yuǎn)不及鄰接矩陣快捷。6.2圖的存儲(chǔ)與操作6.圖的鄰接表存儲(chǔ)定義#defineMAXSIZE10typedefcharElemType;/*定義頂點(diǎn)類(lèi)型為char*//*邊節(jié)點(diǎn)的類(lèi)型定義*/typedefstructArcNode{intadjVex;

structArcNode*nextArc;

intweight;}ArcNode;6.2圖的存儲(chǔ)與操作/*頂點(diǎn)節(jié)點(diǎn)的類(lèi)型定義*/typedefstructVNode{ElemTypedata;

ArcNode*firstArc;}VNode;/*圖的鄰接表數(shù)據(jù)類(lèi)型*/typedefstruct{VNodeadjList[MAXSIZE];

intn,e;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/}ALGraph;6.2圖的存儲(chǔ)與操作7.鄰接表操作(1)在圖G中查找頂點(diǎn)在圖G中查找頂點(diǎn)v，找到后返回其在頂點(diǎn)數(shù)組中的索引號(hào)；若不存在，返回-1intLocateVex(ALGraphG,ElemTypev){inti;

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

if(G.adjList[i].data==v)returni;

return-1;}6.2圖的存儲(chǔ)與操作(2)無(wú)向圖的鄰接表/有向圖的鄰接表/逆鄰接表的建立voidCreateUndirectedGraphLink(ALGraph*pg){inti,j,k;

ElemTypev1,v2;

ArcNode*s;

for(i=0;i<=pg->n;i++) /*n為頂點(diǎn)數(shù)*/

{scanf("%c",&pg->adjList[i].data); /*構(gòu)造頂點(diǎn)信息*/

pg->adjList[i].firstArc=NULL;}

6.2圖的存儲(chǔ)與操作

for(k=0;k<pg->e;k++) /*e為邊數(shù)*/

{scanf("%c%c",&v1,&v2);/*確定兩個(gè)頂點(diǎn)在圖G中的位置*/

i=LocateVex(*pg,v1);j=LocateVex(*pg,v2);

if(i>=0&&j>=0)

{

/*創(chuàng)建無(wú)向圖的鄰接表*/

6.2圖的存儲(chǔ)與操作

s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=j;s->nextArc=pg->adjList[i].firstArc;pg->adjList[i].firstArc=s;//頭插法s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=i;

s->nextArc=pg->adjList[j].firstArc;pg->adjList[j].firstArc=s;//頭插法6.2圖的存儲(chǔ)與操作

/*創(chuàng)建有向圖的鄰接表*/

s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=j;

s->nextArc=pg->adjList[i].firstArc;pg->adjList[i].firstArc=s;//頭插法6.2圖的存儲(chǔ)與操作

/*創(chuàng)建有向圖的逆鄰接表*/

s=(ArcNode*)malloc(sizeof(ArcNode));s->adjVex=i;

s->nextArc=pg->adjList[j].firstArc;pg->adjList[j].firstArc=s;//頭插法

}}}6.2圖的存儲(chǔ)與操作(3)在屏幕上顯示圖G的鄰接表表示voidDisplayAdjList(ALGraphG){inti;ArcNode*p;printf("圖的鄰接表表示：");

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

{printf("\n%4c",G.adjList[i].data);

p=G.adjList[i].firstArc;

while(p!=NULL){printf("->%d",p->adjVex);

p=p->nextArc;}

}

printf("\n");}6.3圖的遍歷6.3圖的遍歷圖的遍歷：從圖中的任意頂點(diǎn)出發(fā)，訪(fǎng)問(wèn)其余頂點(diǎn)，并且保證所有頂點(diǎn)都被訪(fǎng)問(wèn)且只被訪(fǎng)問(wèn)一次，稱(chēng)此過(guò)程為圖的遍歷(TraversingGraph)。判斷圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵路徑都以圖的遍歷為基礎(chǔ)。圖的遍歷過(guò)程中應(yīng)該注意以下問(wèn)題：(1)如何選取起始節(jié)點(diǎn)。在無(wú)向圖中，我們可以任意選取起始節(jié)點(diǎn)。在有向圖中，我們應(yīng)當(dāng)盡量選取入度為0的節(jié)點(diǎn)作為起始節(jié)點(diǎn)。(2)當(dāng)遍歷的圖是非連通圖時(shí)，從一個(gè)節(jié)點(diǎn)出發(fā)只能訪(fǎng)問(wèn)它所在的連通分量上的所有節(jié)點(diǎn)，并不能訪(fǎng)問(wèn)圖的所有節(jié)點(diǎn)。遍歷還需考慮不同連通分量的起始節(jié)點(diǎn)的選取問(wèn)題。6.3圖的遍歷(3)圖中的一個(gè)節(jié)點(diǎn)可能和多個(gè)節(jié)點(diǎn)相鄰接，我們?nèi)绾芜x取下一個(gè)鄰接點(diǎn)。(4)無(wú)向圖和有向圖中都有可能存在回路，那么在一個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)之后有可能因?yàn)榛芈返拇嬖诙俅伪辉L(fǎng)問(wèn)，我們?nèi)绾伪苊庖粋€(gè)節(jié)點(diǎn)被多次訪(fǎng)問(wèn)。6.3圖的遍歷深度優(yōu)先遍歷算法1.圖的深度優(yōu)先（DFS）遍歷深度優(yōu)先遍歷(depth-firstsearch，DFS)類(lèi)似于樹(shù)的先根遍歷，是樹(shù)的先根遍歷的推廣。假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪(fǎng)問(wèn)過(guò)，在G中任選頂點(diǎn)V為出發(fā)點(diǎn)（源點(diǎn)），則深度優(yōu)先搜索遍歷可定義為：（1）首先訪(fǎng)問(wèn)出發(fā)點(diǎn)V；（2）然后依次從V出發(fā)搜索V的每個(gè)鄰接點(diǎn)W，若W未曾訪(fǎng)問(wèn)過(guò)，則以W為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索遍歷，直至圖中所有和源點(diǎn)V有路徑相通的頂點(diǎn)（也稱(chēng)為從源點(diǎn)可達(dá)的頂點(diǎn)）均已被訪(fǎng)問(wèn)為止；6.3圖的遍歷（3）若此時(shí)圖中仍有未訪(fǎng)問(wèn)的頂點(diǎn)，則另選一個(gè)尚未訪(fǎng)問(wèn)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)均已被訪(fǎng)問(wèn)為止。這兩種深度優(yōu)先搜索遍歷序列為：v1v2v5v4v8v3v7v6v1v2v5v4v8v3v6v7從頂點(diǎn)V1出發(fā)的深度優(yōu)先搜索遍歷序列可能有多種，這里只給出其中的兩種，其它的可類(lèi)似分析。6.3圖的遍歷顯然，圖的深度優(yōu)先遍歷是一個(gè)遞歸的過(guò)程。可以定義一個(gè)訪(fǎng)問(wèn)標(biāo)記數(shù)組visited[0…n-1]，初始值均為false，一旦某個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)，立即對(duì)其相應(yīng)分量置true，由此可以區(qū)別圖中節(jié)點(diǎn)是否被訪(fǎng)問(wèn)過(guò)，并最終遍歷所有節(jié)點(diǎn)，同時(shí)避免了節(jié)點(diǎn)的重復(fù)訪(fǎng)問(wèn)。6.3圖的遍歷2.圖的深度優(yōu)先遍歷操作算法6.7從圖的某一節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索voidDFSTraverse(GraphG){intv;for(v=0;v<G.n;v++)visited[v]=0;/*初始化標(biāo)識(shí)數(shù)組*/for(v=0;v<G.n;v++)/*保證非連通圖的遍歷*//*從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/if(!visited[v])DFS(G,v);}6.3圖的遍歷算法6.8利用鄰接矩陣實(shí)現(xiàn)連通圖的深度優(yōu)先遍歷/*從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/voidDFS(GraphG,inti){intj;printf("%3c",G.V[i]);/*訪(fǎng)問(wèn)第i個(gè)頂點(diǎn)*/visited[i]=1;for(j=0;j<G.n;j++)

if((G.arcs[i][j]==1)&&(visited[j]==0))

DFS(G,j);//對(duì)i的尚未訪(fǎng)問(wèn)的鄰接點(diǎn)j遞歸調(diào)用DFS}6.3圖的遍歷算法6.9用鄰接表實(shí)現(xiàn)連通圖的深度優(yōu)先遍歷/*從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/voidDFS(ALGraphG,inti){ArcNode*p;printf(“%3c”,G.adjList[i].data);//訪(fǎng)問(wèn)頂點(diǎn)ivisited[i]=1;p=G.adjList[i].firstArc;while(p!=NULL){if(visited[p->adjVex]==0)//未訪(fǎng)問(wèn)的鄰接點(diǎn)DFS(G,p->adjVex);//遞歸調(diào)用DFSp=p->nextArc;}}6.3圖的遍歷廣度優(yōu)先遍歷算法1.圖的廣度優(yōu)先遍歷廣度優(yōu)先搜索(Breadth_FirstSearch)遍歷類(lèi)似于樹(shù)的按層次遍歷。設(shè)圖G的初態(tài)是所有的頂點(diǎn)均未訪(fǎng)問(wèn)過(guò)，在G中任選一頂點(diǎn)vi為源點(diǎn)，過(guò)程為：（1）首先訪(fǎng)問(wèn)出發(fā)點(diǎn)vi，并將其訪(fǎng)問(wèn)標(biāo)志置為已被訪(fǎng)問(wèn)，即visited[i]=true；（2）依次訪(fǎng)問(wèn)頂點(diǎn)vi的所有鄰接點(diǎn)w0，w1，……，wt；（3）再依次訪(fǎng)問(wèn)頂點(diǎn)w0，w1，……，wt的所有鄰接點(diǎn)。（4）如此類(lèi)推，直至圖中所有的頂點(diǎn)都被訪(fǎng)問(wèn)到。6.3圖的遍歷從頂點(diǎn)V1出發(fā)的廣度優(yōu)先搜索遍歷序列可能有多種，這里只給出其中的三種，其它的可類(lèi)似分析。這三種廣度優(yōu)先搜索遍歷序列為：v1，v2，v3，v4，v5，v6，v7，v8v1，v3，v2，v7，v6，v5，v4，v8v1，v2，v3，v5，v4，v7，v6，v86.3圖的遍歷2.圖的廣度優(yōu)先遍歷操作算法6.10對(duì)圖進(jìn)行廣度優(yōu)先遍歷voidBFSTraverse(GraphG){intv;for(v=0;v<G.n;v++)//初始化標(biāo)志數(shù)組

visited[v]=0;for(v=0;v<G.n;v++)//保證全圖的遍歷

if(!visited[v])BFS(G,v);//從第v個(gè)頂點(diǎn)出發(fā)遞歸地廣度優(yōu)先遍歷圖G}

6.3圖的遍歷算法6.11廣度優(yōu)先遍歷以鄰接矩陣存儲(chǔ)的圖//從第k個(gè)頂點(diǎn)出發(fā)廣度優(yōu)先遍歷圖G,G以鄰接矩陣表示voidBFS(GraphG,intk){inti,j; InitQueue(&Q);/*初始化隊(duì)列*/printf("%3c",G.V[k]);/*訪(fǎng)問(wèn)第k個(gè)頂點(diǎn)*/visited[k]=1;EnQueue(&Q,k);/*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/while(!QueueEmpty(&Q))/*隊(duì)列非空*/{DelQueue(&Q,&i);6.3圖的遍歷for(j=0;j<G.n;j++){if((G.arcs[i][j]==1)&&(visited[j]==0)){/*訪(fǎng)問(wèn)第i個(gè)頂點(diǎn)的末曾訪(fǎng)問(wèn)的頂點(diǎn)j*/printf("%3c",G.V[j]);visited[j]=1;EnQueue(&Q,j);/*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/}}}}6.3圖的遍歷算法6.12廣度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖voidBFS(ALGraphG,intk){inti;ArcNode*p;InitQueue(&Q);/*初始化隊(duì)列*/printf(“%3c”,G.adjList[k].data);//訪(fǎng)問(wèn)頂點(diǎn)kvisited[k]=1; EnQueue(&Q,k);/*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/while(!QueueEmpty(&Q))/*隊(duì)列非空*/

{

DelQueue(&Q,&i);p=G.adjList[i].firstArc;/*獲取第1個(gè)鄰接點(diǎn)*/6.3圖的遍歷while(p!=NULL){if(visited[p->adjVex]==0){/*訪(fǎng)問(wèn)第i個(gè)頂點(diǎn)的末曾訪(fǎng)問(wèn)的頂點(diǎn)*/printf("%3c",G.adjList[p->adjVex].data);visited[p->adjVex]=1;EnQueue(&Q,p->adjVexp=p->nextArc;}p=p->nextArc;}}}

6.4圖與最小生成樹(shù)6.4圖與最小生成樹(shù)生成樹(shù)和森林的概念在一個(gè)有n個(gè)頂點(diǎn)的連通圖G中，存在一個(gè)極小的連通子圖G’，G’包含圖G的所有頂點(diǎn)，但只有n-1條邊，并且G’是連通的，稱(chēng)G’為G的生成樹(shù)。6.4圖與最小生成樹(shù)由深度優(yōu)先搜索得到的生成樹(shù)稱(chēng)為深度優(yōu)先生成樹(shù)，簡(jiǎn)稱(chēng)為DFS生成樹(shù)；由廣度優(yōu)先搜索得到的生成樹(shù)稱(chēng)為廣度優(yōu)先生成樹(shù)，簡(jiǎn)稱(chēng)為BFS生成樹(shù)。無(wú)向圖G11的兩種生成樹(shù)無(wú)向圖G11深度優(yōu)先生成樹(shù)廣度優(yōu)先生成樹(shù)6.4圖與最小生成樹(shù)若一個(gè)圖是非連通圖或非強(qiáng)連通圖，但有若干個(gè)連通分量或若干個(gè)強(qiáng)連通分量，則通過(guò)深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，不能得到生成樹(shù)，但可以得到生成森林，且若非連通圖有n個(gè)頂點(diǎn)，m個(gè)連通分量或強(qiáng)連通分量，則可以遍歷得到m棵生成樹(shù)，合起來(lái)為生成森林，森林中包含n-m條樹(shù)邊。6.4圖與最小生成樹(shù)最小生成樹(shù)無(wú)向連通帶權(quán)圖G的權(quán)為生成樹(shù)T中各邊的權(quán)值總和；邊的權(quán)值總和最小的生成樹(shù)，稱(chēng)為最小代價(jià)生成樹(shù)(MinimumcostSpanningTree，MST)。構(gòu)造最小生成樹(shù)的準(zhǔn)則如下：(1)必須只使用該網(wǎng)中的邊來(lái)構(gòu)造最小生成樹(shù)；(2)必須使用且僅使用n-1條邊來(lái)連接網(wǎng)中的n個(gè)頂點(diǎn)；(3)不能使用產(chǎn)生回路的邊。6.4圖與最小生成樹(shù)最小生成樹(shù)在帶權(quán)的連通無(wú)向圖G=(V,E)上，構(gòu)造最小生成樹(shù)有普里姆算法和克魯斯卡爾算法，它們都是應(yīng)用最小生成樹(shù)MST的性質(zhì)：U是頂點(diǎn)V的一個(gè)非空子集，若(u,v)是一條具有最小權(quán)值的邊，其中u∈U,v∈V?U，則一定存在一棵包含邊(u,v)的最小生成樹(shù)。6.4圖與最小生成樹(shù)1.通過(guò)普里姆算法生成最小生成樹(shù)(1)普里姆(Prim)算法的基本思想設(shè)G=(V,E)是帶權(quán)圖，V是圖G的頂點(diǎn)集，E是邊集。①在圖中任取一個(gè)頂點(diǎn)k作為開(kāi)始點(diǎn)，令U={k}，W=V-U，TE={ф}，其中W為圖中剩余頂點(diǎn)的集合。②在由一個(gè)頂點(diǎn)在U中，另一個(gè)頂點(diǎn)在W中的兩個(gè)頂點(diǎn)構(gòu)成的所有邊中，找出一條權(quán)值最小的邊(u，v)(u∈U，v∈W)，將該邊作為最小生成樹(shù)的樹(shù)邊放入TE，并將頂點(diǎn)v加入集合U中，并從W中刪去這個(gè)頂點(diǎn)。③重復(fù)②，直到W為空集為止。此時(shí)TE中有n-1條邊，此時(shí)T=(U,TE)就是G的一棵最小生成樹(shù)。6.4圖與最小生成樹(shù)普里姆算法是從最小生成樹(shù)中頂點(diǎn)的角度出發(fā)來(lái)考慮的，因?yàn)閳D中有n個(gè)頂點(diǎn)，按照生成樹(shù)的定義，所有的頂點(diǎn)都必須加入到最小生成樹(shù)中，所以除去最初選定的頂點(diǎn)，剩余的n-1個(gè)頂點(diǎn)在加入到最小生成樹(shù)的過(guò)程中可以選擇n-1條邊加入到最小生成樹(shù)的邊集中。6.4圖與最小生成樹(shù)6.4圖與最小生成樹(shù)(2)普里姆算法的操作記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊需要設(shè)置一個(gè)MinEdge類(lèi)型的輔助數(shù)組，類(lèi)型定義如下：#defineMAXSIZE10typedefcharElemType;/*定義頂點(diǎn)類(lèi)型*/typedefstruct{ ElemTypeadjvax;//U中的頂點(diǎn)

intlowcost;//邊的權(quán)值}MinEdge;//記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊需要的輔助數(shù)組類(lèi)型6.4圖與最小生成樹(shù)//求集合V-U依附于頂點(diǎn)u(u∈U)的權(quán)值最小的頂點(diǎn)的序號(hào)/*在輔助數(shù)組中求出權(quán)值最小的頂點(diǎn)序號(hào)*/intMinCost(GraphG,MinEdgee[]){inti,j,min;

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

if(e[i].lowcost!=0)break;

min=i;

for(j=i+1;j<G.n;j++)

if(e[j].lowcost!=0&&e[j].lowcost<e[min].lowcost)min=j;

returnmin;}

6.4圖與最小生成樹(shù)/*【算法6.13普里姆算法】*//*從頂點(diǎn)v出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)，并輸出最小生成樹(shù)的各條邊*/voidMiniSpanTree_PRIM(GraphG,ElemTypev){inti,j,k;

MinEdgee[MAXSIZE];

k=LocateVex(G,v);/*確定頂點(diǎn)v在網(wǎng)G中的序號(hào)*/

for(j=0;j<G.n;j++)/*初始化輔助數(shù)組*/

if(j!=k)

{e[j].adjvax=v;

e[j].lowcost=G.arcs[k][j]

}6.4圖與最小生成樹(shù)

/*初始頂點(diǎn)生成樹(shù)集合，lowcost值為0，表示該頂點(diǎn)已并入生成樹(shù)集合*/

e[k].lowcost=0;

for(i=0;i<G.n-1;i++)

{k=MinCost(G,e);//求輔助數(shù)組中權(quán)值最小頂點(diǎn)

/*輸入最小生成樹(shù)的一條邊和對(duì)應(yīng)的權(quán)值*/printf("(%c,%c,%d)“,e[k].adjvax,G.V[k],e[k].lowcost);

e[k].lowcost=0;//將頂點(diǎn)k并入生成樹(shù)集合6.4圖與最小生成樹(shù)

for(j=0;j<G.n;j++)/*重新調(diào)整e*/

if(G.arcs[k][j]<e[j].lowcost)

{e[j].adjvax=G.V[k];

e[j].lowcost=G.arcs[k][j];

}

}

printf("\n");}表6.1給出了在用算法6.13構(gòu)造圖6.17的圖G13的最小生成樹(shù)的過(guò)程中，MinEdge類(lèi)型數(shù)組元素的兩個(gè)成員分量及兩個(gè)集合的取值變化情況。

6.4圖與最小生成樹(shù)最小生成樹(shù)1.通過(guò)普里姆算法生成最小生成樹(shù)

e[vi]e[v1]e[v2]e[v3]e[v4]e[v5]e[v6]e[v7]UMinCostW=V-Uadjvexlowcostv10v118v1∞v1∞v1∞v12v14{v1}2{v2,v3,v4,v5,v6,v7}adjvexlowcostv10v118v1∞v1∞v69v10v14{v1,v6}4{v2,v3,v4,v5,v7}adjvexlowcostv10v713v1∞v1∞v69v10v10{v1,v6,v7}9{v2,v3,v4,v5}adjvexlowcostv10v713v1∞v51v60v10v10{v1,v6,v7,v5}1{v2,v3,v4}adjvexlowcostv10v713v45v50v60v10v10{v1,v6,v7,v5,v4}5{v2,v3}adjvexlowcostv10v36v40v50v60v10v10{v1,v6,v7,v5,v4,v3}6{v2}adjvexlowcostv10v30v40v50v60v10v10{v1,v6,v7,v5,v4,v3,v2}

{}6.4圖與最小生成樹(shù)6.4圖與最小生成樹(shù)2.通過(guò)克魯斯卡爾算法生成最小生成樹(shù)普里姆算法適用于稠密圖，而克魯斯卡爾算法適用于稀疏圖?？唆斔箍査惴ㄊ菑倪叺慕嵌惹髨D的最小生成樹(shù)?？唆斔箍査惴紤]問(wèn)題的出發(fā)點(diǎn)是為了使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，這樣應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能小。6.4圖與最小生成樹(shù)克魯斯卡爾算法具體做法如下：(1)將圖中所有邊按權(quán)值遞增順序排列；(2)先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖；(3)依次選取權(quán)值較小的邊，但要求后面選取的邊不能與前面選取的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，再去選取后面權(quán)值較大的邊。(4)重復(fù)第(3)步，在具有n個(gè)頂點(diǎn)的圖中，選夠n-1條邊即可。圖6.18是圖6.17(a)帶權(quán)無(wú)向圖的克魯斯卡爾算法構(gòu)造最小生成樹(shù)的過(guò)程。6.4圖與最小生成樹(shù)6.5最短路徑6.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

1.單源點(diǎn)最短路徑的定義在網(wǎng)圖中，求點(diǎn)A到點(diǎn)B的所有路徑中，邊的權(quán)值之和最短的那一條路徑。這條路徑就是兩點(diǎn)之間的最短路徑，并稱(chēng)路徑上的第一個(gè)頂點(diǎn)為起點(diǎn)(Sourse)，最后一個(gè)頂點(diǎn)為終點(diǎn)(Destination)。最短路徑問(wèn)題是圖的一個(gè)比較典型的應(yīng)用問(wèn)題。而單源點(diǎn)最短路徑是其中比較重的一個(gè)應(yīng)用。設(shè)有向圖G=(V,E)。以某指定頂點(diǎn)為源點(diǎn)，求從出發(fā)到圖中其余各點(diǎn)的最短路徑稱(chēng)為單源最短路徑。6.5最短路徑源點(diǎn)終點(diǎn)最短路徑路徑長(zhǎng)度v6v1<v6，v1>2v6v2<v6，v7，v2>17v6v3<v6，v5，v4，v3>15v6v4<v6，v5，v4>10v6v5<v6，v5>9v6v7<v6，v7>4

通過(guò)表6.2可以看出，從v6出發(fā)到v3存在4條路徑，分別是<v6，v1，v2，v3>、<v6，v7，v2，v3>、<v6，v5，v7，v2，v3>、<v6，v5，v4，v3>，這四條路徑的長(zhǎng)度分別是26，23，49，15。通過(guò)比較得出，<v6，v5，v4，v3>是v6到v3的最短路徑。

6.5最短路徑2.迪杰斯特拉(Dijlstra)算法迪杰斯特拉提出了按路長(zhǎng)遞增產(chǎn)生各頂點(diǎn)的最短路徑算法。(1)迪杰斯特拉算法的基本思想把圖中所有頂點(diǎn)分成兩組，第一組包括已確定最短路徑的頂點(diǎn)，第二組包括未確定最短路徑的頂點(diǎn)，然后按最短路徑長(zhǎng)度遞增的次序逐個(gè)把第二組的頂點(diǎn)加到第一組中，直至從源點(diǎn)出發(fā)可以到達(dá)的所有頂點(diǎn)都包括到第一組中。保持從源點(diǎn)到第一組各頂點(diǎn)的最短路徑長(zhǎng)度都不大于從源點(diǎn)到第二組的任何頂點(diǎn)的最短路徑長(zhǎng)度。每一個(gè)頂點(diǎn)都對(duì)應(yīng)一個(gè)距離值，第一組頂點(diǎn)對(duì)應(yīng)的距離值就是從源點(diǎn)到此頂點(diǎn)的只包括第一組的頂點(diǎn)為中間頂點(diǎn)的最短路徑長(zhǎng)度。6.5最短路徑設(shè)v0是起始源點(diǎn)，S是已求得最短路徑的終點(diǎn)集合。迪杰斯特拉算法的基本思想是：①V-S=未確定最短路徑的頂點(diǎn)的集合，初始時(shí)S={v0}，長(zhǎng)度最短路徑是邊數(shù)為1且權(quán)值最小的路徑。②下一條長(zhǎng)度最短的路徑：vi

V-S，先求出v0到vi且中間只經(jīng)S中頂點(diǎn)的最短路徑；上述最短路徑中長(zhǎng)度最小者即為下一條長(zhǎng)度最短的路徑，將所求最短路徑的終點(diǎn)加入S中。③重復(fù)②直到求出所有終點(diǎn)的最短路徑。6.5最短路徑(2)迪杰斯特拉算法的實(shí)現(xiàn)為實(shí)現(xiàn)迪杰斯特拉算法，我們需要引入一個(gè)輔助數(shù)組D[i]，用于保存從源點(diǎn)出發(fā)到達(dá)頂點(diǎn)vi的最短路徑，其值為最短路徑長(zhǎng)度。①初始時(shí)，若源點(diǎn)到頂點(diǎn)vi有邊，則D[i]為邊上的權(quán)值；否則，D[i]為∞。從v0出發(fā)，長(zhǎng)度最短的路徑是(v0，vj)，即D[j]=min{D[i]|vi∈V-S}，將頂點(diǎn)vj加入S集合，同時(shí)將其從集合V-S中去掉；6.5最短路徑②求下一條長(zhǎng)度最短的路徑：修改從v0出發(fā)到達(dá)集合V-S中所有頂點(diǎn)的最短路徑的長(zhǎng)度。這些路徑可能是v0直達(dá)vk，或者是從v0出發(fā)經(jīng)過(guò)S中的某一個(gè)或一些頂點(diǎn)。如果D[j]+arcs[j][k]<D[k](vk∈V-S)，則修改D[k]為D[j]+arcs[j][k]。③最短路徑中長(zhǎng)度最小者即為下一條長(zhǎng)度最短的路徑，即D[j]=min{D[i]|vi∈V-S}。將頂點(diǎn)vj加入S集合，同時(shí)將其從集合V-S中去掉；④重復(fù)②和③直到求出所有頂點(diǎn)的最短路徑。最短路徑終點(diǎn)vi從v6頂點(diǎn)出發(fā)到其余各頂點(diǎn)的最短路徑path[i]的變化情況i=0i=1i=2i=3i=4i=5i=6

dist[v1]path[v1]

2<v6,v1>

dist[v2]path[v2]

∞20<v6,v1,v2>17<v6,v7,v2>17<v6,v7,v2>17<v6,v7,v2>17<v6,v7,v2>dist[v3]path[v3]

∞∞∞∞15<v6,v5,v4,v3>

dist[v4]path[v4]

∞∞∞10<v6,v5,v4>

dist[v5]path[v5]

9<v6,v5>9<v6,v5>9<v6,v5>

dist[v6]path[v6]0

dist[v7]path[v7]

4<v6,v7>4<v6,v7>

vj

v1v7v5v4v3v2S{v6}{v6,v1}{v6,v1,v7}{v6,v1,v7,v5}{v6,v1,v7,v5,v4}{v6,v1,v7,v5,v4,v3}{v6,v1,v7,v5,v4,v3,v2}6.5最短路徑voidDijkstra(GraphG,intv0,intpath[],intdist[])/*求有向圖G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑，path[i]是v0到vi的最短路徑上的前驅(qū)頂點(diǎn)，dist[i]是路徑長(zhǎng)度*/{ inti,j,v,w; intmin;ints[MAXSIZE]; for(i=0;i<G.n;i++)/*初始化s，dist和path*/ {s[i]=0;dist[i]=G.arcs[v0][i]; if(dist[i]<Max)path[i]=v0; elsepath[i]=-1;} dist[v0]=0;s[v0]=1;/*初始源點(diǎn)v0屬于s集*/ /*循環(huán)求v0到某個(gè)頂點(diǎn)v的最短路徑，并將v加入s集*/

6.5最短路徑for(i=1;i<G.n-1;i++){min=Max; for(w=0;w<G.n;w++)//w不屬于s且離v0更近 {if(!s[w]&&dist[w]<min) {v=w;min=dist[w];}} s[v]=1;/*頂點(diǎn)v并入s*/ for(j=0;j<G.n;j++)//更新最短路徑及距離 {if(!s[j]&&(min+G.arcs[v][j]<dist[j])) {dist[j]=min+G.arcs[v][j];path[j]=v;} }}}

6.6AOV網(wǎng)與拓?fù)渑判?.6AOV網(wǎng)與拓?fù)渑判駻OV網(wǎng)在一個(gè)有向圖中，若用頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)間的先后關(guān)系，稱(chēng)該有向圖為用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(ActivityOnVertexnetwork，AOV)。若從頂點(diǎn)vi到頂點(diǎn)vj之間存在一條有向路徑，稱(chēng)頂點(diǎn)vi是頂點(diǎn)vj的前驅(qū)，或者稱(chēng)頂點(diǎn)vj是頂點(diǎn)vi的后繼。即若<vi，vj>是圖中的邊，則稱(chēng)頂點(diǎn)vi是頂點(diǎn)vj的直接前驅(qū)，頂點(diǎn)vj是頂點(diǎn)vi的直接后繼。6.6AOV網(wǎng)與拓?fù)渑判駻OV網(wǎng)大工程被劃分成許多子工程(稱(chēng)為活動(dòng))。在大工程實(shí)施過(guò)程中，有些活動(dòng)開(kāi)始是以它的所有前序活動(dòng)的結(jié)束為先決條件的，必須在其他有關(guān)活動(dòng)完成后才能開(kāi)始；有些活動(dòng)沒(méi)有先決條件，可以安排在任意時(shí)間開(kāi)始。AOV網(wǎng)是一種可以形象地反映出整個(gè)工程中各個(gè)活動(dòng)之間前后關(guān)系的有向圖。6.6AOV網(wǎng)與拓?fù)渑判虮?.4各課程先后依存關(guān)系表課程課程名稱(chēng)先修課程C1高等數(shù)學(xué)無(wú)C2C語(yǔ)言程序設(shè)計(jì)無(wú)C3離散數(shù)學(xué)C1，C2C4數(shù)據(jù)結(jié)構(gòu)C2，C3C5Java程序設(shè)計(jì)C2C6編譯方法C5，C7C7操作系統(tǒng)C4，C9C8數(shù)字邏輯C1C9計(jì)算機(jī)組成原理C8圖6.20課程開(kāi)設(shè)的先后關(guān)系A(chǔ)OV網(wǎng)6.6AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判蛲負(fù)渑判?TopologicalSort)是圖中重要的運(yùn)算之一，在實(shí)際中應(yīng)用很廣泛。對(duì)給定的AOV網(wǎng)應(yīng)首先判定網(wǎng)中是否存在環(huán)。檢測(cè)的辦法是對(duì)有向圖進(jìn)行拓?fù)渑判颍═opologicalSort），拓?fù)渑判蛑赴凑沼邢驁D給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線(xiàn)性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則加上任意的次序關(guān)系，所得頂點(diǎn)的線(xiàn)性序列稱(chēng)之為拓?fù)渑判蛐蛄小?.6AOV網(wǎng)與拓?fù)渑判?.拓?fù)渑判虻亩x給出有向圖G=(V，E)，對(duì)于V中的頂點(diǎn)的線(xiàn)性序列(v1，v-2，…，vk)，如果滿(mǎn)足如下條件：若在G中從頂點(diǎn)vi到vj有一條路徑，則在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前，稱(chēng)該序列為G的一個(gè)拓?fù)湫蛄?。?gòu)造有向圖的拓?fù)湫蛄械倪^(guò)程稱(chēng)為拓?fù)渑判颉?.6AOV網(wǎng)與拓?fù)渑判?1)拓?fù)渑判虻淖⒁馐马?xiàng)①在AOV網(wǎng)中，若不存在回路，則所有活動(dòng)可排成一個(gè)線(xiàn)性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，那么該序列為拓?fù)湫蛄?。②拓?fù)湫蛄胁皇俏ㄒ坏?。③?duì)AOV網(wǎng)不一定都有拓?fù)湫蛄小＂軐OV圖中頂點(diǎn)排成一個(gè)線(xiàn)性序列，若該線(xiàn)性序列中包含AOV網(wǎng)全部的頂點(diǎn)，則AOV網(wǎng)中無(wú)環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該網(wǎng)所代表的工程是不可行的。6.6AOV網(wǎng)與拓?fù)渑判?2)拓?fù)湫蛄械膶?shí)際意義如果按照拓?fù)湫蛄兄械捻旤c(diǎn)次序進(jìn)行每一項(xiàng)活動(dòng)，就能夠保證在開(kāi)始每一項(xiàng)活動(dòng)時(shí)，它的所有前驅(qū)活動(dòng)均已完成，從而使整個(gè)工程順序執(zhí)行。6.6AOV網(wǎng)與拓?fù)渑判?.拓?fù)渑判虻幕静襟E①在AOV網(wǎng)中選一個(gè)入度為0的頂點(diǎn)(沒(méi)有前驅(qū))并輸出它；②從AOV網(wǎng)中刪除此頂點(diǎn)及從該頂點(diǎn)發(fā)出來(lái)的所有有向邊；③重復(fù)①②兩步，直到AOV網(wǎng)中所有的頂點(diǎn)都被輸出或網(wǎng)中不存在入度為0的頂點(diǎn)。6.6AOV網(wǎng)與拓?fù)渑判?.拓?fù)渑判虻幕静襟E對(duì)圖6.20進(jìn)行拓?fù)渑判?。列舉兩種得到的拓?fù)溆行蛐蛄校篊1，C8，C9，C2，C3，C4，C7，C5，C6或 C1，C8，C9，C2，C5，C3，C4，C7，C66.7AOE網(wǎng)與關(guān)鍵路徑6.7AOE網(wǎng)與關(guān)鍵路徑AOE網(wǎng)若在帶權(quán)的有向圖中，以頂點(diǎn)表示事件；有向邊表示活動(dòng)；邊上的權(quán)值表示活動(dòng)的開(kāi)銷(xiāo)(如該活動(dòng)持續(xù)的時(shí)間)。則稱(chēng)此帶權(quán)的有向圖為AOE(activityonedge)網(wǎng)。如果用AOE網(wǎng)來(lái)表示一項(xiàng)工程，可以如下信息：完成預(yù)定工程計(jì)劃所需要進(jìn)行的活動(dòng)；每個(gè)活動(dòng)計(jì)劃的完成時(shí)間；要發(fā)生哪些事件以及這些事件與活動(dòng)之間的關(guān)系。針對(duì)某一工程對(duì)應(yīng)的AOE網(wǎng)，我們可以用確定關(guān)鍵路徑的方法來(lái)驗(yàn)證該工程能否完成，并且要估計(jì)工程的完成所需要的時(shí)間以及確定哪些活動(dòng)會(huì)影響工程進(jìn)度。6.7AOE網(wǎng)與關(guān)鍵路徑AOE網(wǎng)在AOE網(wǎng)中，只有在某頂點(diǎn)所代表的事件發(fā)生后，從該頂點(diǎn)出發(fā)的各有向邊所代表的活動(dòng)才能開(kāi)始；只有在進(jìn)入每個(gè)頂點(diǎn)的各有向邊所代表的活動(dòng)都已經(jīng)結(jié)束后，該頂點(diǎn)所代表的事件才能發(fā)生。一個(gè)表示工程的AOE網(wǎng)應(yīng)該是沒(méi)有回路的有向網(wǎng)，網(wǎng)中僅存在一個(gè)入度為0的頂點(diǎn)，稱(chēng)作開(kāi)始頂點(diǎn)(源點(diǎn))，它表示整個(gè)工程的開(kāi)始；網(wǎng)中僅存在一個(gè)出度為0的頂點(diǎn)，稱(chēng)為結(jié)束頂點(diǎn)(匯點(diǎn))，它表示整個(gè)工程的結(jié)束。6.7AOE網(wǎng)與關(guān)鍵路徑圖6.21是一個(gè)有9個(gè)活動(dòng)11個(gè)事件的AOE網(wǎng)。頂點(diǎn)v1、v2、…、v9表示事件；<v1，v2>，<v1，v3>，<v1，v4>…<v8，v9>表示活動(dòng)。其中v1為開(kāi)始頂點(diǎn)，入度是0；v9為結(jié)束頂點(diǎn)，出度是0。6.7AOE網(wǎng)與關(guān)鍵路徑關(guān)鍵路徑1.相關(guān)術(shù)語(yǔ)(1)AOE網(wǎng)的路徑長(zhǎng)度AOE網(wǎng)的路徑長(zhǎng)度是該路徑上各個(gè)活動(dòng)所需時(shí)間的總和。(2)關(guān)鍵路徑由于AOE網(wǎng)中的某些活動(dòng)能夠同時(shí)進(jìn)行，故完成整個(gè)工程所必須花費(fèi)的時(shí)間應(yīng)該為：源點(diǎn)到終點(diǎn)的最大路徑長(zhǎng)度(路徑長(zhǎng)度是指該路徑上的各個(gè)活動(dòng)所需時(shí)間之和)。具有最大路徑長(zhǎng)度的路徑稱(chēng)為關(guān)鍵路徑。關(guān)鍵路徑上的活動(dòng)稱(chēng)為關(guān)鍵活動(dòng)。6.7AOE網(wǎng)與關(guān)鍵路徑(3)事件的最早發(fā)生時(shí)間ve(i)從源點(diǎn)到頂點(diǎn)i的最大路徑長(zhǎng)度代表的時(shí)間，意味著所有以頂點(diǎn)i為弧尾的活動(dòng)的最早開(kāi)始時(shí)間計(jì)算方法如下：①令ve(1)=0，i=2；②ve(i)=Max{ve(k)+t(k,i)|k為i的直接前驅(qū)}；③++i，重復(fù)②，直到i>n。6.7AOE網(wǎng)與關(guān)鍵路徑(4)事件的最遲發(fā)生時(shí)間vl(i)事件vi允許的最晚發(fā)生時(shí)間vl(k)是指在不推遲整個(gè)工程工期(即保證結(jié)束頂點(diǎn)vn在ve(n)時(shí)刻發(fā)生)的前提下，