AOE网活动和关键路径

#include<iostream.h> #include<stdio.h> #include<stdlib.h> const int MAX =30; typedef struct node //顶点 { int data; struct node *parent; struct node *child[MAX]; }Apex; typedef struct Edgenode //边 { int adjvex; int info; struct Edgenode *next; }Edge; struct vexnode //链表结点 { int data; struct Edgenode *link; }; struct stack //栈 { Apex *da[MAX]; int top; }; //出栈 void Pop(stack &s,Apex *&p) { p=s.da[s.top]; s.top--; } //入栈 void Push(stack &s,Apex *&p) { s.top++; s.da[s.top]=p; } typedef struct vexnode List[MAX]; int t,n,top[MAX],ee[MAX],le[MAX],e[MAX*MAX],l[MAX*MAX],ve[MAX],vl[MAX],eemax; void creategraph(List g) //建立aoe网络,以邻接表形式存储 { int e,i,s,d,cost; Edge *p; i=MAX; printf("请输入AOE图的顶点数(小于30):"); scanf("%d",&n); printf("请输入AOE图的边数:"); scanf("%d",&e); for(i=0;i<n;i++) //初始化 { g[i].data=i+1; g[i].link=NULL; } printf("请输入各工程的起点，终点和权值:\n"); for(i=0;i<e;i++) { scanf("%d %d %d",&s,&d,&cost); p=(Edge *)malloc(sizeof(Edge)); p->adjvex=d; p->info=cost; p->next=g[s-1].link; g[s-1].link=p; } cout<<"-------------------------------------------------\n"; } int check(List g) //检查网中是否有回路 { int m,i,j,v,k,deg[MAX],s[MAX]; Edge *p; for(i=0;i<MAX;i++) deg[i]=0; for(i=0;i<n;i++) { p=g[i].link; while(p!=NULL) { deg[(p->adjvex)-1]++; p=p->next; } } j=0; for(i=0;i<n;i++) { if(deg[i]==0) {s[j]=i+1;j++;} } m=0; for(i=0;i<n;i++) ee[i]=0; t=0; while(j!=0) { j--; top[t]=s[j]; v=s[j]-1; t++; m++; for(p=g[v].link;p!=NULL;p=p->next) { k=(p->adjvex)-1; if(--deg[k]==0) {s[j]=k+1;j++;} if(ee[v]+(p->info)>ee[k]) ee[k]=ee[v]+(p->info); } } if(m==n) return(0); else return(1); } Apex *copy(Apex *a) //复制树的结点及其子女 { Apex *temp,*b; int i; b=(Apex *)malloc(sizeof(Apex)); b->data=a->data; for(i=0;i<MAX;i++) b->child[i]=NULL; for(i=0;i<MAX;i++) { if(a->child[i]!=NULL) { temp=(Apex *)malloc(sizeof(Apex)); temp->data=a->child[i]->data; b->child[i]=temp; } } return(b); } void Print(Apex *a) //关键路径输出的实现 { Apex *t; stack s; s.top=0; for(t=a;t!=NULL;t=t->parent) Push(s,t); while(s.top!=1) { Pop(s,t); cout<<t->data<<"->"; } Pop(s,t); cout<<t->data<<endl; } void printpath(List graph) //输出所有关键路径 { Apex *q[3000],*root,*pt,*cadj[MAX],*temp,*phead; Edge *p; int head,tail,i,j,k; for(i=0;i<n;i++) { cadj[i]=(Apex *)malloc(sizeof(Apex)); cadj[i]->data=graph[i].data; for(j=0;j<MAX;j++) cadj[i]->child[j]=NULL; k=0; for(p=graph[i].link;p;p=p->next) { pt=(Apex *)malloc(sizeof(Apex)); pt->data=p->adjvex; cadj[i]->child[k]=pt; k++; } } for(i=0;i<n;i++) if(ee[i]==0) break; root=cadj[i]; root->parent=NULL; q[0]=root; head=0; tail=1; while(head<tail) { pt=q[head]; if(ee[(pt->data)-1]==eemax) { phead=pt; Print(phead); } head++; for(i=0;i<MAX;i++) if(pt->child[i]!=NULL) { temp=(Apex *)malloc(sizeof(Apex)); temp=copy(cadj[(pt->child[i]->data)-1]); pt->child[i]=temp; pt->child[i]->parent=pt; q[tail]=pt->child[i]; tail++; } } } void crit(List g) //输出关键活动,关键路径,各边的e与l,及工程完成最早时间 { Edge *p,*q; int i,v,k,m,x=0; int diff[MAX],begin[MAX],end[MAX]; for(i=0;i<n;i++) le[i]=ee[n-1]; while(t!=0) { for(t--,v=top[t]-1,p=g[v].link;p;p=p->next) { k=(p->adjvex)-1; if(le[v]>le[k]-(p->info)) le[v]=le[k]-(p->info); } } m=0; cout<<"\n边\te\tl\n"; for(i=0;i<n;i++) for(p=g[i].link;p;p=p->next) { e[m]=ee[i]; l[m]=le[(p->adjvex)-1]-(p->info); diff[m]=l[m]-e[m]; cout<<"("<<g[i].data<<","<<p->adjvex<<")\t"<<e[m]<<'\t'<<l[m]<<endl; if(diff[m]==0) { begin[x]=g[i].data; end[x]=p->adjvex; x++; } else if(p==g[i].link) g[i].link=p->next; else { for(q=g[i].link;q->next!=p;q=q->next); q->next=p->next; } m++; } eemax=0; for(i=0;i<n;i++) if(ee[i]>eemax) eemax=ee[i]; printf("-------------------------------------------------\n"); cout<<"工程完成最早时间:"<<eemax<<endl; cout<<"-------------------------------------------------\n"; cout<<"关键活动:\n"; for(i=0;i<x;i++) cout<<"("<<begin[i]<<","<<end[i]<<")"<<'\t'; cout<<"\n-------------------------------------------------\n"; cout<<"\n关键路径:\n"; printpath (g); printf("-------------------------------------------------\n"); } int main() { List g; system("cls"); system("color 81"); system("mode con cols=80 lines=400"); printf("@*************************************************************@\n"); putchar('\n'); printf(" %c----------欢迎进入AOE网最短路径测试程序----------%c\n",2,2); putchar('\n'); printf("@*************************************************************@\n"); printf("-------------------------------------------------\n"); creategraph(g); if(check(g)==0) { cout<<"\n工程可行!"; cout<<"\n-------------------------------------------------\n"; crit(g); } else cout<<"\n工程有误!\n"; cout<<endl; printf("%c-------%c-------%c-------%c-------%c\n",2,2,2,2,2); printf(" (^_^)谢谢使用!(^_^)\n"); printf("%c-------%c-------%c-------%c-------%c\n",2,2,2,2,2); system("pause"); return 1; }