用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期……
三、程序清单
#include<stdio.h> #include<stdlib.h> #include<iomanip.h> #include <process.h>
typedef struct node //定义表结点 { int adjvex; //该弧所指向的顶点的位置 int dut; //弧的权值 struct node *next; //指向下一条弧的指针 }edgenode;
typedef struct //定义头结点 { int projectname; //顶点信息 int id; //结点入度 edgenode *link; //指向第一条依附该顶点的弧的指针 }vexnode;
void CreateGraphic(vexnode* G,int prnum,int actnum) //创建图 { int begin,end,duttem; edgenode *p; for(int i=0;i<prnum;i++) { G[i].projectname=i; G[i].id=0; G[i].link=NULL; } printf("某项目的开始到结束在图中的结点输入<vi,vj,dut>\n"); printf("如：3,4,9 回车表示第三节点到第四结点之间的活动用了9个单位时间\n"); for(int k=0;k<actnum;k++) { scanf("%d,%d,%d",&begin,&end,&duttem); p=(edgenode*)malloc(sizeof(edgenode)); p->adjvex=end-1; p->dut=duttem; G[end-1].id++; p->next=G[begin-1].link ; G[begin-1].link=p; } }