數(shù)據(jù)結(jié)構(gòu)與算法

《數(shù)據(jù)結(jié)構(gòu)與算法》關(guān)鍵路徑

源程序清單

#include<stdio.h>

#include<stdlib.h>

#include<iomanip.h>

ttinclude<process.h>

typedefstructnode〃邊表結(jié)點(diǎn)

{

intadjvex;〃鄰接點(diǎn)編號(hào)

intdut;〃弧的信息

structnode*next;〃下一條弧指針

}edgenode;

typedefstruct〃頂點(diǎn)表結(jié)點(diǎn)

(

intprojectname;〃頂點(diǎn)域

intid;〃頂點(diǎn)的入度信息

edgenode*link;〃邊表頭指針

}vexnode;

voidCreateGraphic(vexnode*Graphicmap,int

projectnumber,intactivenumber)ffl

intbegin,end,duttem;

〃分別代表弧的前節(jié)點(diǎn)，尾節(jié)點(diǎn)，活動(dòng)時(shí)間

edgenode*p;〃邊表頭指針

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

(

Graphicmap[i].projectname=i;

//頂點(diǎn)的命名按0,1,2,3.....

Graphicmap[i].id=0;

〃頂點(diǎn)的信息的度數(shù)均賦為零

Graphicmap[i].link=NULL;

)

printf(〃\n〃)；

printf(〃請輸入某項(xiàng)目的信息，并請用整形數(shù)字

表示(格式：弧頭，弧尾，權(quán)值)：\n〃)；

printf(〃例如:輸入1,2,4即代表結(jié)點(diǎn)1與2

之間的活動(dòng)需要4個(gè)時(shí)間單位。\n〃)；

printf(〃\n〃);

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

//activenumber為活動(dòng)的數(shù)目，即弧的條數(shù)

(

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

〃請輸入第%d條的起點(diǎn)、終點(diǎn)和權(quán)值

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

時(shí)分配存儲(chǔ)空間

p->adjvex二endT;〃因?yàn)槭菑牧汩_始記的，

故要減1,就是讓終點(diǎn)插入到鄰接表內(nèi)

p->dut=duttem;

〃該弧的活動(dòng)時(shí)間為duttem

Graphicmap[end-1].id++;

〃入度加1

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

Graphicmap[begin-1].link=p;〃讓下一個(gè)

節(jié)點(diǎn)作為下一插入節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)

intSearchMapPath(vexnode*

Graphicmap,intprojectnumber,int

activenumber

,int&totaltime)

〃求出最大路徑，并打印出關(guān)鍵路徑

{

inti,j,k,m=0;

intfront=-l,rear=-l;

int*

topologystack=(int*)malloc(projectnumber*si

zeof(int));

〃用來保存拓?fù)渑帕?/p>

int*vl二(int*)malloc

(projectnumber*sizeof(int));

〃用來表示在不推遲整個(gè)工程的前提下，Vj允許

最遲發(fā)生的時(shí)間

int*ve=(int*)malloc

(projectnumber*sizeof(int));

〃用來表示Vj最早發(fā)生時(shí)間

int*1=(int*)malloc

(activenumber*sizeof(int));〃用來表示活動(dòng)

Ai最遲完成開始時(shí)間

int*e=(int*)malloc

(activenumber*sizeof(int));〃表示活動(dòng)最早開

始時(shí)間

edgenode*p;//邊表頭的指針

totaltime=0;〃存放整個(gè)工程的最短時(shí)間

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

〃先把每個(gè)工程的最早發(fā)生時(shí)間初始化為零

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

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

{

topologystack[++rear]=i;

〃讓所有的頭節(jié)點(diǎn)入隊(duì)列

m++;

〃記錄入隊(duì)列的頂點(diǎn)個(gè)數(shù)

)

)

while(front!=rear)

(

front++;//出隊(duì)列

j=topologystack[front];

〃拓?fù)渑判虻墓?jié)點(diǎn)依次出隊(duì)列

p=Graphicmap[j].link;

〃指向頂點(diǎn)指向的下一個(gè)頂點(diǎn)

while(p)

(

k=p->adjvex;//鄰接點(diǎn)編號(hào)

Graphicmap[k].id一;

〃讓入度減1,相當(dāng)于刪除一個(gè)入度為零的前驅(qū)節(jié)

點(diǎn)，和相關(guān)的弧

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

〃將最長的路徑賦給VE[K]

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

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

〃如果入度為零，則入隊(duì)列

(

topologystack[++rear]=k;

m++;〃記錄入隊(duì)列的節(jié)點(diǎn)個(gè)數(shù)

)

p=p->next;〃指向下一個(gè)節(jié)點(diǎn)

)

}

if(m<projectnumber)

〃如果有環(huán)，則不能遍歷每個(gè)節(jié)點(diǎn)

(

printf(，z\n本程序所建立的圖有回路不可計(jì)

算出關(guān)鍵路徑!\n〃)；

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

return0;

}

totaltime=ve[projectnumber-1];

〃最短完成時(shí)間即為最后一個(gè)節(jié)點(diǎn)所

〃累加的時(shí)間之和

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

vl[i]=totaltime;

〃初始化所有頂點(diǎn)的最遲時(shí)間為最長

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

//用逆拓?fù)渑判騺砬蠡顒?dòng)Ai最遲完成

〃開始時(shí)間，即從最后一個(gè)節(jié)點(diǎn)減去最短

〃的時(shí)間

(

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起點(diǎn)|終點(diǎn)|最早開始時(shí)間|最

遲完成時(shí)間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])〃當(dāng)差值為零時(shí)，則為關(guān)

鍵路徑

printfC關(guān)鍵活動(dòng)〈％2d,%4d>〃，

Graphicmap[j].projectname

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

printf(〃\n〃)；

p=p->next;

}

)

return1;

)

voidseekkeyroot()〃求關(guān)鍵路徑的主函數(shù)

{

int

projectnumber,activenumber,totaltime=0;

printf(〃\n〃)；

printf(〃輸入符合標(biāo)準(zhǔn)，歡迎進(jìn)入求關(guān)鍵路徑的

系統(tǒng)!\n〃)；

printf(〃\n〃);

printf(〃請輸入這個(gè)項(xiàng)目的AOE-網(wǎng)的節(jié)點(diǎn)數(shù)：

〃)；

scanf(〃％d〃，&projectnumber);

printf(〃請輸入這個(gè)項(xiàng)目的AOE-網(wǎng)的活動(dòng)個(gè)數(shù):

〃)；

scanf(〃％d〃，&activenumber);

vexnode*

Graphicmap=(vexnode*)malloc(projectnumber*s

izeof(vexnode));

CreateGraphic(Graphicmap,projectnumber,acti

venumber);〃創(chuàng)建鄰接圖

SearchMapPath(Graphicmap,projectnumber,acti

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

關(guān)鍵路徑

printf(〃\n〃)；

printf(〃整個(gè)工程所用的最短時(shí)間為：%d個(gè)單

位時(shí)間\n〃,totaltime);

system(〃pause〃);

intmain()

charch;

for(;;)

(

do

(

system(〃cls〃);

printf

★\n〃)；

printf(〃

歡迎進(jìn)入求關(guān)鍵路徑算法程序

\n〃)；

printf

\n〃);

printf(〃％s〃，〃\ns(start)開始輸入

工程的節(jié)點(diǎn)數(shù)據(jù)并求出關(guān)鍵路徑\n〃);

printf(〃\n〃)；

printf(〃如〃,〃e(exi