基于路径分解的关键路径算法.doc

《基于路径分解的关键路径算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于路径分解的关键路径求解方法关键路径的求解方案可描述为：1）对AOE网进行拓扑排序，若成功，则得出其拓扑有序序列；2）利用拓扑有序序列的逆序，从汇点开始进行逆向的路径分解，直到所有路径全部分解完毕；3）从所有可能路径中挑选出其中路径长度最长的路径，即关键路径。算法设计的关键在于如何实现路径的分解并保存所有路径。根据AOE网的特点，可以设计一个多头单尾链表结构来处理。算法设计思想可描述如下：1）建立图的扩展邻接表存储结构；2）进行拓扑排序，并利用栈保存其拓扑有序序列；3）利用拓扑有序序列的逆序，创建一个多头单尾

2、链表，求出所有可能的路径；4）挑选出其中路径长度最长的路径，即关键路径。完整的程序清单：#include#include#defineN20#defineERROR0#defineOK1#defineM5typedefstructedgenode{/*图的邻接表：邻接链表结点*/intadjvex;/*顶点序号*/intweight;/*对应边的权值*/structedgenode*next;/*下一个结点的指针*/}edgenode;typedefstructvnode{

3、/*图的邻接表：邻接表表头结点*/intdata;/*顶点信息*/intind;/*顶点入度*/structedgenode*link;/*指向邻接链表的指针*/}vnode;typedefstructALgraph{/*图的邻接表：邻接表*/intvexnum,arcnum;/*顶点信息*/vnodeadjlist[N];/*顶点入度*/}ALgraph;typedefstructpnode{/*图的多头单尾链表表头结点*/intpathlength;/*路径长度*/structedgenode*link;/

4、*指向多头单尾链表结点的指针*/}pnode;typedefintElemType;/*定义元素的类型*/typedefstruct{ElemType*base;ElemType*top;intstacksize;/*当前已分配的存储空间*/}SqStack;intInitStack(SqStack*S){S->base=(ElemType*)malloc(N*sizeof(ElemType));if(!S->base)returnERROR;S->top=S->base;S->stacksize=N;retu

5、rnOK;}/*InitStack*/intStackEmpty(SqStack*S){if(S->top==S->base)returnOK;elsereturnERROR;}intPush(SqStack*S,ElemTypee){if(S->top-S->base>=S->stacksize){S->base=(ElemType*)realloc(S->base,(S->stacksize+M)*sizeof(ElemType));if(!S->base)returnERROR;S->top=S->bas

6、e+S->stacksize;S->stacksize+=M;}*S->top++=e;returnOK;}/*Push*/intPop(SqStack*S,ElemType*e){if(S->top==S->base)returnERROR;*e=*--S->top;returnOK;}/*Pop*/voidcreateGraph_list(ALgraph*g);/*建立有向图的邻接表*/voidCri_path(ALgraph*g);/*拓扑排序和关键路径求解*/voidcreateGraph_list(A

7、Lgraph*g){/*建立有向图的邻接表*/inti,j,n,e;charv;edgenode*s;i=0;n=0;e=0;printf("输入顶点序列(以#结束)：");while((v=getchar())!='#'){g->adjlist[i].data=v;/*读入顶点信息*/g->adjlist[i].link=NULL;g->adjlist[i].ind=0;i++;}n=i;g->vexnum=n;printf("请输入弧的信息(i=-1结束)：i,j:");/*建立邻接链表*/sc

8、anf("%d,%d",&i,&j);while(i!=-1){s=(structedgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=g->adjlist[i].link;g->adjlist[i].link=s;g->adjlist[j].ind++;/*顶点j的入度加1*/e++;scanf("%d,%d",&i,&j);}