guanjianlujing.cpp

求关键路径

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define INFINITY  88
#define MAX_VERTEX_NUM 20
#define MAX_ARC_NUM  MAX_VERTEX_NUM*2
#define STACK_INIT_SIZE  100
#define STACKINCREMENT 10
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int InfoType;
typedef char VertexType;

typedef struct ArcNode
{
  int adjvex;
  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;
  int ve[ MAX_VERTEX_NUM];
  int vl[ MAX_VERTEX_NUM];
}ALGraph;

typedef int SElemType;
typedef struct
{
  SElemType *base;
  SElemType *top;
  int stacksize;
} SqStack;

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

Status Push(SqStack &S,SElemType e)
{
   int stackincrement=STACKINCREMENT;
   if(S.top-S.base >= S.stacksize)
   {
      S.base=(SElemType*)realloc(S.base,(S.stacksize+stackincrement)*sizeof(SElemType));
      if(!S.base) exit (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 (TRUE);
   else return (FALSE);
}

Status CreateDN(ALGraph &G)
{
  int i,j,k,w,IncInfo;
  char v1,v2,V;
  ArcNode *p;
  int LocateVex(ALGraph,char);
  printf("input the number for vexnum and arcnum");
  scanf("%d,%d",&G.vexnum,&G.arcnum);
  IncInfo=0;IncInfo=IncInfo;
  V=getchar(); //skip the enter ,same as next...
  
  printf("input %d char for vexs \n",G.vexnum);
  for(i=0;i<G.vexnum;++i)
  {
     G.vertices[i].data=getchar();
     V=getchar();
  }
  
  for(i=0;i<G.vexnum;++i)
     G.vertices[i].firstarc=NULL;
    
  printf("input %d arc(char,char,weight)  \n",G.arcnum);
  for(k=0;k<G.arcnum;++k)
  {
    printf("%d:   ",k);
    scanf("%c,%c,%d",&v1,&v2,&w);
    V=getchar(); V=V;
    i=LocateVex(G,v1);   j=LocateVex(G,v2);
    if(i!=100&&j!=100)
    {
       p=new ArcNode;
       p->adjvex=j;
       p->info=new InfoType;
       *(p->info)=w;
       p->nextarc=G.vertices[i].firstarc;
       G.vertices[i].firstarc=p;
    }
  }
   return OK;
}

int  LocateVex(ALGraph G,char v)
{
  int i,p;
  p=100;
  for(i=0;i<G.vexnum;++i)
     if(v==G.vertices[i].data)p=i;
  return p;
}

Status DispGraph(ALGraph G)
{
  int i;
  ArcNode *p;
  for(i=0;i<G.vexnum;++i)
  {
     printf("%3d%c",i,G.vertices[i].data);
     p=G.vertices[i].firstarc;
     while(p)
     {
        printf("--->%d%3d",p->adjvex,*(p->info));
        p=p->nextarc;
     }
     printf("\n");
  }
  return OK;
}

Status TopologicalOrder(ALGraph &G,SqStack &T)
{
  int indegree[ MAX_VERTEX_NUM];
  int i,j,k,count;
  ArcNode *p;
  SqStack S;
  InitStack(S);  InitStack(T);
  count=0;

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

  for(i=0;i<G.vexnum;++i)  G.ve[i]=0;
  
  for(i=0;i<G.vexnum;++i)
    if(!indegree[i])Push(S,i);

  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]==0)  Push(S,k);
	   if(G.ve[j] +*(p->info) > G.ve[k])
         G.ve[k] = G.ve[j]+*(p->info);
    }
  // for(j=0;j<G.vexnum;++j)printf("%d--%d\n",j,indegree[j]);
  }
  if(count<G.vexnum)return ERROR;
  else return OK;
}

Status CriticalPath(ALGraph G)
{
  int i,j,k,dut,ee,el;
  ArcNode *p;
  SqStack T;
  char tag;
  
  if(! TopologicalOrder(G,T))return ERROR;

  for(i=0;i<G.vexnum;++i)
    G.vl[i]=G.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(G.vl[k]-dut<G.vl[j])G.vl[j]=G.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=G.ve[j];el=G.vl[k]-dut;
         tag=(ee==el)?'*':'@';
     	 printf("%c  %d-->%d  dut:%d  ee:%d  el:%d\n",tag,j,k,dut,ee,el);
      }
   return OK;
}

void main()
{
   ALGraph G;
   CreateDN(G);
   //DispGraph(G);
   if(! CriticalPath(G))printf("The graph G exist cycle !");
}