數(shù)據(jù)結(jié)構(gòu)第七章概況

1、第七章圖7.1圖的概念圖的定義:圖G=(V,E)V是頂點(diǎn)的有窮非空集合。E是偶對(duì)(邊)有窮集合。相關(guān)術(shù)語:頂點(diǎn)、弧、弧頭、弧尾、有向圖、無向圖、無向完全圖、有向完全圖、 稀疏圖、稠密圖、權(quán)、網(wǎng)絡(luò)、鄰接點(diǎn)、度、入度、出度、子圖、路徑、路徑長(zhǎng)度、 連通圖、強(qiáng)連通圖、連通分量、強(qiáng)連通分量、生成樹。| 1|(Vi,Vj)或 <Vi,Vj>是邊| 0(Vi,Vj)或 <Vi,Vj>不是邊若G是網(wǎng)絡(luò)，貝| wij(Vi,Vj)或 <Vi,Vj>是邊或v Vi,Vj 不是邊% (Vi,Vj)7.2圖的存儲(chǔ)1.鄰接矩陣表示法 鄰接矩陣：表示頂點(diǎn)之間相互關(guān)系的矩陣設(shè)G=(V,

2、E)，具有n個(gè)頂點(diǎn)，貝U:是對(duì)稱的，可采用壓縮存儲(chǔ)方法，僅存下三角矩陣(不包Ai,j=|I 0，存儲(chǔ)結(jié)構(gòu):typedef struct char vexs n;adjvex arcs n n; graph;無向圖(網(wǎng)絡(luò))括對(duì)角線)。 創(chuàng)建網(wǎng)絡(luò):CREATGRAPH(graph *ga) int i,j,k;float w;for(i=0;i <n ;i+)ga->vexsi=getchar();for(i=0;i <n ;i+)for(j=0;j< n;j+)ga->arcs n n=0;for(k=0;k< n;k+) sca nf(%d%d%f,&

3、;i,&j,&w); ga->arcsij=w; ga->arcsji=w; 顯然，鄰接矩陣的時(shí)間復(fù)雜度T(n)=O(n 2)顯然，鄰接矩陣的空間復(fù)雜度 T(n)=O(n 2)2. 鄰接表表示法鄰接表：對(duì)G中每個(gè)頂點(diǎn)Vi，把所有鄰接于 V的頂點(diǎn)Vj拉成一個(gè)鏈表，此 表稱Vi的鄰接結(jié)點(diǎn)結(jié)構(gòu)：邊表|adjvex | n ext結(jié)點(diǎn)序號(hào)指針表。頂點(diǎn)表 Vertex | link 頂點(diǎn)信息指針 邊表：無向圖的鄰接表。出邊表：有向圖的鄰接表。入邊表：逆鄰接表。頂點(diǎn)表：鄰接表的表頭向量。結(jié)點(diǎn)定義：typedef struct node int adjvex;struct nod

4、e *n ex t;edge no de;typedef struct node vextype vertex;edge node *li nk;vex no de;vex node ga n;建鄰接表：CREATADJLIST(vex n ode ga)int i,j,k;edge node *s; for(i=0;i< n;i+)/ 頂點(diǎn)信息 ga->vextex=getchar();gai.li nk=NULL; for(k=0;k<e;k+) /建立邊表sca n f(%d%d, & i,&j);s=malloc(sizeof(edge no de);

5、/頭插法s->adjvex=j;s->n ext=gai.li nk;gai.li n k=s;s=malloc(sizeof(edge no de);/頭插法s->adjvex=i;s->n ext=gaj.li nk;gaj.li nk=s;簡(jiǎn)單結(jié)論：一個(gè)圖的鄰接矩陣是唯一的，而鄰接表不唯 每個(gè)邊表對(duì)應(yīng)矩陣的一行或一列，結(jié)點(diǎn)個(gè)數(shù)為非0元素的個(gè)數(shù)。 若G是無向圖，有2e個(gè)邊表結(jié)點(diǎn)。若G是有向圖，有e個(gè)邊表結(jié)點(diǎn)(入邊表或出邊表)。3. 十字鏈表4. 多重鏈表7.3 圖的遍歷圖的遍歷： 從某個(gè)頂點(diǎn)出發(fā)， 沿著某條路徑對(duì)圖中每個(gè)頂點(diǎn)各做一次訪問。 對(duì)于 連通圖， 可一次訪問

6、到所有頂點(diǎn)，而非連通圖，則需多次遍歷。為避免重復(fù)訪問 一個(gè)結(jié)點(diǎn)，可設(shè)一 布爾向量 visitedn 標(biāo)記是否訪問過。1. 深度優(yōu)先搜索 DFS 深度優(yōu)先搜索類似于樹的前序遍歷。 首先，從初態(tài) Vi 出發(fā)，訪問 Vi ， 標(biāo)記已訪問。然后，從 Vi出發(fā)搜索Vi的每一個(gè)鄰接點(diǎn)Vj，若Vj未訪問，則以Vj為新出 發(fā)點(diǎn)繼續(xù)搜索。顯然，上述定義是遞歸的，特點(diǎn)是盡可能對(duì)縱深方向搜索。 遍歷所得到的頂點(diǎn)序列稱 深度優(yōu)先搜索 (DFS 序列。遍歷算法：/ 基于鄰接矩陣的 DFSint visitedn; graph g;void DFS(int i) int j;print(%c,g.vexsi); visi

7、tedi=TRUE;for (j=0;j<n;j+)if (g.arcsij=1)&&(!visitedj)DFSj;/ 基于鄰接表上的 DFSL vexnode g1n;void DFS(int i) int j;edgenode *p; print(%c,g1.vertex) visitedi=TRUE;p=g1i.link;while (p) if (!visitedp->adjvex) DFSL(p->adjvex);p=p->next;算法分析： DFS 算 法T( n)=O(n 廣度優(yōu)先搜索 BFS 廣度優(yōu)先搜索類似于樹的按層遍歷。首先，從初

8、態(tài) Vi 出發(fā)，訪問 Vi ，標(biāo)記已訪問。然后，從 Vi 出發(fā)搜索 Vi 的 所有鄰 接點(diǎn)W1,W2 ; ?Wt,然后，依次訪問與 W1,W2 ; ?Wt鄰接的未訪問過的 頂點(diǎn)。依 此類推顯然，上述方法的特點(diǎn)是盡可能橫向搜索因此稱廣度優(yōu)先搜索 (BFS) 。 遍歷所得到的頂點(diǎn)序列稱廣度優(yōu)先搜索 (BFS 序列。 遍歷算法：需引入一個(gè)隊(duì)列保存)DFSL算法 -T(n)=O(n+e)算法 DFS 和 DFSL 所用的輔助空間是標(biāo)志數(shù)組和實(shí)現(xiàn)遞歸所用的棧， 因此， S(n)=O(n) 。圖的鄰接矩陣是唯一的，所以 DFS 序列是唯一的。 圖的鄰接表不是唯一的， 所以 DFSL 序列不唯一。已訪問過的

9、結(jié)點(diǎn)(W1 ; W2 ;Wt)。/基于鄰接矩陣的 BFSvoid BFS(int k) int i ； j;SETNULL(Q);print(%cn ； g.vexsk) visitedk=TRUE; ENQUEUE(Q ； k); while(!EMPTY(Q) i=DEQUEUE(Q);for (j=0;j<n;j+)if (g.arcsij=1)&&(!visitedj) print(%cn ； g.vexsj); visitedj=TRUE;ENQUEUE(Q ； j);/ 基于鄰接表上的 BFSLvoid BFSL(int k)int i;edgenode *p

10、;SETNULL(Q); print(%cn ； g1k.vertex);visitedk=TRUE;ENQUEUE(Q ； k);while (!EMPTY(Q) i=DEQUEUE(Q); p=g1i.link;while(p) if (!visitedp->adjvex) print(%cn,g1p->adjvex.vertex); visitedp->adjvex=TRUE; ENQUEUE(Q,p->adjvex); p=p->next;算法分析： BFS 算 法T( n)=O(n 2)BFSL算法 -T(n)=O(n+e)算法BFS和BFSL所用的輔助

11、空間是標(biāo)志數(shù)組和實(shí)現(xiàn)算法所需的隊(duì)列，因此，S(n)=O(n) 。圖的鄰接矩陣是唯一的，所以 BFS 序列是唯一的。 圖的鄰接表不是唯一的， 所以 BFSL 序列不唯一 o則從圖中任意一個(gè)頂點(diǎn)出發(fā)都不能訪問到3. 非連通圖的遍歷 若一個(gè)無向圖是非連通圖， 圖中的所有頂點(diǎn)。只能從每個(gè)連通分量中選一個(gè)頂點(diǎn)作為出發(fā)點(diǎn)進(jìn)行搜索， 便可訪問到 非連通圖的所有頂點(diǎn)，因此，需調(diào)用前述的 DFS DFSL 或 BFS BFSL 算法。 /調(diào)用 DFS 的非連通圖的遍歷算法 void TRAVER() int i;for (i=0;i<n;i+)visitedi=FALSE;for (i=0;i<n;

12、i+) if (!visitedi)DFS(i);print(comp endn); 以上討論的遍歷算法對(duì)有向圖也是適用的。7.4 生成樹和最小生成樹樹(tree):在圖中，樹定義為無回路的連通圖。有些圖看起來不是樹，但若選取一個(gè)結(jié)點(diǎn)做根，便轉(zhuǎn)化為樹。生 成 樹：連通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹，則稱該子圖為G的生成樹。簡(jiǎn)單結(jié)論：n個(gè)頂點(diǎn)的連通圖至少有 n-1條邊，一定是無回路的的樹。 生成樹是連通圖的極小 ( 邊數(shù)最少 )連通子圖。 在生成樹中， 去掉任何一條邊則變?yōu)榉沁B通圖， 添加一條邊就必定 出現(xiàn)回路圖 G=(V,E) 是連通圖，如何求得生成樹？在對(duì)G的遍歷中，從Vi出發(fā)

13、搜索到Vj,并訪問。這樣，必經(jīng)過(Vi,Vj),除起點(diǎn)外，對(duì) 其它 n-1 個(gè)頂點(diǎn)的的訪問必經(jīng)過 n-1 條邊。由 n 個(gè)頂點(diǎn)和 n-1 條邊 所構(gòu)成的極小連通子 圖就是一棵生成樹。在遍歷算法中 (DFS DFSL BFS BFSL) 只要將打印稍作改動(dòng)就可得到生成樹 的算法 (將打印語句改成打印邊(Vi,Vj)，分別稱為DFS生成樹BFS生成樹。從圖的遍歷角度而 言，生成樹還可以定義為： 生 成 樹：從圖的某個(gè)頂點(diǎn)出發(fā)，在遍歷時(shí)所經(jīng)過的邊和所有頂點(diǎn)構(gòu)成的子圖，稱作該圖的生成樹。此定義也適用于有向圖。簡(jiǎn)單結(jié)論：若G是非連通圖，則需多次調(diào)用遍歷算法，得到多個(gè)生成樹，組成G的生成森林，分別稱作 D

14、FS 生成森林或 BFS 生成森林。 若 G 是非連通的有向圖，且出發(fā)點(diǎn)又不是有向圖的根，則遍歷時(shí)只 能得到 生成森林。 圖的生成樹不唯一， 從不同頂點(diǎn)出發(fā)， 可得到不同的生成樹。 最小生成樹：連通網(wǎng)絡(luò)G=(V,E)邊是帶權(quán)的，我們把生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)值最小的生成樹稱為 G 的最小生成樹 (Minimun Spanning Tree) 。典型應(yīng)用： n 個(gè)城市的通訊網(wǎng)絡(luò)問題？把 n 個(gè)城市連接起來至少要有 n-1 條線路 把 n 個(gè)城市連接起來最多要 n(n-1)/2 條線路。如果用權(quán)代表兩城市之間的線路長(zhǎng)度或造價(jià)，那么，顯然要選擇 n-1 條線路使 得線路總長(zhǎng)最短或造

15、價(jià)最低。這就勢(shì)必要構(gòu)造該圖的一棵最小生成樹。 構(gòu)造最小生成樹的普里姆 (Prim) 算法和克魯斯卡爾 (Kruskal) 算法：Prim 算法： 設(shè) G=(V,E) ， T=(U,TE) 置T為任意一個(gè)頂點(diǎn)U=uO，置初始候選邊集，即關(guān)聯(lián)于 uO的邊(另一 端在 V 里) while仃中頂點(diǎn)數(shù)v n) 從候選邊集中選取最短的邊 (u,v) ； 將(u,v)擴(kuò)充到T中，v也擴(kuò)充到T中； 調(diào)整候選的短邊集；改進(jìn)算法： 設(shè) T 中有 k 個(gè)頂點(diǎn)，則候選邊數(shù) k(n-k) ，不適于全部搜索。只需將 n-k 個(gè)? V 的點(diǎn)關(guān)聯(lián)的邊作候選邊集即可。結(jié) 論：連通網(wǎng)絡(luò)的最小生成樹不一定是唯一的， 對(duì)于權(quán)值相等

16、的候選邊， 可 任選一短邊 擴(kuò)充到 T 中，但它們的權(quán)值總和是相等的。 Prim 算法適合于求稠密 網(wǎng)的最小生成樹。存儲(chǔ)結(jié)構(gòu)： typedef struct / int生成樹格式fromvex,endvex;/ float length; /起點(diǎn)、終點(diǎn) edge;權(quán)值float distnn; edge Tn-1;/生成樹 n-1 條邊算法實(shí)現(xiàn)：T( n)=O(n 2)/Prim算法求最小生成樹#in clude<iostream.h>#in clude<stdio.h>結(jié)點(diǎn)數(shù)#defi ne n 6/邊數(shù)#defi ne e 10/typedef int vextyp

17、e;typedef int adjtype;vextype vexs n; /頂點(diǎn)集adjtype arcs nn; /鄰接矩陣typedef struct / int生成樹格式fromvex,e ndvex;int len gth; edge;edge Tn-1; /生成樹n-1條邊void CREATGRAPH() /建立連通網(wǎng)絡(luò) int i,j,k,w;cout<<"請(qǐng)輸入六個(gè)結(jié)點(diǎn):"<<e ndl;for(i=0;i <n ;i+)cin> >vexsi;cout<<"輸入完畢"<<

18、;endl;for(i=0;i <n ;i+)for(j=0;j< n;j+)arcsij=10000; /沒有權(quán)值應(yīng)為無窮大coutvv"請(qǐng)輸入起點(diǎn),終點(diǎn),權(quán)值"<<e ndl;for(k=0;k<e;k+) cin>>i> >j>>w;/無向圖arcsij=w;arcsji=w; cout<<endl;void PRIM() int j,k,m,v,mi n,max=10000;int d;edge f;for(j=1;j<n;j+) / 構(gòu)造初始候選邊集 Tj-1.fromvex=0;

19、Tj-1.e ndvex=j;Tj-1.le ngth=arcs0j;for(k=0;k<n-1;k+) / min=max;for(j=k;j<n-1;j+) /if (Tj.length<min) min=Tj.length;m=j; f=Tm;Tm=Tk;Tk=f; v=Tk.endvex; for(j=k+1;j<n-1;j+) / d=arcsvTj.endvex; if(d<Tj.length) Tj.length=d; Tj.fromvex=v;求第 k 條邊找最短紫邊調(diào)整候選邊集還剩 n-k-2 條邊void main()CREATGRAPH();

20、PRIM();for(int t=0;t<n-1;t+) cout<<Tt.fromvex<<Tt.endvex<<Tt.length<<endl;Kruskal 算法：設(shè) G=(V,E) ，T=(U,TE) 置 T=(V, ) 將 G 中所有的邊按遞增排序。 依次將E中的一條邊(u,v)加入T中，從E中刪去(u,v)。 加入(u,v)不產(chǎn)生回路，則將(u,v)并入T中，否則舍棄。 重復(fù)。結(jié) 論：連通網(wǎng)絡(luò)的最小生成樹不一定是唯一的， 對(duì)于權(quán)值相等的候選邊， 可 任選一短邊 擴(kuò)充到 T 中，但它們的權(quán)值總和是相等的。 Kruskal 算法適合

21、于求稀 疏網(wǎng)的最小生成樹。存儲(chǔ)結(jié)構(gòu)： typedef struct /邊的信息 int head,tail;/起點(diǎn)、終點(diǎn)float lowcost /權(quán)值 edge;edge Edgearcnum; /邊集int VexsetMVnum; /并查集整形數(shù)組 VexsetMVnum ：標(biāo)識(shí)各個(gè)頂點(diǎn)所屬的連通分量。初始時(shí) Vexseti=i ，表示各頂點(diǎn)自成一個(gè)連通分量。算法思想： 將數(shù)組 Edge 中的元素按權(quán)值從小到大排序。 依次從排序好的數(shù)組 Edge 中選出一條邊 (v1,v2) ，在 Vexset 中分 別查找 v1 和 v2 所在的連通分量 vs1 和 vs2。?如果 VS1 和 VS

22、2 不等，表明所選的兩個(gè)頂點(diǎn)分屬不同的連通分量，輸出此邊，并合并 vs1 和 vs2 兩個(gè)連通分量。?如果 VS1 和 VS2 相等，表明所選的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量， 舍去 此邊，選擇下一條權(quán)值最小的邊。 重復(fù)，直至Edge中所有的邊都掃描判斷完，并且所有頂點(diǎn)都在同一個(gè)連通分量上。算法實(shí)現(xiàn)： T(n)=O(eloge)/KruSkal 算法求最小生成樹無向網(wǎng)絡(luò)G以鄰接矩陣存儲(chǔ)，構(gòu)造 G的最小生成樹T,輸出T的各個(gè)條邊Void MiniSpanTree_KruSkal(AMGGraph G)Sort(Edge); II將數(shù)組 Edge 中的元素按權(quán)值從小到大排序for(i=0;i<G

23、.Vexnum;i+)VexSeti=i; II表示各頂點(diǎn)自成一個(gè)連通分量for(i=0;i<G.arcnum;i+) v 仁 Locate(G,Edgei.Head); IIv1V2=Locate(G,Edgei.Tail); IIV2 vS1=VexSetv1;IIvS2=VexSetv2;II為邊的始點(diǎn) Head 的下標(biāo) 為邊的終點(diǎn) Tail 的下標(biāo) 獲取邊 Edgei 的始點(diǎn)所在的連通分量 獲取邊 Edgei 的終點(diǎn)所在的連通分量if (vS1!=vS2) cout<<Edgei.Head<<Edgei.Tail<<Edgei.lowcoSt&

24、lt;<endl;II輸出此邊f(xié)or(i=0;i<G.vexnum;i+)if (VexSeti)=vS2) VexSeti)=vS1;II合并 vS1 和 vS2 兩個(gè)分量，即將兩個(gè)集合II統(tǒng)一編號(hào)，將集合編號(hào) vS2 的都改為 vS1其它方法：破圈法， Solin 算法， DijkStra 算法7.5 最短路徑 這里的路徑長(zhǎng)度不是路徑上邊的數(shù)目，而是路徑上權(quán)值的總和。 習(xí)慣稱開 始點(diǎn)源點(diǎn)，最后一個(gè)頂點(diǎn)終點(diǎn)。1. 單源最短路徑對(duì)于給定的有向網(wǎng)絡(luò) G=(V,E)及單個(gè)源點(diǎn)V,求從V到其余各頂點(diǎn)的路徑。 例圖：總 結(jié)： 最短路徑不一定是邊數(shù)最小。若按長(zhǎng)度遞增的順序生成 V 到其它頂點(diǎn)

25、的最短路徑，則當(dāng)前正在生 成的路 徑上除終點(diǎn)外，其余頂點(diǎn)的最短路徑已生成。迪杰斯特拉算法 ( Dijkstra ) ：基本思想：設(shè)置并逐步擴(kuò)充一個(gè)集合 S,存放最短路徑的頂點(diǎn)，則尚未確定的頂 點(diǎn)集是V-S。 置 S 為僅有源點(diǎn)的集合 while (S中頂點(diǎn)數(shù)v n)在V-S中選最短路徑長(zhǎng)度的 K擴(kuò)充到S中；基本問題： 如何在藍(lán)集中選擇藍(lán)點(diǎn) k 來擴(kuò)充紅點(diǎn)集？ 為此，需定義一個(gè)數(shù)組 Dn 來存放 各頂點(diǎn)的距離值，顯然每個(gè)紅點(diǎn)的 Dn 就是該點(diǎn)的最短路徑長(zhǎng)度，而藍(lán)點(diǎn)不一定。可以證明：若當(dāng)前藍(lán)點(diǎn)集中具有最小距離值的藍(lán)點(diǎn)是k,則其Dk-1是K的最短路徑長(zhǎng)度，并且 k 是最短的頂點(diǎn)。算法求精：S=V;

26、置初始藍(lán)點(diǎn)集中各藍(lán)點(diǎn)的距離值 while （S中的紅點(diǎn)數(shù) v n）在藍(lán)集中選擇距離最小的 k;S=S+k;調(diào)整剩余藍(lán)點(diǎn)的距離值；如何調(diào)整： 調(diào)整 Dn 的值： 對(duì)藍(lán)點(diǎn)集掃描檢查，若某藍(lán)點(diǎn) j 的原距離值 Dj-1 大于新路 徑的長(zhǎng)度Dk-1+邊v k,j 上的權(quán)，則將Dj-1修改為此長(zhǎng)度值。例 圖： 算法描述： Dn 各頂點(diǎn)的距離值Pn 路徑向量 Pi-1 源點(diǎn)到 i 最短路徑上的前趨Sn 卜一紅點(diǎn)集即進(jìn)入 S 集的頂點(diǎn)。float Dn;/頂點(diǎn)的距離值int Pn,Sn;/路徑、紅點(diǎn)集void DIJKSTRA(float Cn,int v) int i,j,k,v1,pre;int nin

27、,max=6000,inf=8000;v1=v-1;for(i=0;i<n;i+)/置初始距離值 Di=Cv1i;if (Di!=max) Pi=v;else Pi=0;for(i=0;i<n;i+)/置紅點(diǎn)集為空Si=0;Sv1=1;Dv1=0for(i=0;i<n-1;i+)/擴(kuò)充紅點(diǎn)集合 min=inf;for(j=0;j<n;j+)if (!Sj)&&(Dj<min) min=Dj;k=j;Sk=1; / 將 k+1 加入紅點(diǎn)集for(j=0;j<n;j+) / 調(diào)整藍(lán)點(diǎn)的距離值if (!Sj)&&(Dj)>Dk

28、+Ckj) Dj=Dk+Ckj;Pj=k+1;for(i=0;i<n;i+) / 打印結(jié)果 print(%fn%d,Di,i+1);pre=Pi;while(pre!=0) print( %d,pre);pre=Ppre-1; 算法優(yōu)化：一旦當(dāng)藍(lán)點(diǎn)集中所有藍(lán)點(diǎn)的距離值均為 max 則表示這些藍(lán)點(diǎn)的最短 路徑均不存在， 因此無需再將它們擴(kuò)充到紅點(diǎn)集， 這樣，可在把 K 加入紅點(diǎn)集之 前判斷 Dk-1或min是否等于max '若是，推出擴(kuò)充紅點(diǎn)集的循環(huán)，打印結(jié)果。算法分析：T(n)=O(n 2) S(n)=O(n)2. 所有頂點(diǎn)之間的最短路徑我們可以依次把有向網(wǎng)絡(luò)的每個(gè)頂點(diǎn)作為源點(diǎn)，

29、重復(fù)執(zhí)行 D 算法 n 次，即可求得，其 T(n)=O(n 3)費(fèi)洛伊德算法： 仍米用鄰接矩陣 C 表示有向網(wǎng)絡(luò)當(dāng) <i,j> 不存在時(shí) Ci-1j-1=max 當(dāng) i=j 時(shí) Ci-1j-1=0 T(n)=O(n3)直觀分析：若有 <i,j> ，則長(zhǎng)度為 Ci-1j-1 ，但并不一定最短，因?yàn)榭赡艽?在一條從 i 至叮， 但中間包含其它頂點(diǎn)的路徑，因此我們要考察i 至叮是否有以頂點(diǎn)1,2,n為中間點(diǎn)的更短路徑。算法關(guān)鍵： 要保留每一步所求得的，所有頂點(diǎn)之間的當(dāng)前最短路徑，設(shè)一個(gè) nxn 的方陣序 列 A0,A1, ,An 來保存當(dāng)前求得的最短路徑，特別 AO=C,An

30、 即最短路徑 長(zhǎng)度?；舅枷耄簭?A0開始，遞推生成序列 A1,A2,An 遞推公式：A0ij=Cij Ak+1ij=min Akij,Akik+Akkj具體算法：僅用A來保存當(dāng)前最短路徑長(zhǎng)度，還須設(shè)置路徑矩陣pathnn在k+1次送代中 pathij 是 i 到 j 序號(hào)不大于 k+1 的最短路徑上頂點(diǎn) i 的后繼。 int pathnn; void FLOYD(float An,float Cn)/迭代矩陣、有向網(wǎng)絡(luò) int i,j,k,next;int max= g; for(i=0;i<n;i+) for(j=0;j<n;j+) if (Cij!=max) pathij=j

31、+1;else pathij=0;Aij=Cij;for(k=0;k<n;k+) for(i=0;i<n;i+) for(j=0;j<n;j+)if (Aij>Aik+Akj) Aij=Aik+Akj pathij=pathik;for(i=0;i<n;i+)for(j=0;j<n;j+) print(%f,Aij);next=pathij;if (next=0)print(%dto%d no path.n,i+1,j+1); else print(%d,i+1);while(next!=j) print( %d,next); next=pathnextj;

32、print( %d,j+1);7.6 拓?fù)渑判?一個(gè)大的工程常常被劃分成許多小的子工程， 這些子工程稱活動(dòng)， 當(dāng)這些 子 工程順利完成時(shí)，整個(gè)工程也就完成了。例 如：AOV 網(wǎng)：頂點(diǎn)活動(dòng)網(wǎng)。我們將頂點(diǎn)表示活動(dòng)，邊表示先后關(guān)系，這樣的有向圖 稱 AOV 網(wǎng)。拓?fù)渑判颍涸贏OV網(wǎng)中拓?fù)湫蛄蠽i1,Vi2,Vin滿足V到Vj有路徑，則Vi必在Vj之前， 把 AOV 網(wǎng)構(gòu)造拓?fù)湫蛄械牟僮鞣Q為拓?fù)渑判?。?jiǎn)單結(jié)論： 1.A0 V 網(wǎng)的一個(gè)拓?fù)湫蛄惺谴泄こ掏瓿傻囊环N可行方案。2. 若網(wǎng)中存在回路，則找不到該網(wǎng)的拓?fù)湫蛄?，這種現(xiàn)象稱死鎖。3. 任何無回路的 AOV 網(wǎng)都可排成一個(gè)拓?fù)湫蛄?，但可能不唯一。?

33、法：1. 從網(wǎng)中選擇一個(gè)入度為 0 的頂點(diǎn)且輸出之；2. 從網(wǎng)中刪掉此頂點(diǎn)及所有出進(jìn)3. 反復(fù)執(zhí)行 1,2 直至所有頂點(diǎn)已輸出， 此時(shí)整個(gè)拓?fù)湫蛄幸淹瓿桑换?者直到余留在網(wǎng)中的頂點(diǎn)入度都不為 0 為止，說明網(wǎng)中存在回路， 拓?fù)湫蛄胁淮?在。例 如： 存儲(chǔ)結(jié)構(gòu)： 鄰接表 +頂點(diǎn)表中入度域 id 算法描述： 在具體實(shí)現(xiàn)時(shí)，上述鏈棧無需占用額外空間，而利用頂點(diǎn)表中值為 0 的入度域 存放指針， 用頂點(diǎn)存放鏈棧的頂點(diǎn)域， 即靜志鏈表， 入棧時(shí)只須修改指 針。 算法實(shí)現(xiàn)： 算法分析： T(n)=O(n+e)另 夕卜：對(duì)于一個(gè)無回路的 AOV 網(wǎng)，也可以利用 DFS 進(jìn)行拓?fù)渑判?，為此，?設(shè)置一個(gè)棧 S

34、, 在遍歷過程中，訪問某頂點(diǎn)時(shí)，就將它壓入棧中，直到從該頂點(diǎn)出發(fā)的搜索過程結(jié)束，才把它從棧 S 中彈出并輸出之。雖然，最先退棧的頂點(diǎn)， 其出度為 0.它是拓 撲序列地 最后一個(gè)頂點(diǎn)，而當(dāng)頂點(diǎn) Vi 從棧頂彈出時(shí)，認(rèn) Vi 為起點(diǎn)的邊， 其終點(diǎn) Vj 都 已出棧， 即相當(dāng)于刪去了 Vi 的所有出邊 <Vi,Vj>, 此時(shí) 出棧的頂點(diǎn) Vj 的出度要為零。由 此，按此種方法輸出地頂點(diǎn)序列恰為一個(gè)逆向 的拓?fù)湫蛄小?.7 關(guān)鍵路徑AOE 網(wǎng)：是一個(gè)帶權(quán)的有向圖，頂點(diǎn)表示事件，邊表示活動(dòng)，權(quán)表示活動(dòng)持續(xù) 時(shí)間。頂 點(diǎn)所表示的時(shí)間實(shí)際上就是它的入邊所表示的活動(dòng)已完成， 它的出邊所 表示的活動(dòng)可以開 始。通常：可用 AOE 網(wǎng)來估算工程計(jì)劃的完成時(shí)間。 AOE 網(wǎng)應(yīng)該是無回路的，且網(wǎng)中只有一個(gè)入度為 0 的頂點(diǎn) ( 源點(diǎn))和一個(gè)出度為 0 的頂點(diǎn) (匯點(diǎn) )。例圖：研究問題： 1.完成整個(gè)工程至少需要多少時(shí)間？2. 哪些活