数据结构之---C语言实现关键路径AOE图
程序员文章站
2024-01-31 14:15:46
//关键路径AOE
//杨鑫
#include
#include
#include
//定义邻接表
typedef struct node
{...
//关键路径AOE //杨鑫 #include #include #include //定义邻接表 typedef struct node { int adjvex; int w; struct node *nextedge; }edgenode; //定义边集 typedef struct { char data; int id; edgenode *firstedge; }vexnode; void CreateGraph(vexnode* Graph,int vexnumber,int arcnumber) { int i = 0, j = 0, k = 0; int begin,end,duttem; char ch; edgenode *p; for(i=0;i ); for(k=0;kadjvex =end-1; p->w =duttem; Graph[end-1].id ++; p->nextedge =Graph[begin-1].firstedge ; Graph[begin-1].firstedge =p; } } int SearchMapPath(vexnode* Graph,int vexnumber,int arcnumber) { int totaltime=0; int m=0; int i,j,k,t; char sv[100]; int front,rear; int *topology_queue,*vl,*ve,*el,*ee; front=rear=-1; t=0; topology_queue=(int*)malloc(vexnumber*sizeof(int)); vl=(int*)malloc(vexnumber*sizeof(int)); ve=(int*)malloc(vexnumber*sizeof(int)); el=(int*)malloc(arcnumber*sizeof(int)); ee=(int*)malloc(arcnumber*sizeof(int)); edgenode *p; for(i=0;iadjvex ; Graph[k].id --; if(ve[j]+p->w >ve[k]) ve[k]=ve[j]+p->w ; if(Graph[k].id ==0) topology_queue[++rear]=k; p=p->nextedge ; } } if(m=0;i--) { j=topology_queue[i]; p=Graph[j].firstedge; while(p) { k=p->adjvex ; if((vl[k]-p->w )w; p=p->nextedge; } } printf(| 起点 | 终点 | 最早开始时间 | 最迟开始时间 | 差值 | 是否为关键路径 ); i=0; for(j=0;jadjvex; ee[++i]=ve[j]; el[i]=vl[k]-p->w; printf(| %4c | %4c | %12d | %12d | %4d |,Graph[j].data ,Graph[k].data ,ee[i],el[i],el[i]-ee[i]); if(el[i]==ee[i]) { printf( 此弧为关键活动 ); sv[t]=Graph[j].data;t++; } printf( ); p=p->nextedge; } } printf(关键路径节点为:); sv[t]=Graph[vexnumber-1].data; for(i=0;i<=t;i++) { printf(%c,sv[i]); if(sv[i]!=Graph[vexnumber-1].data) printf(--->); } printf( ); printf(关键路径长度为:%d个单位时间 ,totaltime); return 1; } int main( ) { int vexnumber,arcnumber,totaltime=0; printf(请输入这个图中的节点数:); scanf(%d,&vexnumber); printf(请输入这个图中的弧数:); scanf(%d,&arcnumber); vexnode* Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode)); CreateGraph(Graph,vexnumber,arcnumber); SearchMapPath(Graph,vexnumber,arcnumber); return 0; }
结果:
上一篇: 山核桃的营养价值
下一篇: 华硕推云计算车载导航系统