smiledata
2017-06-20 06:44
采纳率: 0%
浏览 1.5k

关键路径算法求完善,AOV网关键路径

#include "stdafx.h"
#include"malloc.h"
typedef int Status;
typedef int InfoType;
typedef int VertexType;
typedef int SElemType;
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;
int weight;//该边所关联的另一顶点的位置
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;

typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)return(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

Status Push(SqStack &S,SElemType e){
if(S.top-S.base>=S.stacksize){
S.base=(SElemType )realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)return(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base)return ERROR;
e=
--S.top;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base)
return OK;
else
return ERROR;
}

int indegree[20];
void FindInDegree(ALGraph G,int indegree[])
{
int i,j,w,k=0,n=0;
ArcNode *p;
int i;
for(i=0; i for(j=0;j {
for(i=0;i {
p=G.vertices[i].firstarc;
while (p)
{
w=p->adjvex;
if(w=i) n++;
p=p->nextarc;
}
}
indegree[k++]=n;
printf("%d",indegree[k]);
n=0;
}
}
int ve[20],vl[20];
SqStack S;
Status TopologicalOrder(ALGraph G,SqStack &T){
int count,j,k;

FindInDegree(G,indegree);
InitStack(T);count=0;
int i;
for(i=0; i<G.vexnum; i++)   ve[i] = 0;
/*ve[0..G.vexnum-1]=0 ;*/
while(!StackEmpty(S)){
Pop(S,j);Push(T,j);++count;
ArcNode *p;
for(p=G.vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;
if(--indegree[k]==0)  Push(S,k);
if(ve[j]+*(p->info)>ve[k])  ve[k]=ve[j]+*(p->info);
}   
}
if(count<G.vexnum) return ERROR;
else return OK;
}

SqStack &T;
Status CriticalPath(ALGraph G){
int j; char tag;int k;int dut;
int ee;int el;
ArcNode p;
if(!TopologicalOrder(G,T)) return ERROR;
int i;
for(i=0; i while(!StackEmpty(T))
for (Pop(T,j),p=G.vertices[j].firstarc; p; p=p->nextarc){
k=p->adjvex; dut=
(p->info);
if (vl[k]-dut }
for(j=0;j for(p=G.vertices[j].firstarc; p; p=p->nextarc){
k=p->adjvex; dut= (p->info);
ee=ve[j]; el=vl[k]-dut;
tag=(ee==el)? '
':' ';
printf("%d %d %d %d %d %c\n",j,k,dut,ee,el,tag);
}

}

int _tmain(int argc, _TCHAR* argv[])
{
ALGraph G;

printf("以下是查找图的关键路径的程序。\n");

TopologicalOrder(G,T);

CriticalPath(G);
return 0;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题