数据结构----*拓扑排序&&关键路径算法

发表于

#include<iostream.h>
#include<cstdlib>
#define outmax 3//最大出度
#define inmax 2//最大入度
#define vex 9//顶点个数
#define max 10000//定义极大值
int linjie_0[vex][outmax]={{1,2,3},{4},{4},{5},{6,7},{7},{8},{8},{-1}};//出邻接顶点
int linjie_1[vex][inmax]={{-1},{0},{0},{0},{1,2},{3},{4},{4,5},{6,7}};//入邻接顶点
int label_1[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};//第0列是拓扑列标志位,第1列是入度,第2列是出度
int labevl[vex][3]={{0,0,3},{0,1,1},{0,1,1},{0,1,1},{0,2,2},{0,1,1},{0,1,1},{0,2,1},{0,2,0}};//第0列是拓扑列标志位,第1列是入度(在拓扑排序子程序中值要改变),第2列是出度
int juzhen[vex][vex];//邻接矩阵
int tuopu[vex],tuopu_k=0;//拓扑序列
int ve[vex],vl[vex];//顶点,事件的最早发生时间和最迟发生时间
int e[vex][vex],l[vex][vex];//边,活动的最早开始时间和最迟开始时间,两者相等的即为关键路径
void tuopupaixu();//拓扑排序子程序
void make_ve();//事件最早发生时间子程序
void make_vl();//事件最迟发生时间子程序
void critical_path();//关键路径子程序
int main()
{
int i,j;
for(i=0;i<vex;i++)
for(j=0;j<vex;j++)
{
tuopu=0;
ve=0;
juzhen[j]=max;
vl=max;
}
juzhen[0][1]=6;
juzhen[0][2]=4;
juzhen[0][3]=5;
juzhen[1][4]=1;
juzhen[2][4]=1;
juzhen[3][5]=2;
juzhen[4][6]=9;
juzhen[4][7]=7;
juzhen[5][7]=4;
juzhen[6][8]=2;
juzhen[7][8]=4;//初始化
tuopupaixu();
make_ve();
make_vl();
critical_path();
cout<<endl;
system("pause");
return 0;
}

void tuopupaixu()
{
int i,j;
while(1)
{
for(i=0;i<vex;i++)
if(labevl[0]==0)
j=1;
if(j==0)
break;
for(i=0;i<vex;i++)
if(labevl[0]==0 && labevl[1]==0)
{
labevl[0]=1;//删除已经排入拓扑序列的顶点
tuopu[tuopu_k]=i;//拓扑编号
tuopu_k++;
for(j=0;j<labevl[2];j++)
labevl[linjie_0[j]][1]--;//使和排入拓扑序列的顶点相邻的顶点的入度减1
}
}
cout<<"拓扑序列:";
for(i=0;i<vex;i++)
cout<<tuopu<<" ";
}
void make_ve()
{
cout<<endl<<"事件的最早开始时间:";
int i,j;
int a1,a2,a3;
for(i=0;i<vex;i++)//按拓扑序列的顺序做
{
a1=tuopu;
for(j=0;j<label_1[a1][2];j++)//从源点到汇点推进
{
a2=linjie_0[a1][j];//向后邻接顶点
a3=juzhen[a1][a2];//边的权值
if(ve[a2]<ve[a1]+a3)
ve[a2]=ve[a1]+a3;//ve(j)=Max { ve(i)+dut(<i,j>) }
}
}
for(i=0;i<vex;i++)
cout<<"["<<i<<"]-"<<ve<<" ";
}
void make_vl()
{
cout<<endl<<"事件的最迟开始时间:";
int i,j;
int a1,a2,a3;
vl[vex-1]=ve[vex-1];//汇点的vl值等于其ve值
for(i=vex-1;i>0;i--)//按逆拓扑序列的顺序做
{
a1=tuopu;
for(j=0;j<label_1[a1][1];j++)//从汇点到源点推进
{
a2=linjie_1[a1][j];//向前邻接顶点
a3=juzhen[a2][a1];//边的权值
if(vl[a2]>vl[a1]-a3)
vl[a2]=vl[a1]-a3;//vl(i)=Min { vl(j)-dut(<i,j>) }
}
}
for(i=0;i<vex;i++)
cout<<"["<<i<<"]-"<<vl<<" ";
}
void critical_path()
{
cout<<endl<<"关键路径:";
int i,j;
for(i=0;i<vex;i++)
for(j=0;j<vex;j++)
{
if(juzhen[j]!=max)
{
e[j]=ve;//e(i)=ve(i)
l[j]=vl[j]-juzhen[j];//l(i)=vl(j)-dut(<i,j>)
if(e[j]==l[j] && e[j]!=max)//关键路径的判断
cout<<"["<<i<<"]"<<"-->"<<"["<<j<<"]     ";
}
}
}

ysfeng(游客)发表评论于2007-4-23 15:34:04头两个库函数怎么没有列出?
以下为blog主人的回复:
因为字体的原因,可能编译器认不出来吧