数据结构与算法

《数据结构与算法》关键路径

源程序清单

#include<stdio.h>

#include<stdlib.h>

#include<iomanip.h>

ttinclude<process.h>

typedefstructnode〃边表结点

{

intadjvex;〃邻接点编号

intdut;〃弧的信息

structnode*next;〃下一条弧指针

}edgenode;

typedefstruct〃顶点表结点

(

intprojectname;〃顶点域

intid;〃顶点的入度信息

edgenode*link;〃边表头指针

}vexnode;

voidCreateGraphic(vexnode*Graphicmap,int

projectnumber,intactivenumber)ffl

intbegin,end,duttem;

〃分别代表弧的前节点，尾节点，活动时间

edgenode*p;〃边表头指针

for(inti=0;i<projectnumber;i++)

(

Graphicmap[i].projectname=i;

//顶点的命名按0,1,2,3.....

Graphicmap[i].id=0;

〃顶点的信息的度数均赋为零

Graphicmap[i].link=NULL;

)

printf(〃\n〃)；

printf(〃请输入某项目的信息，并请用整形数字

表示(格式：弧头，弧尾，权值)：\n〃)；

printf(〃例如:输入1,2,4即代表结点1与2

之间的活动需要4个时间单位。\n〃)；

printf(〃\n〃);

for(intk=0;k<activenumber;k++)

//activenumber为活动的数目，即弧的条数

(

scanf(〃％d,%d,%d〃,&begin,&end,&duttem);

〃请输入第%d条的起点、终点和权值

p=(edgenode*)malloc(sizeof(edgenode));//临

时分配存储空间

p->adjvex二endT;〃因为是从零开始记的，

故要减1,就是让终点插入到邻接表内

p->dut=duttem;

〃该弧的活动时间为duttem

Graphicmap[end-1].id++;

〃入度加1

p->next=Graphicmap[begin-1].link;

Graphicmap[begin-1].link=p;〃让下一个

节点作为下一插入节点的前驱节点

intSearchMapPath(vexnode*

Graphicmap,intprojectnumber,int

activenumber

,int&totaltime)

〃求出最大路径，并打印出关键路径

{

inti,j,k,m=0;

intfront=-l,rear=-l;

int*

topologystack=(int*)malloc(projectnumber*si

zeof(int));

〃用来保存拓扑排列

int*vl二(int*)malloc

(projectnumber*sizeof(int));

〃用来表示在不推迟整个工程的前提下，Vj允许

最迟发生的时间

int*ve=(int*)malloc

(projectnumber*sizeof(int));

〃用来表示Vj最早发生时间

int*1=(int*)malloc

(activenumber*sizeof(int));〃用来表示活动

Ai最迟完成开始时间

int*e=(int*)malloc

(activenumber*sizeof(int));〃表示活动最早开

始时间

edgenode*p;//边表头的指针

totaltime=0;〃存放整个工程的最短时间

for(i=0;i<projectnumber;i++)ve[i]=0;

〃先把每个工程的最早发生时间初始化为零

for(i=0;i<projectnumber;i++)

if(Graphicmap[i].id==O)

{

topologystack[++rear]=i;

〃让所有的头节点入队列

m++;

〃记录入队列的顶点个数

)

)

while(front!=rear)

(

front++;//出队列

j=topologystack[front];

〃拓扑排序的节点依次出队列

p=Graphicmap[j].link;

〃指向顶点指向的下一个顶点

while(p)

(

k=p->adjvex;//邻接点编号

Graphicmap[k].id一;

〃让入度减1,相当于删除一个入度为零的前驱节

点，和相关的弧

if(ve[j]+p->dut>ve[k])

〃将最长的路径赋给VE[K]

ve[k]=ve[j]+p->dut;

if(Graphicmap[k].id==0)

〃如果入度为零，则入队列

(

topologystack[++rear]=k;

m++;〃记录入队列的节点个数

)

p=p->next;〃指向下一个节点

)

}

if(m<projectnumber)

〃如果有环，则不能遍历每个节点

(

printf(，z\n本程序所建立的图有回路不可计

算出关键路径!\n〃)；

printf(〃将退出本程序！\n〃);

return0;

}

totaltime=ve[projectnumber-1];

〃最短完成时间即为最后一个节点所

〃累加的时间之和

for(i=0;Kprojectnumber;i++)

vl[i]=totaltime;

〃初始化所有顶点的最迟时间为最长

for(i=projectnumber-2;i>=0;i--)

//用逆拓扑排序来求活动Ai最迟完成

〃开始时间，即从最后一个节点减去最短

〃的时间

(

j二topologystack[i];

p=Graphicmap[j].link;

while(p)

{

k=p->adjvex;

if((vl[k]-p->dut)<vl[j])

vl[j]=vl[k]-p->dut;

p=p->next;

)

)

i=0;

printf(〃\n〃)；

printf(z/1起点|终点|最早开始时间|最

迟完成时间I差值I备注\n〃)；

for(j=0;j<projectnumber;j++)

|

p=Graphicmap[j].link;

while(p)

k=p->adjvex;

e[++i]=ve[j];

1[i]=vl[k]-p->dut;

printfC|%4d|%4d|%lld|%lld

%3d|z/,Graphicmap[j].projectname

+1,Graphicmap[k].projectname

+1,e[i],1[i],1[i]-e[i]);

if(l[i]==e[i])〃当差值为零时，则为关

键路径

printfC关键活动〈％2d,%4d>〃，

Graphicmap[j].projectname

+1,Graphicmap[k].projectname+1);

printf(〃\n〃)；

p=p->next;

}

)

return1;

)

voidseekkeyroot()〃求关键路径的主函数

{

int

projectnumber,activenumber,totaltime=0;

printf(〃\n〃)；

printf(〃输入符合标准，欢迎进入求关键路径的

系统!\n〃)；

printf(〃\n〃);

printf(〃请输入这个项目的AOE-网的节点数：

〃)；

scanf(〃％d〃，&projectnumber);

printf(〃请输入这个项目的AOE-网的活动个数:

〃)；

scanf(〃％d〃，&activenumber);

vexnode*

Graphicmap=(vexnode*)malloc(projectnumber*s

izeof(vexnode));

CreateGraphic(Graphicmap,projectnumber,acti

venumber);〃创建邻接图

SearchMapPath(Graphicmap,projectnumber,acti

venumber,totaltime);〃求出最大路径,并打印出

关键路径

printf(〃\n〃)；

printf(〃整个工程所用的最短时间为：%d个单

位时间\n〃,totaltime);

system(〃pause〃);

intmain()

charch;

for(;;)

(

do

(

system(〃cls〃);

printf

★\n〃)；

printf(〃

欢迎进入求关键路径算法程序

\n〃)；

printf

\n〃);

printf(〃％s〃，〃\ns(start)开始输入

工程的节点数据并求出关键路径\n〃);

printf(〃\n〃)；

printf(〃如〃,〃e(exi