//006.h

#include <stdio.h>
#include <stdlib.h>
typedef int Status;
typedef int SElemType;

#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
typedef struct {
 SElemType *base;
 SElemType *top;
 int stacksize;
}SqStack;

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

Status StackEmpty(SqStack S)
{
 if(S.top==S.base)
  return OK;
 else
  return ERROR;
}

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;
 S.top++;
 return OK;
}

Status Pop(SqStack &S,SElemType e)
{
  if(S.top==S.base)
   return ERROR;
  e=*S.top;
  S.top--;
  return OK;
}

//007.h

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "006.h"
#define MAX_VERTEX_NUM 20
#define NULL 0
#define OK 1
#define ERROR 0

#define MAX_NAME 5
typedef int InfoType;
typedef int Status;
typedef int InfoType;
typedef char VertexType[MAX_NAME];//字符串类型

int ve[MAX_VERTEX_NUM];//全局变量

#define MAX_VERTEX_NUM 20
struct ArcNode
{
 int adjvex;
 ArcNode *nextarc;
 InfoType *info;
};//表结点

typedef struct{
 VertexType data;//顶点信息
 ArcNode *firstarc;//第一个结点的地址，指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];//头结点

struct ALGraph
{
 AdjList vertices;
 int vexnum,arcnum;
 int kind;
};

Status LocateVex(ALGraph G,VertexType u)
{
 int i;
 for(i=0;i<G.vexnum;i++)
  if(strcmp(u,G.vertices[i].data)==0)
   return i;
  return -1;
}

Status CreateGraph(ALGraph &G)
{
 int i,j,k;
 int w;
 ArcNode *p;
 VertexType va,vb;
 printf("请输入图的顶点数、边数:");
 scanf("%d,%d",&G.vexnum,&G.arcnum);
 printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
 for(i=0;i<G.vexnum;i++)//构造顶点向量
 {
  scanf("%s",G.vertices[i].data);
  G.vertices[i].firstarc=NULL;
 }
 printf("请输入每条弧的权值、弧尾和弧头(以空格作为间隔):\n");
 for(k=0;i<G.arcnum;k++)
 {
  scanf("%d%s%s",&w,va,vb);
  i=LocateVex(G,va);//弧尾
  j=LocateVex(G,vb);//弧头
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=j;
  p->info=(int*)malloc(sizeof(int));
  *(p->info)=w;
  p->nextarc=G.vertices[i].firstarc;//插在表头
  G.vertices[i].firstarc=p;
 }
 return OK;
}

void Display(ALGraph G)
{
 int i;
 ArcNode *p;
 printf("有向网:\n");
 printf("%个顶点:\n",G.vexnum);
 for(i=0;i<G.vexnum;i++)
      printf("%s",G.vertices[i].data);
 printf("\n%d条弧:\n",G.arcnum);
 for(i=0;i<G.vexnum;i++)
 {
  p=G.vertices[i].firstarc;
  while(p)
  {
   printf("%s-%s",G.vertices[i].data,G.vertices[p->adjvex].data);
   printf(":%d",*(p->info));
      p=p->nextarc;
  }
  printf("\n");
 }
}

void FindInDegree(ALGraph G,int indegree[])
{
   int i;
   ArcNode *p;
   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;
    }
   }
}

 

Status TopologicalOrder(ALGraph G,SqStack &T)
{
 //有向网G采用邻接表存储结构，求各个顶点事件的最早发生时间ve(全局变量).T为拓扑序列顶点栈，
 //S为零入度顶点栈，若G回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR
 int i,j,k,count,indegree[MAX_VERTEX_NUM];
 SqStack S;
 ArcNode *p;
 FindInDegree(G,indegree);
 InitStack(S);
 for(j=0;j<G.vexnum;j++)//建立零入度顶点栈S
  if(indegree[j]==0)
   Push(S,j);//入度为0者进栈
  InitStack(T);//初始化拓扑序列顶点栈
  count=0;//对输出顶点计数
  for(j=0;j<G.vexnum;j++)
   ve[j]=0;
  while(!StackEmpty(S))
  {
   //栈不空
   Pop(S,j);
   Push(T,j);
   ++count;
   for(p=G.vertices[j].firstarc;p;p=p->nextarc)
   {//对j号顶点的每个邻接点的入度减一
    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)
  {
   printf("此有向网有回路\n");
   return ERROR;
  }
  else
   return OK;
}

Status CriticalPath(ALGraph G)
{
 //G为有向网，输出G的各项关键活动
 int vl[MAX_VERTEX_NUM];
 SqStack T;
 int i,j,k,ee,el;
 ArcNode *p;
 char dut,tag;
 if(!TopologicalOrder(G,T))//产生有向环
  return ERROR;
 j=ve[0];
 for(i=1;i<G.vexnum;i++)
  if(ve[i]>j)
   j=ve[i];
  for(i=0;i<G.vexnum;i++)//初始化顶点事件的最尺发生时间(最大值)
   vl[i]=j;//完成点的最早发生时间}
       while(!StackEmpty(T))//按拓扑逆序求各顶点的vl值
     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;
     }
     printf("j k dut ee el tag\n");
     for(j=0;j<G.vexnum;++j) //求ee el 和关键活动
      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("%2d%2d%3d%3d%3d %c\n",j,k,dut,ee,el,tag);//输出关键活动
      }
      printf("关键活动为:\n");
      for(j=0;j<G.vexnum;++j)
       for(p=G.vertices[j].firstarc;p;p->nextarc)
       {
        k=p->adjvex;
        dut=*(p->info);
        if(ve[j]==vl[k]-dut)
         printf("%s-%s\n",G.vertices[j].data,G.vertices[k].data);
       }
       return OK;
}

 

 

// 主函数

#include <stdio.h>
#include <stdlib.h>
#include "007.h"

void main()
{
 ALGraph h;
 CreateGraph(h);
 Display(h);
 CriticalPath(h);
}