文章目錄

• AOE關(guān)鍵路徑編程
• AOE完整求解程序

AOE關(guān)鍵路徑編程

不難發(fā)現(xiàn)AOE圖最大特點(diǎn)是沒有回路，并且有向圖方向始終是從源點(diǎn)走向匯點(diǎn)，且源點(diǎn)匯點(diǎn)都是一個(gè)。

把圖1寫成鄰接矩陣文件，見文件P200G736.TXT，并在此復(fù)制G0.C到AOE.C，修改這個(gè)程序的讀文件名稱，使其正確讀出該文件的數(shù)據(jù)并構(gòu)造圖。

分析圖1可知，該圖實(shí)際有以下路徑：

V1->V2->V5->V7->V9;
V1->V3->V5->V7->V9;
V1->V2->V5->V8->V9;
V1->V3->V5->V8->V9;
V1->V4->V6->V8->V9;

一共是5條路徑，這5條路徑上面的權(quán)值和最大者就是關(guān)鍵路徑。

很明顯，把上述5條路徑的V1合并成一個(gè)結(jié)點(diǎn)，則可以看這個(gè)結(jié)果實(shí)際是一個(gè)生成樹，這個(gè)生成樹上的結(jié)點(diǎn)或許是重復(fù)的，但要全部走完，則結(jié)果肯定是這樣的一棵樹，這樣的樹我們這里成為全路徑生成樹，或許N多教材沒這個(gè)稱謂，但要編程求解該問題則必然是要先解出該樹來、然后累計(jì)求和每個(gè)子樹上的權(quán)值和。

C#的程序上很容易做到這個(gè)樹，這個(gè)解就是：

這樣的樹，實(shí)際是一種特殊的深度優(yōu)先遍歷生成的結(jié)果。

回顧我們在普通的圖上做的深度優(yōu)先遍歷，由于一般意義上的圖中存在回路，所以我們需要一個(gè)Visited[]這樣的數(shù)組、標(biāo)記已經(jīng)走過的頂點(diǎn)，從而制止了在一個(gè)回路上無限循環(huán)，但我們分析AOE圖則不難發(fā)現(xiàn)：我們不需要標(biāo)記已經(jīng)走過的頂點(diǎn)，深度優(yōu)先遍歷也可以順利從源點(diǎn)到匯點(diǎn)走完。

手工完成這樣的遍歷不是問題，所以我們可以編寫出以下的程序來遍歷：

void AOETrav (struct Graph *G,int n) {int i;if(G==NULL) return;printf("%d\t%s\n",n,G->pV[n]);for(i=0;i<G->num;i++)if(G->pA[n][i]!=0)AOETrav(G,i); }

對照我們前面的深度優(yōu)先遍歷函數(shù)：

void DFS(struct Graph *G,int n) {int i;if(G==NULL) return;if(n<0||n>G->num) return;G->Visited[n]=1;printf("%s ",G->pV[n]); for(i=0;i<G->num;i++)if(G->pA[n][i]!=0&&G->Visited[i]!=1) DFS(G,i); }

執(zhí)行AOE1.c程序，則結(jié)果是：

V1、 V2、V5、V7、 V9、V8、V9、V3、V5、V7、V9、 V8、V9、V4、V6、V8、V9

分析表1的程序以及結(jié)果不難發(fā)現(xiàn)：

<1> 如AOETrav( )函數(shù)入口參數(shù)n是生成樹父結(jié)點(diǎn)的話、那么在第8行進(jìn)入下一個(gè)頂點(diǎn)時(shí)所找到的第i個(gè)頂點(diǎn)、則就是第n個(gè)結(jié)點(diǎn)的孩子；

<2> 如果設(shè)到第n個(gè)結(jié)點(diǎn)的權(quán)值累計(jì)合是w，則該函數(shù)就是這樣的入口參數(shù)：

void AOETrav (struct Graph *G,int n,int w)

有這樣的函數(shù)后，則在表1的第9行就是：

AOETrav(G,i, w+G->pA[n][i]);

也就是說：到第n個(gè)頂點(diǎn)的權(quán)值如果是w的話，則到第n個(gè)后的第i個(gè)頂點(diǎn)，其權(quán)值合計(jì)是:

w+A[n][i];

然后，我們設(shè)計(jì)一個(gè)雙親表示法的表格，按：

void AOETrav (struct Graph *G,int n,int w) {int i,nw;if(G==NULL) return;for(i=0;i<G->num;i++)if(G->pA[n][i]!=0){nw=w+G->pA[n][i]; printf("%d\t%d\t%s\t%d\n",i,n,G->pV[i],nw);AOETrav(G,i,nw);} }

修改main()函數(shù)，使其從第0個(gè)頂點(diǎn)開始，就是：

main() {int i,j;struct Stack *S;struct Graph *G;G=GraphCreat("p200G736.txt");printf("頂點(diǎn)名稱:\n");for(i=0;i<G->num;i++)printf("%s\t",G->pV[i]);printf("\n鄰接矩陣:\n");for(i=0;i<G->num;i++) {for(j=0;j<G->num;j++)printf("%d\t",G->pA[i][j]);printf("\n");}printf("\n");printf("ID\tPID\tV\tW\n");printf("%d\t%d\t%s\t%d\n",0,-1,G->pV[0],0);AOETrav(G,0,0); }

運(yùn)行這個(gè)程序，會有以下結(jié)果：

至此，AOE的問題基本解決，查看表6，其最大權(quán)值是18，見上表第4行、第6行，如是第4行，則是V9，回溯PID=6到第3行V7、從V7取PID=4回到第2行V5、再從PID=1回到V2、從V2取PID=0回到V1，全路程就是：

V1、V2、V5、V7、V9，全路程權(quán)值合計(jì)是18

同理在第6行也有一條路徑：

V1、V3、V5、V8、V9，全路程權(quán)值和也是18，這也是一條關(guān)鍵路徑。

表6需要注意的是：由于這個(gè)樹上、一個(gè)結(jié)點(diǎn)可能出現(xiàn)在好幾個(gè)子樹上，所以父結(jié)點(diǎn)編號要尋找上面最近的結(jié)點(diǎn)編號。

AOE完整求解程序

上述解法、對小的AOE圖是可行的，但在大的圖上，很明顯對表6也需要進(jìn)行編程處理，所以一個(gè)完整的AOE處理程序，還需要設(shè)計(jì)一個(gè)順序表、保存表6的結(jié)果，然后通過順序表求解出完整的計(jì)算結(jié)果。這個(gè)工作就留給同學(xué)們自己解決。

AOE2.c是通過一種簡單的方式、把各個(gè)路徑上的權(quán)值累計(jì)合計(jì)和路徑顯示出來的程序，請同學(xué)們自己分析。

總結(jié)

以上是生活随笔為你收集整理的学妹，你要的C语言版AOE网络数据结构来了，就这么简单！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。