AOE网络的ve和vl

#include
#include
#include
using namespace std;
#define MAX_N 100
#define STACK_INT_SIZE 100
#define STACKINTCREMENT 10
typedef int SElemType;
//邻接表的表结点数据存储结构定义
typedef struct Node
{
double w; //边或弧的权重
int j;// 邻接点下标
struct Node *nextarc;
}ArcNode;
//邻接表的头结点数据存储结构定义
typedef struct
{
int i;// 顶点下标
ArcNode *firstarc;
}HNode;
// 邻接表形式的图的数据存储结构的定义
typedef struct
{
HNode h[MAX_N];
int n,e;// n 为实际顶点数，e为边或弧的数目

}ALGraph;



typedef struct {

SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack &S)
{
S.base=(SElemType*)malloc(STACK_INT_SIZE*sizeof(SElemType));
if(!S.base)
{
printf("ask for memory failed");
exit(0);
}
S.top=S.base;
S.stacksize=STACK_INT_SIZE;
return 1;
}
int GetTop(SqStack S,SElemType &e)
{
if(S.top==S.base) return -1;
e=*(S.top-1);
return 1;
}
int Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INT_SIZE)*sizeof(SElemType));
if(!S.base)
{
printf("ask for memory failed");
exit(0);
}
S.top=S.base+S.stacksize;
S.stacksize+=STACKINTCREMENT;
}
*S.top++=e;
return 1;

}
int Pop(SqStack &S)
{
int e;
if(S.top==S.base)
return -1;
e=*--S.top;
return e;

}
bool StackEmpty(SqStack S)

{
if(S.top==S.base)
return true;
else
return false ;
}
// 建立有向图邻接表的函数
void crtDAGraph(ALGraph &G) // ALGraph 表示是邻接表，DAG表示有向无环图
{
int h,i,j,k;
ifstream ifile("input.txt");
if(!ifile)
cout<<"file not open"<else
cout<<"file open successfully"<ifile>>G.n>>G.e;
// cout<// 初始化顶点序列号
for(i=0;i{
G.h[i].i=i;
G.h[i].firstarc=NULL;
}
for(k=0;k{
ArcNode *pr,*p,*q;
q=new ArcNode ;
ifile>>i>>j>>h;
// 建立第i行结点
q->j=j;
q->w=h;
q->nextarc=NULL;
pr=NULL;
p=G.h[i].firstarc;
while(p&&p->j{
pr=p;
p=p->nextarc;
}
if(pr==NULL)
{
q->nextarc=p;
G.h[i].firstarc=q;
}
else
{
pr->nextarc=q;
q->nextarc=p;
}
}

}

int CalVex(ALGraph &G,double *ve,double *vL)
{
int *indegree=new int[G.n]; //创建indegree 数组，用来标记每个顶点的入度
int i,j,k,count;
double ltime;
double etime;
ArcNode *p;
SqStack S,T;
// 数组初始化
for(i=0;i{
indegree[i]=0;
}
// 此循环为计算每个顶点的入度
for(i=0;i{
for(p=G.h[i].firstarc;p!=NULL;p=p->nextarc)
{
indegree[p->j]++;
}
}
InitStack(S);
InitStack(T);
for(i=0;i{
ve[i]=0;
}
for(i=0;i{

if(!indegree[i])
{
Push(S,i); // 入度为0，入栈
k=i;
break;
}
}

count=0;
while(!StackEmpty(S))
{
i=Pop(S);
// cout<Push(T,i);
count++;
// 顶点出栈，与之连接顶点入度减1
for(p=G.h[i].firstarc;p;p=p->nextarc)
{
indegree[p->j]--;
if(!indegree[p->j])
Push(S,p->j);
//以上两句可以合并为一句代码， if(!(--indegree[p->j])) Push(S,p->j);

etime=ve[i]+p->w;
if(ve[p->j]{ ve[p->j]=etime;

}
}
}
delete[]indegree;
if(countreturn -1;
if(!StackEmpty(T))
{
j=Pop(T);
}
for(i=0;i{
vL[i]=ve[j];
}
while(!StackEmpty(T))
{
i=Pop(T);
for(p=G.h[i].firstarc;p;p=p->nextarc)
{
ltime=vL[p->j]-p->w;
if(vL[i]>ltime)
{ vL[i]=ltime;
}
}
}
return k;
}
int main()
{
int i=0;
int k=0;
ALGraph G;

crtDAGraph(G);
double *ve=new double[G.n];
double *vL=new double[G.n];
k=CalVex(G,ve,vL);
cout<<"AOE网络的ve[]输出结果按结点标号从小到大依次为："<for(i=0;i{
cout<}
cout<cout<<"AOE网络的vl[]输出结果按结点标号从小到大依次为："<for(i=0;i{
cout<}
cout<//PrtKA(G,ve,vL);
system("pause");
return 0;
}