消息关闭
    暂无新消息!

求完善AOV网关键路经

问题作者 : McLusky2017-06-22发布
使用算法为下面这个
#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<20; i++) indegree[i] = 0;
 for(j=0;j<G.vexnum;j++)
 {
 for(i=0;i<G.vexnum;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<G.vexnum; i++) vl[i] =ve[G.vexnum-1];
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<vl[j])   vl[j]=vl[k]-dut;
       }
  for(j=0;j<G.vexnum;++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); 
}

}

3个回答

︿ 0
创建网输入输出问题#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;

int LocateVex(ALGraph G , VertexType v){
 //确定点v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
 if(G.vertices[i].data == v)
 return i;
    return -1;
 }//LocateVex
 Status CreateUDG(ALGraph &G){ 
 //采用邻接表表示法,创建无向图G
 int i, j, k,x;
   VertexType v1, v2;
 ArcNode *p;
 
printf ( "************采用邻接表表示法创建有向图**************") ;
scanf("%d %d",&G.vexnum,&G.arcnum); //输入总顶点数,总边数 
printf("请输入%d个顶点:\n",G.vexnum);
 for(i = 0; i<G.vexnum;i++)
 {     
scanf("%d",&G.vertices[i].data);            //输入顶点值 
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL 
 }//for
for(k = 0; k < G.arcnum;++k){         //输入各边,构造邻接表
printf("请输入第%d条边,权值是:\n",k+1);
//scanf("%d",&)
scanf("%d %d",&v1,&v2);  //输入一条边依附的两个顶点
i = LocateVex(G, v1); 
j = LocateVex(G, v2);//确定v1和v2在G中位置,即顶点在G.vertices中的序号 
p=new ArcNode;                //生成一个新的边结点*p1 
p->adjvex=j;
 p->weight=x;//邻接点序号为j 
 p->nextarc= G.vertices[i].firstarc; 
 G.vertices[i].firstarc=p;  
 //将新结点*p插入顶点vi的边表头部
    }//for 
     return OK; 
 }//CreateUDG 
//输出邻接表表示的有向图
 void OutputUDG(ALGraph G)
 { int i;
 VNode temp;
 ArcNode *p;  
printf("*****邻接表表示法创建的有向图*****") ;
 for(i = 0 ; i < G.vexnum ; ++i)
 {
 temp = G.vertices[i];
 p = temp.firstarc;
 if(p == NULL){
 printf  ("%d",G.vertices[i].data);
 }
 else{
 printf ("%d",temp.data);
 while(p){

printf  ("%d",p->adjvex);
 printf ("%d",p->weight);
 p = p->nextarc;
 }
 }
 }
 }

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 j,w,k=0,n=0;
 ArcNode *p;
 int i;
 for(i=0; i<G.vexnum; i++) indegree[i] = 0;

 for(i=0;i<G.vexnum;i++)
 {
 p=G.vertices[i].firstarc;
 while (p)
 {
 w=p->adjvex;
 indegree[w]++;

 p=p->nextarc; }
 
 //printf("%d",indegree[k]);
  }
 }

 int ve[20],vl[20];
SqStack S;SqStack T;
Status TopologicalOrder(ALGraph G,SqStack &T){
int count,j,k;
FindInDegree(G,indegree);
InitStack(T);count=0;
int i; ArcNode *p;
    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;
for(p=G.vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;
if(!(--indegree[k]))  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;
}


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<G.vexnum; i++) vl[i] =ve[G.vexnum-1];
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<vl[j])   vl[j]=vl[k]-dut;
       }
  for(j=0;j<G.vexnum;++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;  

 CreateUDG(G);
 OutputUDG;

       /*printf("以下是查找图的关键路径的程序。\n"); */ 
      // TopologicalOrder(G,T);  
      // CriticalPath(G); 
return 0;

}