基于邻接矩阵存储的AOE网关键路径算法

AOE邻接矩阵表示一个图，这里的邻接矩阵与一般的稍有不同，在V[i]到V[j]之间没有直接路径时，GRAPH[i][j]=0,以便于使用。另外，程序有些浪费内存，有待改善。源代码如下：

#include

#define NUMER 100

using namespace std;

int Graph[NUMER][NUMER],Mark[NUMER],STACK[NUMER];

int Ve[NUMER],Vl[NUMER],top=0,number;

void initGraph()

{

int i,j;

cout<<"下面我们来建一个AOE网络,请按照提示填入连个节点间的路径值，二者没有直接路径输入0:\n"<

for(i=1;i<=number;i++)

{

for(j=1;j<=number;j++)

{

cout<<"下面请输入从节点"<

cin>>Graph[i][j];

}

}

cout<<"一个具有"<

}

int Tuopu()

{

int i,j,flag,mark=0;//mark作为是否是环的标记变量存在，mark为1表示环

for(i=1;i<=number;i++) {Mark[i]=0; Ve[i]=0;  }//对Mark数组和Ve数组进行初始化

for(j=0;j<=number;j++)//拓扑排序

{

flag=0;//用于检验是否入度为0

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

{

if(Mark[j]==0)

{

if(Graph[i][j]!=0) 

{

flag++;

if(Ve[i]+Graph[i][j]>Ve[j]) Ve[j]=Ve[i]+Graph[i][j];

}

}

else flag=1;//排除已访问过的节点

}

if(flag==0) 

{

Mark[j]=1;

STACK[top]=j;

top++;

cout<

}

}

if(top

{

cout<<"这是一个环!"<

mark++;

}

return mark;

}

void Nituopu(int ltime)

{

int i,j,flag;//i用于初始化,flag用于检查是否出度为0

top=0;

for(i=1;i<=number;i++) {  Mark[i]=0;  Vl[i]=ltime;  }//对mark进行初始化

for(i=number;i>0;i--)//逆拓扑排序

{

flag=0; //用于检验出度为0否

for(j=number;j>0;j--)

{

if(Mark[j]==0)

{

if(Graph[i][j]!=0) 

{

flag++;

if(Vl[i]+Graph[i][j]

}

}

else flag=1;//排除已访问过的节点

}

if(flag==0) 

{

Mark[j]=1;

STACK[top]=j;

top++;

}

}

}

void main()

{

int flag;

cout<<"输入AOE网结点个数(<100):"<

cin>>number;

initGraph();

flag=Tuopu();

if(flag==1) goto loop;

else Nituopu(Ve[number]);

cout<<"关键路径序列如下:"<

for(flag=0;flag

{ 

if(Ve[flag]=Vl[flag]) cout<

}

    loop:

cout<<"程序结束!"<

}