www.pudn.com > zb.rar > 006.c

#include 
#include 
#define MAXVEX 100 
#define TRUE 1 
#define FALSE 0 
#define MAXEDGE 100  
typedef struct EdgeNode EdgeNode; 
typedef struct EdgeNode * PEdgeNode; 
typedef struct EdgeNode * EdgeList; 
typedef float AdjType; 
 
struct EdgeNode 
{ int endvex;             /* 相邻顶点字段 */ 
  AdjType weight; 
  PEdgeNode nextedge;     /* 链字段 */ 
};                        /* 边表中的结点 */ 
typedef struct 
{ int vertex; 
  EdgeList edgelist;      /* 边表头指针 */ 
} VexNode; 
 
typedef struct 
{VexNode vexs[MAXVEX];    /* 顶点表中的结点 */ 
 int n;                  /* 图的顶点个数 */ 
}GraphList; 
 
typedef struct 
{int vexsno[MAXVEX];     /* 顶点在顶点表中的下标值 */ 
}Topo; 
 
void findInDegree(GraphList* g, int *inDegree)   /* 求出图中所有顶点的入度 */ 
{int i; 
 PEdgeNode p; 
 for(i=0; in; i++) 
   inDegree[i] = 0; 
 for(i=0; in; i++) 
 {p = g->vexs[i].edgelist; 
   while(p) 
    {++inDegree[p->endvex]; 
      p = p->nextedge; 
    } 
  } 
} 
 
void makeNewAOV(EdgeList p,int* indegree,int* top) 
{int k; 
 while(p)                               /* 删除以该顶点为起点的边 */ 
 {k=p->endvex; 
   indegree[k]--; 
  if(indegree[k]==0)                   /* 将新的入度为零的边入栈 */ 
  {indegree[k]=*top; 
    *top=k; 
  } 
  p=p->nextedge; 
 } 
} 
 
int topoSort(GraphList *paov,Topo *ptopo)             /* 拓扑排序算法*/ 
{EdgeList p; 
 int i, j,nodeno=0, top=-1; 
 int indegree[MAXVEX]; 
  findInDegree(paov,indegree);                /* 求出图中所有顶点的入度 */ 
  for(i=0; in; i++) 
    if(indegree[i]==0)                        /* 将入度为零的顶点入栈 */ 
      {indegree[i]=top; top=i; } 
        while(top!=-1) 
        {j=top; 
         top=indegree[top];               /* 取出当前栈顶元素 */ 
         ptopo->vexsno[nodeno]=paov->vexs[j].vertex; /* 将该元素输出到拓扑序列中 */ 
          ptopo->vexsno[nodeno++]=j; 
        p=paov->vexs[j].edgelist;         /* 取该元素边表中的第一个边结点 */ 
        makeNewAOV(p,indegree,&top);      /*删除该结点,构造新的AOV网*/ 
         } 
     if(nodenon)       /* AOV网中存在回路 */ 
      {printf("The aov network has a cycle.\n"); 
       return(FALSE); 
       } 
      return(TRUE); 
} 
 
void insert(GraphList*p,int a,int b,float weight) 
{   EdgeList pp; 
    PEdgeNode temp; 
    temp=(PEdgeNode)malloc(sizeof(EdgeNode)); 
    temp->endvex=b; 
    temp->nextedge=NULL; 
    temp->weight=weight; 
    pp=p->vexs[a].edgelist; 
    if(pp==NULL)p->vexs[a].edgelist=temp; 
    else{ 
        while(pp->nextedge!=NULL) 
            pp=pp->nextedge; 
        pp->nextedge=temp; 
    } 
} 
     
GraphList* makeList()            /* 邻接表的构造*/ 
{ GraphList*p; 
  int i; 
  int a,b,weight; 
  int s; 
  p=(GraphList*)malloc(sizeof(GraphList)); 
  printf("please input the number of the vertex:"); 
  scanf("%d",&(p->n)); 
  for(i=0;in;i++) 
    p->vexs[i].edgelist=NULL; 
  printf("please input the vertexs and the weight:\n"); 
  do{printf("from=>");   scanf("%d",&a); 
     printf("to=>");    scanf("%d",&b); 
     printf("weight=>");   scanf("%d",&weight); 
     insert(p,a,b,weight); 
     do 
     {printf("press 1 to go on input.    press 2  to stop.\n"); 
      scanf("%d",&s); 
      if(s<1||s>2) 
       printf("ERROR!input again.\n"); 
     }while(s<1||s>2); 
    }while(s!=2); 
    return p; 
} 
 
void countee(GraphList*paoe,Topo*ptopo, AdjType*ee)/* 计算数组ee*/ 
{int  i,j,k;EdgeList p; 
 for(i=0; in; i++)  ee[i]=0; 
 for(k=0; kn; k++)                           /* 求事件vj可能的最早发生时间ee(j) */ 
 {i=ptopo->vexsno[k]; p=paoe->vexs[i].edgelist; 
  while (p!=NULL) 
  {j=p->endvex; 
    if(ee[i]+p->weight>ee[j]) 
    ee[j]=ee[i]+p->weight; 
   p=p->nextedge; 
  } 
 } 
} 
 
void countle(GraphList *paoe,Topo*ptopo, AdjType*ee, AdjType*le)     /* 计算数组le*/ 
{int  i,j,k;EdgeList p; 
 for(i=0;in; i++)                  /* 求事件vi允许的最迟发生时间le(i) */ 
  le[i]=ee[paoe->n-1]; 
 for(k=paoe->n-2; k>=0; k--) 
 {i=ptopo->vexsno[k]; 
  p=paoe->vexs[i].edgelist; 
  while(p!=NULL) 
  {j=p->endvex; 
    if( (le[j]-p->weight)weight; 
     p=p->nextedge; 
  } 
 } 
} 
 
void counte_l(GraphList *paoe,Topo *ptopo, AdjType*ee,AdjType*le, AdjType*e, AdjType*l) 
{int i,j,k ;EdgeList p; k=0; 
  for(i=0;in;i++)    /* 求活动ak的最早开始时间e(k)及最晚开始时间l(k) */ 
  {p=paoe->vexs[i].edgelist; 
   while(p!=NULL) 
   {j=p->endvex; e[k]=ee[i]; 
    l[k]=le[j]-p->weight; 
    if(e[k]==l[k]) 
    printf(", ",i,j); 
    k++; 
    p=p->nextedge; 
   } 
  } 
} 
 
int CriticalPath(GraphList * paoe)    /* 关键路径算法*/ 
{AdjType ee[MAXVEX], le[MAXVEX], l[MAXEDGE], e[MAXEDGE]; 
 Topo topo; 
  if(topoSort(paoe,&topo)==FALSE)               /* 求AOE网的一个拓扑序列 */ 
    return(FALSE); 
  countee(paoe,&topo, ee);                 /*计算数组ee*/ 
  countle(paoe,&topo, ee,le);              /*计算数组le*/ 
  counte_l(paoe,&topo, ee,le, e, l);       /*计算数组e,l并输出结果*/ 
  printf("\n"); 
  return(TRUE); 
} 
 
gua() 
{ GraphList* p; 
  Topo topo; 
  int i; 
  p=makeList(); 
   if(topoSort(p,&topo)==TRUE) 
    if(CriticalPath(p)==FALSE) 
        printf("There is no critical path!\n"); 
    else 
    {printf("the critical path is:\n"); 
      for(i=0;in;i++) 
       printf("%d\t",topo.vexsno[i]); 
    } 
 getch(); 
}