关键 路径代码算法.docx

#include#include#define stack_max_size 100#define stack_extra 10typedef structint *top;int *base;int stacksize;vexstack,*pvexstack;int initstack(vexstack &st)st.base =(int *)malloc(stack_max_size*sizeof(int);if(!st.base )exit(0);st.top =st.base ;st.stacksize =stack_max_size;return 1;int pop(vexstack &st,int &a)if(st.top=st.base)return 0;a=*(-st.top);return 1;int push(vexstack &st,int a)if(st.top -st.base =st.stacksize )st.base =(int*)realloc(st.base ,(stack_max_size+stack_extra)*sizeof(int);if(!st.base )exit(0);st.top=st.base+st.stacksize;st.stacksize+=stack_extra;*st.top+=a;return 1;int destroystack(vexstack &st)free(st.base );return 1;int emptystack(vexstack st)if(st.top =st.base)return 1;else return 0;typedef struct narc int adjvex; int info;narc,*pnarc;typedef struct headvexterint indegree;int kaiguan;int outdegree; char data;pnarc outarc;headvexter,* pheadvexter;typedef structint vexnum;pheadvexter vexs;graph,*pgraph;void initgraph(graph &G)int i=0,j,k=0,n,l=0;char c100;printf(请输入有向图的节点：n); gets(c);while(ci!=0) i+;G.vexnum=i;G.vexs=(pheadvexter)malloc(i+1)*sizeof(headvexter);i=0;while(ci!=0) G.vexsi+1.data =ci;G.vexsi+1.kaiguan=0;i+; n=i;for(j=1;j=n;j+)printf(请输入节点%c的入度：,G.vexsj.data);scanf(%d,&G.vexsj.indegree);printf(请输入节点%c的出度：,G.vexsj.data);scanf(%d,&G.vexsj.outdegree);G.vexsj.outarc=(pnarc)malloc(G.vexsj.outdegree+1)*sizeof(narc);for(i=1;i=G.vexsj.outdegree;i+)printf(%c节点的第%d条弧对应的邻接点所对应的序号为：,G.vexsj.data,i);scanf(%d,&G.vexsj.outarci.adjvex);printf(%c节点的第%d条弧所带的信息为：,G.vexsj.data,i);scanf(%d,&G.);int topologicalorder(graph G,vexstack &s,int *&ve,int &max)int i=1,j,k,count=0;ve=(int*)malloc(G.vexnum+1)*sizeof(int);while(i=(G.vexnum+1)vei+=0; for(i=1;i=G.vexnum;i+) if(G.vexsi.indegree=0)&G.vexsi.kaiguan=0)push(s,i); G.vexsi.kaiguan=1;count+; for(j=1;jvek) vek=vei+G.; max=k; if(!(-G.vexsk.indegree)&G.vexsk.kaiguan=0) push(s,k);G.vexsk.kaiguan=1; count+; G.vexsk.indegree+; if(countG.vexnum )return 0;else return 1;void criticalpath(graph G,vexstack &s,int *date,int max)int i=1,j,k,*vl,dut;vl=(int*)malloc(G.vexnum+1)*sizeof(int);while(i=G.vexnum)vli+=datemax;i=1;while(!emptystack(s)int q=emptystack(s);pop(s,i);int m=*(s.top-1);for(j=1;j=G.vexsi.outdegree;j+)k=G.vexsi.outarcj.adjvex;dut=G.; if(vlk-dutvli)vli=vlk-dut;for(i=1;i=G.vexnum;i+)for(j=1;j%cn,G.vexsi.data,G.,G.vexsk.data);void main()int *a,max=0;graph g;initg