第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
数据结构综合课设关键路径问题.docx
关键路径问题
1. 问题描述
设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键
活动。
2. 基本要求
（1）对一个描述工程的 AOE 网，应判断其是否能够顺利进行。
（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每
一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。
3. 算法思想
（1）在有向图中，如果用顶点表示事件，弧表示活动，弧上的值表示活动
持续的时间，这样的有向图 AOE 网，，通常可用 AOE 网来估算工程的完成时
间。由于一个 AOE 网中的某些活动可以并行地进行，所以完成工程的最短时
间是从源点到汇点最长路径的长度。相应的最长路径就是 AOE 网的关键路径。
（2）对于一个描述工程的 AOE 网，判断是否能顺利完成就是判断该网中是
否存在环。对于该问题可用拓扑序列来判断，当输出的拓扑序列的顶点数小
于真正的顶点数时（即图中尚有顶点为输出，但已不存在入度为 0 的顶点）
就说明存在环。
（3）第二个问题求整项工程至少需要的时间，就得找出关键路径，要找出
关键路径，就要求出各活动的最早可能开始时间 e(i)和允许的最晚发生时间
l(i)并找出满足条件 e(i)=l(i)的活动。
（4）要求出各个活动的 e(i)和 l(i)，就必须知道代表活动的有向边所关联的
两个事的可能最早开始时间 ve(i)和允许的最晚发生时间 vl(i)。
（5）算法步骤：
a. 从键盘上输入或从文件中读入 n 个顶点、e 条弧、顶点值，建立
AOE 网的存储结构。
b. 先利用出边表求出各个事件的可能最早开始时间。（求解 ve(i)的过程
必须按 AOE 网的拓扑序列顺序进行）。
ve(0)=0
ve（i）=max{ve(j)+活动持续的时间}(1<=i<=n-1);j p(i); （p(i)是以顶
点 vi 为头的所有弧的尾结点的集合）
c. 设活动 ak 对应的弧为，活动 ak 持续的时间记为 len()
d. 求每一个顶点 i 的最晚允许发生时间 vl(i)可以沿图中的汇点开始，按
图的逆拓扑序列逐个递推出每个顶点的 vl(i)。
(0<=i<=n-2)
vl(n-1)=ve(n-1);
Vl=min{vl(j)-len()}
头顶点的集合)
e. 根据 e(k)和 l(k)的意义算出：
e(k)=ve(i);
l(k)=vl(j)-len();
f. 再求 e(k)和 l(k)的同时，判断 e(k)是否等于 l(k)，并输出关键活动。
j s(i);(s(i)是以顶点 vi 为尾的所有弧的
4. 模块划分
1. 函数 void creat(AoeGraph *gin,AoeGraph *gout,char *f) 功能：建立图的
邻接矩阵的存储结构（从文件读入）；
2. 函数 void creat1(AoeGraph *gin,AoeGraph *gout) 功能：建立图的邻接矩
阵的存储结构（从键盘读入）；
3. 函数 void print(AoeGraph g) 功能：输出 AOE 网的邻接表；
4. 函数 int EarlistTime(AoeGraph gout,int ve[],int seq[])功能：求 AOE 网各事
件的最早发生时间；
5. 函数 void LateTime(AoeGraph gin,int ve[],int vl[],int seq[])功能：求 AOE 网
各事件的最晚允许开始时间；
6. 函数 int keyact(AoeGraph gout,int ve[],int vl[],int e[],int l[])功能：求出 AOE
网的关键活动及其所依附的两个顶点、最早发生时间、最迟发生时间和完成
整项工程至少需要的时间；
5. 数据结构
typedef char vertextype;
typedef struct node
{
int adjvex;
int len;
struct node *next;
} EdgeNode;
typedef struct de
{
EdgeNode* FirstEdge;
vertextype vertex;
int id;
} vertexnode;
typedef struct
{
vertexnode adjlist[M];
int n,e;
} AoeGraph;
/*边结点类型定义*/
/*边的权值*/
/*带顶点入度的头结点定义*/
/*顶点的入度域*/
/*AOE 网络的邻接表结构*/
6. 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每
个函数参数的含义和函数返回值的含义。
/****************************************************************/
/* 求出完成整项工程至少需要多少时间以及整项工程中的关键活动 */
*/
/* 函数名:creat()、creat1()、print()、
/*
*/
/****************************************************************/
#include
EarlistTime() 、 LateTime()、keyact()
#include
#define M 20
typedef char vertextype;
typedef struct node
{
int adjvex;
int len;
struct node *next;
} EdgeNode;
typedef struct de
{
EdgeNode* FirstEdge;
vertextype vertex;
int id;
} vertexnode;
typedef struct
{
vertexnode adjlist[M];
int n,e;
} AoeGraph;
/*边结点类型定义*/
/*边的权值*/
/*带顶点入度的头结点定义*/
/*顶点的入度域*/
/*AOE 网络的邻接表结构*/
/***************************************************************/
/*函数功能:通过文件读入建立 AOE 网的入边表与出边表存储结构
*/
/* 函数参数：入边表指针变量 gin;出边表指针变量 gout;存放 AOE 网络 */
*/
/*
/* 函数返回值：无
*/
/***************************************************************/
void creat(AoeGraph *gin,AoeGraph *gout,char *f)
{
信息的文件名 filename
int i,j,k,w;
vertextype ch;
EdgeNode *s;
FILE *fp;
fp=fopen(f,"r");
if (fp)
{
/*输入 AOE 网中总结点个数与总边数*/
fscanf(fp,"%d%d",&(gin->n),&(gin->e));
gout->n=gin->n;
gout->e=gin->e;
printf("\t\t\t 图的顶点值：");
for(i=0; in; i++) /*输入 n 个顶点值*/
{
表初始化*/
fscanf(fp,"%1s",&ch);
printf("%c",ch);
gout->adjlist[i].vertex=gin->adjlist[i].vertex=ch;
/*入边
gout->adjlist[i].FirstEdge=gin->adjlist[i].FirstEdge=NULL;
gout->adjlist[i].id=gin->adjlist[i].id=0;
}
/*输入边信息*/
for(k=0; ke; k++)
{
}
/****************************************************************/
/* 函数功能：建立通过键盘输入 AOE 网络的入边表与出边表存储结构 */
*/
/* 函数参数：入边表指针变量 gin;出边表指针变量 gout;
/* 函数返回值：无
*/
/****************************************************************/
void creat1(AoeGraph *gin,AoeGraph *gout)
{
int i,j,k,w;
vertextype ch;
fscanf(fp,"%d%d%d",&i,&j,&w);
s=(EdgeNode*)malloc(sizeof(EdgeNode));
/*在出边表中增加
s->adjvex=j;
s->len=w;
gout->adjlist[j].id++;
s->next=gout->adjlist[i].FirstEdge;
gout->adjlist[i].FirstEdge=s;
s=(EdgeNode*)malloc(sizeof(EdgeNode));
/*顶点 j 的入度加 1*/
/*在入边表中增加
一个边结点*/
一个边结点*/
s->adjvex=i;
s->len=w;
gin->adjlist[j].id++;
s->next=gin->adjlist[j].FirstEdge;
gin->adjlist[j].FirstEdge=s;
/*顶点 j 的入度加 1*/
}
fclose(fp);
}
else
{
}
printf("\t\t\t Read File Error");
gin->n=0;
gout->n=0;
else
{
始化*/
14):****\n");
gout->n=gin->n;
gout->e=gin->e;
printf("\t\t\t ****输入所有顶点值：****\n\t\t\t
for(i=0; in; i++) /*输入 n 个顶点值*/
{
");
scanf("%1s",&ch);
gout->adjlist[i].vertex=gin->adjlist[i].vertex=ch; /*入边表初
gout->adjlist[i].FirstEdge=gin->adjlist[i].FirstEdge=NULL;
gout->adjlist[i].id=gin->adjlist[i].id=0;
}
/*输入边信息*/
printf("\t\t\t ****输入边的信息，输入格式如 Vi Vj len(1 2
for(k=0; ke; k++)
{
EdgeNode *s;
/*输入 AOE 网中总结点个数与总边数*/
printf("\t\t\t ****输入图的顶点数和边数：****\n\t\t\t
while(1)
{
");
scanf("%d%d",&(gin->n),&(gin->e));
if(gin->n==0)
printf("\t\t\t 顶点数不能为 0，请重新输入\n");
");
printf("\t\t\t
scanf("%d%d%d",&i,&j,&w);
s=(EdgeNode*)malloc(sizeof(EdgeNode));
/*在出边表中
s->adjvex=j;
s->len=w;
gout->adjlist[j].id++;
s->next=gout->adjlist[i].FirstEdge;
gout->adjlist[i].FirstEdge=s;
s=(EdgeNode*)malloc(sizeof(EdgeNode));
/*顶点 j 的入度加 1*/
/*在入边表中
增加一个边结点*/
增加一个边结点*/
s->adjvex=i;
s->len=w;
gin->adjlist[j].id++;
s->next=gin->adjlist[j].FirstEdge;
gin->adjlist[j].FirstEdge=s;
/*顶点 j 的入度加 1*/
}
break;
}
}
}
/***************************************************/
/* 函数功能：打印 AOE 网络的入边表或出边表
*/
*/
/* 函数参数：图的指针变量 g;
/* 函数返回值：无
*/
/***************************************************/
void print(AoeGraph g)
/*辅助函数，输出 AOE 网的邻接表*/
{
EdgeNode *p;
int i;
printf("\t\t\t
for (i=0; i",g.adjlist[i].id, g.adjlist[i].vertex);
printf("|%3d|%4d|-->",p->len,p->adjvex);
p=p->next;
}
printf("\n");
}
}
/****************************************************************/
/* 函数功能：求 AOE 网各事件的最早发生时间
*/
/* 函数参数：AOE 网的出边表 gout;记录各事件最早发生时间向量 ve[]; */
/*
*/
/* 函数返回值：返回输出的顶点的个数
*/
/****************************************************************/
int EarlistTime(AoeGraph gout,int ve[],int seq[])
{
记录 AOE 网的拓扑序列向量 seq[]
int count=0,i,j,v, flag[M];
int queue[M];
/*队列*/
int front=0,rear=0;
EdgeNode* p;
for (i=0; i
for(i=0; i",gout.adjlist[v].vertex);
seq[count]=v;
count++;
/*计数器加 1*/
p=gout.adjlist[v].FirstEdge;
while(p)
{
j=p->adjvex;
if (--gout.adjlist[j].id==0 && flag[j]==0)
/*将所有与 v 邻接的顶点的入度减 1*/
/*若入度为 0 则将进队
{
queue[rear++]=j;
flag[j]=1;
}
if (ve[v]+p->len>ve[j])
ve[j]=ve[v]+p->len; /*ve[j]的值是从源点到顶点 j 的最长距
p=p->next;
}
}
return count;
*/
离*/
}
/****************************************************************/
*/
/* 函数功能：求 AOE 网各事件的最晚允许开始时间
*/
/* 函数参数：AOV 网的入边表 gin；各事件最早发生时间向量 ve[]；
/*
各事件最晚允许发生时间向量 vl[];拓扑序列向量 seq[]
*/
/* 函数返回值：无
*/
/****************************************************************/
void LateTime(AoeGraph gin,int ve[],int vl[],int seq[])
{
int k=gin.n-1,i,j,v ;
EdgeNode* p;
for (i=0; i
/*按照拓扑逆序求各事件的最晚允许开始时间*/
vl[i]=ve[seq[gin.n-1]];
while (k>-1)
{
v=seq[k];
p=gin.adjlist[v].FirstEdge;
while(p)
{
j=p->adjvex;
if (vl[v]-p->len < vl[j])
vl[j]=vl[v]-p->len;
p=p->next;
}
k--;
}
}
时间、最迟发生时间和完成整项工程至少需要的时间
/***************************************************************/
/* 函数功能：求 AOE 网关键活动及其所依附的两个顶点、最早发生 */
/*
*/
/* 函数参数：AOV 网的出边表 gout；各事件最早发生时间向量 ve[]； */
各事件最晚允许发生时间向量 vl[];
/*
*/
各活动最早开始时间向量 e[];各活动最迟开始时间向量 l[];*/
/*
/* 函数返回值：返回完成整项工程至少需要的时间
*/
/****************************************************************/
int keyact(AoeGraph gout,int ve[],int vl[],int e[],int l[])
{
|--关键活动--|--最早发生时间--|--最晚发生时间
int i=0,j;
int need_time=0;
int k;
EdgeNode *p;
printf("\n\n\t\t\t
--|\n");
for(j=0; jadjvex;
e[++i]=ve[j];
l[i]=vl[k]-p->len;
if(l[i]==e[i])
{
|\n",gout.adjlist[j].vertex,gout.adjlist[k].vertex,e[i],l[i]);
printf("\t\t\t
|
%c-->%c
| %7d
| %7d
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc