学妹，你要的C语言版AOE网络数据结构来了，就这么简单！

骑猪看日落 2022-10-05 15:43 20阅读 0赞

### 文章目录 ###

*  AOE关键路径编程
 *  AOE完整求解程序

# AOE关键路径编程 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2t5NTEyMjI_size_16_color_FFFFFF_t_70_pic_center]  
不难发现AOE图最大特点是没有回路，并且有向图方向始终是从源点走向汇点，且源点汇点都是一个。

把图1写成邻接矩阵文件，见文件P200G736.TXT，并在此复制G0.C到AOE.C，修改这个程序的读文件名称，使其正确读出该文件的数据并构造图。

分析图1可知，该图实际有以下路径：

> 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条路径上面的权值和最大者就是关键路径。

很明显，把上述5条路径的V1合并成一个结点，则可以看这个结果实际是一个生成树，这个生成树上的结点或许是重复的，但要全部走完，则结果肯定是这样的一棵树，这样的树我们这里成为全路径生成树，或许N多教材没这个称谓，但要编程求解该问题则必然是要先解出该树来、然后累计求和每个子树上的权值和。

C\#的程序上很容易做到这个树，这个解就是：

![在这里插入图片描述][20210609232528839.png_pic_center]

这样的树，实际是一种特殊的深度优先遍历生成的结果。

回顾我们在普通的图上做的深度优先遍历，由于一般意义上的图中存在回路，所以我们需要一个Visited\[\]这样的数组、标记已经走过的顶点，从而制止了在一个回路上无限循环，但我们分析AOE图则不难发现：我们不需要标记已经走过的顶点，深度优先遍历也可以顺利从源点到汇点走完。

手工完成这样的遍历不是问题，所以我们可以编写出以下的程序来遍历：

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);
    }

对照我们前面的深度优先遍历函数：

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);
    }

执行AOE1.c程序，则结果是：

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

分析表1的程序以及结果不难发现：

<1> 如AOETrav( )函数入口参数n是生成树父结点的话、那么在第8行进入下一个顶点时所找到的第i个顶点、则就是第n个结点的孩子；

<2> 如果设到第n个结点的权值累计合是w，则该函数就是这样的入口参数：

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

有这样的函数后，则在表1的第9行就是：

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

也就是说：到第n个顶点的权值如果是w的话，则到第n个后的第i个顶点，其权值合计是:

w+A[n][i];

然后，我们设计一个双亲表示法的表格，按：  
![在这里插入图片描述][20210609232653169.png_pic_center]

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()函数，使其从第0个顶点开始，就是：

main()
    { 
    	int i,j;
    	struct Stack *S;
    	struct Graph *G;
    	G=GraphCreat("p200G736.txt");
    	printf("顶点名称:\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);
    }

运行这个程序，会有以下结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2t5NTEyMjI_size_16_color_FFFFFF_t_70_pic_center 1]  
至此，AOE的问题基本解决，查看表6，其最大权值是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，`全路程权值合计是18

同理在第6行也有一条路径：

`V1、V3、V5、V8、V9`，全路程权值和也是18，这也是一条关键路径。

表6需要注意的是：由于这个树上、一个结点可能出现在好几个子树上，所以父结点编号要寻找上面最近的结点编号。

# AOE完整求解程序 #

上述解法、对小的AOE图是可行的，但在大的图上，很明显对表6也需要进行编程处理，所以一个完整的AOE处理程序，还需要设计一个顺序表、保存表6的结果，然后通过顺序表求解出完整的计算结果。这个工作就留给同学们自己解决。

AOE2.c是通过一种简单的方式、把各个路径上的权值累计合计和路径显示出来的程序，请同学们自己分析。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2t5NTEyMjI_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/d7e222c275a049dfb34c933f3a8593ac.png
[20210609232528839.png_pic_center]: /images/20221005/b8a495011067421cade6d1d8d2231a13.png
[20210609232653169.png_pic_center]: /images/20221005/4fddd6787a404c319e97510eeb4ddbc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2t5NTEyMjI_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/e134ff2099034bf598189e78333905bc.png