道路建设网站专题,广告公司名字怎么起,net网站开发找那家,小程序代理哪家好文章目录AOE关键路径编程AOE完整求解程序AOE关键路径编程 不难发现AOE图最大特点是没有回路#xff0c;并且有向图方向始终是从源点走向汇点#xff0c;且源点汇点都是一个。
把图1写成邻接矩阵文件#xff0c;见文件P200G736.TXT#xff0c;并在此复制G0.C到AOE.C#x…
文章目录AOE关键路径编程AOE完整求解程序AOE关键路径编程 不难发现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#的程序上很容易做到这个树这个解就是 这样的树实际是一种特殊的深度优先遍历生成的结果。
回顾我们在普通的图上做的深度优先遍历由于一般意义上的图中存在回路所以我们需要一个Visited[]这样的数组、标记已经走过的顶点从而制止了在一个回路上无限循环但我们分析AOE图则不难发现我们不需要标记已经走过的顶点深度优先遍历也可以顺利从源点到汇点走完。
手工完成这样的遍历不是问题所以我们可以编写出以下的程序来遍历
void AOETrav (struct Graph *G,int n)
{int i;if(GNULL) return;printf(%d\t%s\n,n,G-pV[n]);for(i0;iG-num;i)if(G-pA[n][i]!0)AOETrav(G,i);
}
对照我们前面的深度优先遍历函数
void DFS(struct Graph *G,int n)
{int i;if(GNULL) return;if(n0||nG-num) return;G-Visited[n]1;printf(%s ,G-pV[n]); for(i0;iG-num;i)if(G-pA[n][i]!0G-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, wG-pA[n][i]);也就是说到第n个顶点的权值如果是w的话则到第n个后的第i个顶点其权值合计是:
wA[n][i];然后我们设计一个双亲表示法的表格按
void AOETrav (struct Graph *G,int n,int w)
{int i,nw;if(GNULL) return;for(i0;iG-num;i)if(G-pA[n][i]!0){nwwG-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;GGraphCreat(p200G736.txt);printf(顶点名称:\n);for(i0;iG-num;i)printf(%s\t,G-pV[i]);printf(\n邻接矩阵:\n);for(i0;iG-num;i) {for(j0;jG-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);
}运行这个程序会有以下结果 至此AOE的问题基本解决查看表6其最大权值是18见上表第4行、第6行如是第4行则是V9回溯PID6到第3行V7、从V7取PID4回到第2行V5、再从PID1回到V2、从V2取PID0回到V1全路程就是
V1、V2、V5、V7、V9全路程权值合计是18
同理在第6行也有一条路径
V1、V3、V5、V8、V9全路程权值和也是18这也是一条关键路径。
表6需要注意的是由于这个树上、一个结点可能出现在好几个子树上所以父结点编号要寻找上面最近的结点编号。
AOE完整求解程序
上述解法、对小的AOE图是可行的但在大的图上很明显对表6也需要进行编程处理所以一个完整的AOE处理程序还需要设计一个顺序表、保存表6的结果然后通过顺序表求解出完整的计算结果。这个工作就留给同学们自己解决。
AOE2.c是通过一种简单的方式、把各个路径上的权值累计合计和路径显示出来的程序请同学们自己分析。
