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

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

6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(7)完全圖如果無(wú)向圖中任意兩個(gè)頂點(diǎn)間都存在邊，則稱之為無(wú)向完全圖(CompletedGraph)。在一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向完全圖中，邊數(shù)為n(n-1)/2條。如果有向圖中任意兩個(gè)頂點(diǎn)間都存在方向互為相反的兩條弧，則稱之為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，邊數(shù)為n(n-1)條。(8)稠密圖、稀疏圖當(dāng)一個(gè)圖接近完全圖時(shí)，稱之為稠密圖(DenseGraph)；相反地，當(dāng)一個(gè)圖中含有較少的邊或弧時(shí)，則稱之為稀疏圖(SparseGraph)。6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(9)子圖若有兩個(gè)圖G1和G2，其中，G1=(V1,E1)，G2=(V2,E2)，且滿足如下條件：V2?V1，E2?E1即V2為V1的子集，E2為E1的子集，則稱圖G2為圖G1的子圖。6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(10)鄰接點(diǎn)和度對(duì)于無(wú)向圖，假若頂點(diǎn)v和頂點(diǎn)w之間存在一條邊，則稱頂點(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)的度記為TD(v)，有TD(v)=OD(v)+ID(v)。6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(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ù)目。6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(12)簡(jiǎn)單路徑、回路、簡(jiǎn)單回路頂點(diǎn)序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑，稱為簡(jiǎn)單路徑；若頂點(diǎn)序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同，則稱該路徑為回路或環(huán)(Cycle)；若頂點(diǎn)序列中除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)，則稱該回路為簡(jiǎn)單回路或者簡(jiǎn)單環(huán)。6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(13)連通圖、連通分量無(wú)向圖G中，如果從頂點(diǎn)vi到頂點(diǎn)vj有路徑，則稱頂點(diǎn)vi和vj是連通的。如果對(duì)于圖中任意兩個(gè)頂點(diǎn)vi、vj∈V，vi和vj都是連通的，則稱圖G為連通圖(ConnectedGraph)。在無(wú)向圖中，在滿足連通條件時(shí)，盡可能多地包含原圖中的頂點(diǎn)和這些頂點(diǎn)之間的邊的連通子圖稱為該圖的連通分量(ConnectedComponent)；連通圖的連通分量是它本身，非連通圖的連通分量可能為多個(gè)。例如：圖6.3中的G5就是一個(gè)連通圖。而G6就是非連通圖，但有2個(gè)連通分量，如圖6.4所示。6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)圖6.3連通圖G5圖6.4非連通圖G6及兩個(gè)連通分量6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(14)強(qiáng)連通圖、強(qiáng)連通分量有向圖G中，如果從vi到vj有路徑，則稱頂點(diǎn)vi和頂點(diǎn)vj是連通的；若圖中任意兩個(gè)頂點(diǎn)之間都存在兩條互為反方向的路徑，即從vi到vj及從vj到vi都有路徑，則稱此有向圖為強(qiáng)連通圖。有向圖中的極大連通子圖稱作該有向圖的強(qiáng)連通分量。例如，圖6.5中的G7就是一個(gè)強(qiáng)連通圖。而G8就是非強(qiáng)連通圖，但有2個(gè)強(qiáng)連通分量，如圖6.6所示。6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)圖6.5強(qiáng)連通圖G7圖6.6非強(qiáng)連通圖G8及兩個(gè)連通分量6.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(15)生成樹連通圖G的生成樹，是包含G的全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖，該極小連通子圖有(n-1)條邊。如圖6.7所示，是連通圖G5的生成樹。如果在一棵生成樹上添加一條邊，必定構(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.1圖的定義和基本術(shù)語(yǔ)圖的定義2.圖的基本術(shù)語(yǔ)(16)生成森林如果一個(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所示是有向圖G9及其生成森林。6.1圖的定義和基本術(shù)語(yǔ)2.圖的定義圖的基本術(shù)語(yǔ)圖6.7連通圖G5的生成樹

圖6.8有向圖G9及生成森林6.2圖的存儲(chǔ)與操作6.2圖的存儲(chǔ)與操作鄰接矩陣鄰接矩陣（AdjacencyMatrix）是用兩個(gè)數(shù)組來(lái)表示圖，一個(gè)數(shù)組是一維數(shù)組，存儲(chǔ)圖中頂點(diǎn)的信息，另一個(gè)數(shù)組是二維數(shù)組，即矩陣，存儲(chǔ)頂點(diǎn)之間相鄰的信息，也就是邊（或?。┑男畔ⅲ@是鄰接矩陣名稱的由來(lái)。6.2圖的存儲(chǔ)與操作鄰接矩陣1.圖的鄰接矩陣存儲(chǔ)法圖6.3無(wú)向圖G5和圖6.8有向圖G9的鄰接矩陣如下圖6.9所示。

6.2圖的存儲(chǔ)與操作鄰接矩陣2.網(wǎng)的鄰接矩陣帶樹有向網(wǎng)的鄰接矩陣6.2圖的存儲(chǔ)與操作鄰接矩陣3.鄰接矩陣表示法的特點(diǎn)(1)因?yàn)闊o(wú)向圖的鄰接矩陣具有對(duì)稱性，一定是一個(gè)對(duì)稱矩陣，所以可以采取壓縮存儲(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ù)類型*/typedefstruct{ElemTypeV[MAXSIZE];/*頂點(diǎn)信息*/

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

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

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

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

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

return-1;}6.2圖的存儲(chǔ)與操作鄰接矩陣6.鄰接矩陣操作(2)在屏幕上顯示圖G的鄰接矩陣表示算法6.2在屏幕上顯示圖G的鄰接矩陣表示/*在屏幕上顯示圖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ǔ)與操作鄰接矩陣6.鄰接矩陣操作(3)無(wú)向圖/無(wú)向網(wǎng)/有向圖/有向網(wǎng)的鄰接矩陣的建立算法6.3無(wú)向圖/無(wú)向網(wǎng)/有向圖/有向網(wǎng)的鄰接矩陣的創(chuàng)建/*創(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ǔ)與操作鄰接矩陣6.鄰接矩陣操作/*確定兩個(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è)單鏈表就稱為頂點(diǎn)Vi的鄰接表；再將所有頂點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。6.2圖的存儲(chǔ)與操作鄰接表1.圖的鄰接表存儲(chǔ)法在鄰接表表示中，包括兩種結(jié)點(diǎn)結(jié)構(gòu)。（1）一個(gè)是頂點(diǎn)結(jié)點(diǎn)，每個(gè)頂點(diǎn)結(jié)點(diǎn)由2個(gè)域組成，其中data域存儲(chǔ)頂點(diǎn)Vi的名或其相關(guān)信息，firstArc指向頂點(diǎn)Vi的第一個(gè)鄰接點(diǎn)的邊結(jié)點(diǎn)；（2）第二個(gè)是邊結(jié)點(diǎn)，邊結(jié)點(diǎn)由3個(gè)域組成。其中abjVex域存放與Vi鄰接的點(diǎn)的序號(hào)，nextArc指向Vi下一個(gè)鄰接點(diǎn)的邊結(jié)點(diǎn)，info域存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值。圖6.11鄰接表的節(jié)點(diǎn)結(jié)構(gòu)vexfirstarc

adjvexnextarcdata6.2圖的存儲(chǔ)與操作鄰接表2.圖的逆鄰接表存儲(chǔ)法有向圖的鄰接表不方便查找以vi為弧頭的節(jié)點(diǎn)數(shù)，為此我們可以建立一個(gè)逆鄰接表，為每一個(gè)頂點(diǎn)建立一個(gè)以vi為弧頭的表，如圖6.12所示。僅以頂點(diǎn)編號(hào)作為信息輸入，時(shí)間復(fù)雜度為O(n+e)。(a)無(wú)向圖G1的鄰接表(b)有向圖G2的鄰接表(c)有向圖G2的逆鄰接表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)類型為char*//*邊節(jié)點(diǎn)的類型定義*/typedefstructArcNode{intadjVex;

structArcNode*nextArc;

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

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

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

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

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

return-1;}6.2圖的存儲(chǔ)與操作鄰接表7.鄰接表操作(2)無(wú)向圖的鄰接表/有向圖的鄰接表/逆鄰接表的建立算法6.5無(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ǔ)與操作鄰接表7.鄰接表操作(2)無(wú)向圖的鄰接表/有向圖的鄰接表/逆鄰接表的建立

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ǔ)與操作鄰接表7.鄰接表操作(2)無(wú)向圖的鄰接表/有向圖的鄰接表/逆鄰接表的建立

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

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ǔ)與操作鄰接表7.鄰接表操作(2)無(wú)向圖的鄰接表/有向圖的鄰接表/逆鄰接表的建立

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

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

s->nextArc=pg->adjList[i].firstArc;pg->adjList[i].firstArc=s;//頭插法6.2圖的存儲(chǔ)與操作鄰接表7.鄰接表操作(2)無(wú)向圖的鄰接表/有向圖的鄰接表/逆鄰接表的建立

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

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

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

}}}6.2圖的存儲(chǔ)與操作鄰接表7.鄰接表操作(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ā)，訪問(wèn)其余頂點(diǎn)，并且保證所有頂點(diǎn)都被訪問(wèn)且只被訪問(wèn)一次，稱此過(guò)程為圖的遍歷(TraversingGraph)。判斷圖的連通性、拓?fù)渑判蚝颓箨P(guān)鍵路徑都以圖的遍歷為基礎(chǔ)。6.3圖的遍歷圖的遍歷過(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ā)只能訪問(wèn)它所在的連通分量上的所有節(jié)點(diǎn)，并不能訪問(wèn)圖的所有節(jié)點(diǎn)。因此，遍歷還需要考慮不同連通分量的起始節(jié)點(diǎn)的選取問(wèn)題。(3)圖中的一個(gè)節(jié)點(diǎn)可能和多個(gè)節(jié)點(diǎn)相鄰接，我們?nèi)绾芜x取下一個(gè)鄰接點(diǎn)。(4)無(wú)向圖和有向圖中都有可能存在回路，那么在一個(gè)節(jié)點(diǎn)被訪問(wèn)之后有可能因?yàn)榛芈返拇嬖诙俅伪辉L問(wèn)，我們?nèi)绾伪苊庖粋€(gè)節(jié)點(diǎn)被多次訪問(wèn)。6.3圖的遍歷深度優(yōu)先遍歷算法1.圖的深度優(yōu)先（DFS）遍歷深度優(yōu)先遍歷(depth-firstsearch，DFS)類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪問(wèn)過(guò)，在G中任選頂點(diǎn)V為出發(fā)點(diǎn)（源點(diǎn)），則深度優(yōu)先搜索遍歷可定義為：（1）首先訪問(wèn)出發(fā)點(diǎn)V；（2）然后依次從V出發(fā)搜索V的每個(gè)鄰接點(diǎn)W，若W未曾訪問(wèn)過(guò)，則以W為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索遍歷，直至圖中所有和源點(diǎn)V有路徑相通的頂點(diǎn)（也稱為從源點(diǎn)可達(dá)的頂點(diǎn)）均已被訪問(wèn)為止；（3）若此時(shí)圖中仍有未訪問(wèn)的頂點(diǎn)，則另選一個(gè)尚未訪問(wèn)的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)均已被訪問(wèn)為止。6.3圖的遍歷深度優(yōu)先遍歷算法v1v2v5v4v8v3v7v6v1v2v5v4v8v3v6v7

顯然，圖的深度優(yōu)先遍歷是一個(gè)遞歸的過(guò)程?？梢远x一個(gè)訪問(wèn)標(biāo)記數(shù)組visited[0…n-1]，初始值均為false，一旦某個(gè)節(jié)點(diǎn)被訪問(wèn)，立即對(duì)其相應(yīng)分量置true，由此可以區(qū)別圖中節(jié)點(diǎn)是否被訪問(wèn)過(guò)，并最終遍歷所有節(jié)點(diǎn)，同時(shí)避免了節(jié)點(diǎn)的重復(fù)訪問(wèn)。6.3圖的遍歷深度優(yōu)先遍歷算法2.圖的深度優(yōu)先遍歷操作算法6.7從圖的某一節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索voidDFSTraverse(GraphG)/*對(duì)圖G進(jìn)行深度優(yōu)先遍歷*/{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圖的遍歷深度優(yōu)先遍歷算法2.圖的深度優(yōu)先遍歷操作算法6.8利用鄰接矩陣實(shí)現(xiàn)連通圖的深度優(yōu)先遍歷/*從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/voidDFS(GraphG,inti){intj;printf("%3c",G.V[i]);/*訪問(wèn)第i個(gè)項(xiàng)點(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的尚未訪問(wèn)的鄰接頂點(diǎn)j遞歸調(diào)用DFS}6.3圖的遍歷深度優(yōu)先遍歷算法2.圖的深度優(yōu)先遍歷操作算法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);/*訪問(wèn)第i個(gè)項(xiàng)點(diǎn)*/visited[i]=1;p=G.adjList[i].firstArc;6.3圖的遍歷深度優(yōu)先遍歷算法2.圖的深度優(yōu)先遍歷操作算法6.9用鄰接表實(shí)現(xiàn)連通圖的深度優(yōu)先遍歷/*從第i個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G*/while(p!=NULL){if(visited[p->adjVex]==0)DFS(G,p->adjVex);/*對(duì)i的尚未訪問(wèn)的鄰接頂點(diǎn)j遞歸調(diào)用DFS*/

p=p->nextArc;}}6.3圖的遍歷廣度優(yōu)先遍歷算法1.圖的廣度優(yōu)先遍歷廣度優(yōu)先搜索（Breadth_FirstSearch）遍歷類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有的頂點(diǎn)均未訪問(wèn)過(guò)，在G中任選一頂點(diǎn)vi為源點(diǎn)，則廣度優(yōu)先搜索遍歷過(guò)程為：（1）首先訪問(wèn)出發(fā)點(diǎn)vi，并將其訪問(wèn)標(biāo)志置為已被訪問(wèn)，即visited[i]=true；（2）接著依次訪問(wèn)頂點(diǎn)vi的所有鄰接點(diǎn)w0，w1，w2，……，wt；（3）然后再依次訪問(wèn)頂點(diǎn)w0，w1，w2，……，wt的所有鄰接點(diǎn)。（4）如此類推，直至圖中所有的頂點(diǎn)都被訪問(wèn)到。6.3圖的遍歷廣度優(yōu)先遍歷算法1.圖的廣度優(yōu)先遍歷從頂點(diǎn)V1出發(fā)的廣度優(yōu)先搜索遍歷序列可能有多種，這里只給出其中的三種，其它的可類似分析。這三種廣度優(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圖的遍歷廣度優(yōu)先遍歷算法2.圖的廣度優(yōu)先遍歷操作算法6.10對(duì)圖進(jìn)行廣度優(yōu)先遍歷voidBFSTraverse(GraphG)//對(duì)圖G進(jìn)行廣度優(yōu)先遍歷{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圖的遍歷廣度優(yōu)先遍歷算法2.圖的廣度優(yōu)先遍歷操作算法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]);/*訪問(wèn)第k個(gè)頂點(diǎn)*/visited[k]=1;EnQueue(&Q,k);/*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/while(!QueueEmpty(&Q)){/*隊(duì)列非空*/6.3圖的遍歷廣度優(yōu)先遍歷算法2.圖的廣度優(yōu)先遍歷操作算法6.11廣度優(yōu)先遍歷以鄰接矩陣存儲(chǔ)的圖//從第k個(gè)頂點(diǎn)出發(fā)廣度優(yōu)先遍歷圖G,G以鄰接矩陣表示DelQueue(&Q,&i);for(j=0;j<G.n;j++){if((G.arcs[i][j]==1)&&(visited[j]==0)){/*訪問(wèn)第i個(gè)頂點(diǎn)的末曾訪問(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圖的遍歷廣度優(yōu)先遍歷算法2.圖的廣度優(yōu)先遍歷操作算法6.12廣度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖//從第k個(gè)頂點(diǎn)出發(fā)廣度優(yōu)先遍歷圖G,G以鄰接矩陣表示voidBFS(ALGraphG,intk){inti;ArcNode*p;InitQueue(&Q);/*初始化隊(duì)列*/printf("%3c",G.adjList[k].data);/*訪問(wèn)第k個(gè)項(xiàng)點(diǎn)*/visited[k]=1; EnQueue(&Q,k);/*第k個(gè)頂點(diǎn)進(jìn)隊(duì)*/while(!QueueEmpty(&Q)){/*隊(duì)列非空*/

6.3圖的遍歷廣度優(yōu)先遍歷算法2.圖的廣度優(yōu)先遍歷操作算法6.12廣度優(yōu)先遍歷以鄰接表存儲(chǔ)的圖DelQueue(&Q,&i);p=G.adjList[i].firstArc;/*獲取第1個(gè)鄰接點(diǎn)*/while(p!=NULL){if(visited[p->adjVex]==0){/*訪問(wèn)第i個(gè)頂點(diǎn)的末曾訪問(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圖與最小生成樹6.4圖與最小生成樹生成樹和森林的概念在一個(gè)有n個(gè)頂點(diǎn)的連通圖G中，存在一個(gè)極小的連通子圖G’，G’包含圖G的所有頂點(diǎn)，但只有n-1條邊，并且G’是連通的，稱G’為G的生成樹；由深度優(yōu)先搜索得到的生成樹稱為深度優(yōu)先生成樹，簡(jiǎn)稱為DFS生成樹；由廣度優(yōu)先搜索得到的生成樹稱為廣度優(yōu)先生成樹，簡(jiǎn)稱為BFS生成樹。6.4圖與最小生成樹生成樹和森林的概念若一個(gè)圖是非連通圖或非強(qiáng)連通圖，但有若干個(gè)連通分量或若干個(gè)強(qiáng)連通分量，則通過(guò)深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，不能得到生成樹，但可以得到生成森林，且若非連通圖有n個(gè)頂點(diǎn)，m個(gè)連通分量或強(qiáng)連通分量，則可以遍歷得到m棵生成樹，合起來(lái)為生成森林，森林中包含n-m條樹邊。6.4圖與最小生成樹最小生成樹無(wú)向連通帶權(quán)圖G的權(quán)為生成樹T中各邊的權(quán)值總和；邊的權(quán)值總和最小的生成樹，稱為最小代價(jià)生成樹(MinimumcostSpanningTree，MST)。構(gòu)造最小生成樹的準(zhǔn)則如下：(1)必須只使用該網(wǎng)中的邊來(lái)構(gòu)造最小生成樹；(2)必須使用且僅使用n-1條邊來(lái)連接網(wǎng)中的n個(gè)頂點(diǎn)；(3)不能使用產(chǎn)生回路的邊。6.4圖與最小生成樹最小生成樹在帶權(quán)的連通無(wú)向圖G=(V,E)上，構(gòu)造最小生成樹有普里姆算法和克魯斯卡爾算法，它們都是應(yīng)用最小生成樹MST的性質(zhì)：U是頂點(diǎn)V的一個(gè)非空子集，若(u,v)是一條具有最小權(quán)值的邊，其中u∈U,v∈V?U，則一定存在一棵包含邊(u,v)的最小生成樹。6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹(1)普里姆(Prim)算法的基本思想設(shè)G=(V,E)是帶權(quán)圖，V是圖G的頂點(diǎn)集，E是邊集。①在圖中任取一個(gè)頂點(diǎn)k作為開始點(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)，將該邊作為最小生成樹的樹邊放入TE，并將頂點(diǎn)v加入集合U中，并從W中刪去這個(gè)頂點(diǎn)。③重復(fù)②，直到W為空集為止。此時(shí)TE中有n-1條邊，此時(shí)T=(U,TE)就是G的一棵最小生成樹。6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹(1)普里姆(Prim)算法的基本思想普里姆算法是從最小生成樹中頂點(diǎn)的角度出發(fā)來(lái)考慮的，因?yàn)閳D中有n個(gè)頂點(diǎn)，按照生成樹的定義，所有的頂點(diǎn)都必須加入到最小生成樹中，所以除去最初選定的頂點(diǎn)，剩余的n-1個(gè)頂點(diǎn)在加入到最小生成樹的過(guò)程中可以選擇n-1條邊加入到最小生成樹的邊集中。6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹(2)普里姆算法的操作記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊需要設(shè)置一個(gè)MinEdge類型的輔助數(shù)組，類型定義如下：#defineMAXSIZE10typedefcharElemType;/*定義頂點(diǎn)類型*/typedefstruct{ ElemTypeadjvax; intlowcost;}MinEdge;6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹//求出集合中V-U依附于頂點(diǎn)u（u∈U）的權(quán)值最小的頂點(diǎn)的序號(hào)/*在輔助數(shù)組中求出權(quán)值最小的頂點(diǎn)序號(hào)*/intMinCost(GraphG,MinEdgeedge[]){ inti,j,min; for(i=0;i<G.n;i++) if(edge[i].lowcost!=0) break;

6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹 min=i; for(j=i+1;j<G.n;j++)

if(edge[j].lowcost!=0&&edge[j].lowcost<

edge[min].lowcost) min=j; returnmin;}6.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹(2)普里姆算法的操作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圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹

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

e[k].lowcost=0;

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

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

/*輸入最小生成樹的一條邊和對(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并入生成樹集合

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

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.4圖與最小生成樹最小生成樹1.通過(guò)普里姆算法生成最小生成樹

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圖與最小生成樹最小生成樹2.通過(guò)克魯斯卡爾算法生成最小生成樹克魯斯卡爾算法考慮問(wèn)題的出發(fā)點(diǎn)是為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。具體做法是先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖G’，然后從權(quán)值最小的邊開始，若它的添加不使G’中產(chǎn)生回路，則在G’上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。6.4圖與最小生成樹最小生成樹2.通過(guò)克魯斯卡爾算法生成最小生成樹6.4圖與最小生成樹最小生成樹2.通過(guò)克魯斯卡爾算法生成最小生成樹6.4圖與最小生成樹最小生成樹2.通過(guò)克魯斯卡爾算法生成最小生成樹6.5最短路徑6.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

1.單源點(diǎn)最短路徑的定義在網(wǎng)圖中，求點(diǎn)A到點(diǎn)B的所有路徑中，邊的權(quán)值之和最短的那一條路徑。這條路徑就是兩點(diǎn)之間的最短路徑，并稱路徑上的第一個(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)的最短路徑稱為單源最短路徑。6.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

2.迪杰斯特拉算法6.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

2.迪杰斯特拉算法源點(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>46.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

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最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

2.迪杰斯特拉算法(1)迪杰斯特拉算法的基本思想設(shè)v0是起始源點(diǎn)，S是已求得最短路徑的終點(diǎn)集合。迪杰斯特拉算法的基本思想是：①V-S=未確定最短路徑的頂點(diǎn)的集合，初始時(shí)S={v0}，長(zhǎng)度最短路徑是邊數(shù)為1且權(quán)值最小的路徑。②下一條長(zhǎng)度最短的路徑：viV-S，先求出v0到vi且中間只經(jīng)S中頂點(diǎn)的最短路徑；上述最短路徑中長(zhǎng)度最小者即為下一條長(zhǎng)度最短的路徑，將所求最短路徑的終點(diǎn)加入S中。③重復(fù)②直到求出所有終點(diǎn)的最短路徑。6.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

2.迪杰斯特拉算法(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最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

2.迪杰斯特拉算法(2)迪杰斯特拉算法的實(shí)現(xiàn)②求下一條長(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)到其余各頂點(diǎn)的最短路徑

2.迪杰斯特拉算法

終點(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最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

2.迪杰斯特拉算法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];

6.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

if(dist[i]<Max) path[i]=v0; else path[i]=-1; } dist[v0]=0; s[v0]=1;/*初始時(shí)源點(diǎn)v0屬于s集*/ //循環(huán)求v0到某個(gè)頂點(diǎn)v的最短路徑，并將v加入s集 for(i=1;i<G.n-1;i++) { min=Max; for(w=0;w<G.n;w++) { /*頂點(diǎn)w不屬于s集且離v0更近*/

6.5最短路徑單源點(diǎn)到其余各頂點(diǎn)的最短路徑

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++) {//更新當(dāng)前最短路徑及距離

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)系，稱該有向圖為用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(ActivityOnVertexnetwork，AOV)。若從頂點(diǎn)vi到頂點(diǎn)vj之間存在一條有向路徑，稱頂點(diǎn)vi是頂點(diǎn)vj的前驅(qū)，或者稱頂點(diǎn)vj是頂點(diǎn)vi的后繼。即若<vi，vj>是圖中的邊，則稱頂點(diǎn)vi是頂點(diǎn)vj的直接前驅(qū)，頂點(diǎn)vj是頂點(diǎn)vi的直接后繼?，F(xiàn)代化管理中，一個(gè)大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動(dòng)。在整個(gè)工程實(shí)施過(guò)程中，有些活動(dòng)開始是以它的所有前序活動(dòng)的結(jié)束為先決條件的，必須在其他有關(guān)活動(dòng)完成之后才能開始，有些活動(dòng)沒(méi)有先決條件，可以安排在任意時(shí)間開始。AOV網(wǎng)就是一種可以形象地反映出整個(gè)工程中各個(gè)活動(dòng)之間前后關(guān)系的有向圖。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è)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。由此所得頂點(diǎn)的線性序列稱之為拓?fù)渑判蛐蛄小?.6AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判?.拓?fù)渑判虻亩x給出有向圖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)造有向圖的拓?fù)湫蛄械倪^(guò)程稱為拓?fù)渑判颉?.6AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判?.拓?fù)渑判虻亩x(1)拓?fù)渑判虻淖⒁馐马?xiàng)關(guān)于拓?fù)渑判蛭覀冃枰⒁庖韵聨c(diǎn)：①在AOV網(wǎng)中，若不存在回路，則所有活動(dòng)可排成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，那么該序列為拓?fù)湫蛄?。②拓?fù)湫蛄胁皇俏ㄒ坏摹＂蹖?duì)AOV網(wǎng)不一定都有拓?fù)湫蛄?。④將AOV圖中頂點(diǎn)排成一個(gè)線性序列，若該線性序列中包含AOV網(wǎng)全部的頂點(diǎn)，則AOV網(wǎng)中無(wú)環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該網(wǎng)所代表的工程是不可行的。6.6AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判?.拓?fù)渑判虻亩x(2)拓?fù)湫蛄械膶?shí)際意義如果按照拓?fù)湫蛄兄械捻旤c(diǎn)次序進(jìn)行每一項(xiàng)活動(dòng)，就能夠保證在開始每一項(xiàng)活動(dòng)時(shí)，它的所有前驅(qū)活動(dòng)均已完成，從而使整個(gè)工程順序執(zhí)行。6.6AOV網(wǎng)與拓?fù)渑判蛲負(fù)渑判?.拓?fù)渑判虻幕静襟E對(duì)AOV網(wǎng)進(jìn)行拓?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ù)渑判?.拓?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)的開銷（如該活動(dòng)持續(xù)的時(shí)間）。則此帶權(quán)的有向圖稱為AOE(activityonedge)網(wǎng)。如果用AOE網(wǎng)來(lái)表示一項(xiàng)工程，通?？梢詮腁OE網(wǎng)中得到：完成預(yù)定工程計(jì)劃所需要進(jìn)行的活動(dòng)；每個(gè)活動(dòng)計(jì)劃完成的時(shí)間；要發(fā)生哪些事件以及這些事件與活動(dòng)之間的關(guān)系。6.7AOE網(wǎng)與關(guān)鍵路徑AOE網(wǎng)表示實(shí)際工程的AOE網(wǎng)應(yīng)該是沒(méi)有回路的有向網(wǎng)，在AOE網(wǎng)中，只有一個(gè)入度為0的頂點(diǎn)（稱為源點(diǎn)）和一個(gè)出度為0的頂點(diǎn)（稱為終點(diǎn)）。如果用AOE網(wǎng)來(lái)表示一項(xiàng)工程，那么需要研究的問(wèn)題是：（1）完成工程至少需要多少時(shí)間?（2）那些活動(dòng)是影響進(jìn)程的關(guān)鍵?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)度的路徑稱為關(guān)鍵路徑。關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)。6.7AOE網(wǎng)與關(guān)鍵路徑關(guān)鍵路徑1.相關(guān)術(shù)語(yǔ)(3)事件的最早發(fā)生時(shí)間ve(i)從源點(diǎn)到頂點(diǎn)i的最大路徑長(zhǎng)度代表的時(shí)間，意味著所有以頂點(diǎn)i為弧尾的活動(dòng)的最早開始時(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)鍵路徑關(guān)鍵路徑1.相關(guān)術(shù)語(yǔ)(4)事件的最遲發(fā)