Chinaunix首页 | 论坛 | 博客
  • 博客访问: 256765
  • 博文数量: 33
  • 博客积分: 861
  • 博客等级: 军士长
  • 技术积分: 325
  • 用 户 组: 普通用户
  • 注册时间: 2011-02-26 09:35
文章存档

2013年(1)

2012年(8)

2011年(25)

分类: C/C++

2012-05-10 10:50:44

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<<"程序结束!"<
}

阅读(5538) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~