关键路径.cpp

是用C语言实现的

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
using namespace std;
#define MAX_VERTEX_NUM 200
#define MAX 200
struct InfoType{
	int dut;  //权值
	int e;    //活动最早发生时间
	int l;    //活动最持发生时间
};//存放弧的信息

struct VerTex{
	int degree;
	int ve;
	int vl;
};

typedef struct ArcNode{
   int adjvex;  //该弧指向的顶点位置
   struct ArcNode *nexttarc;  //指向下一条弧的指针
   struct InfoType info;  //弧的信息
};

typedef struct VNode{
	VerTex ver;   //顶点入度
    ArcNode *firstarc;  //指向第一条依附该顶点的弧
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{
	AdjList vertices;
	int vexnum;  //图的当前顶点数
	int arcnum;  //图的当前弧数
}ALGraph;

void create(ALGraph &Gra,string name[]) //构造图
 { 
	  ArcNode *p;
      int num;
	  int arc;
	  int i;
	  int v1,v2,dut;
	  string v11,v22;
     num = 0;
	 arc = 0;
	 while(1)
	 {
	 cout<<"请输入工程名:";
	 cin>>name[num];
	 cout<<"是否继续 Y/N ";
	 num++;
	 getchar();char g =getchar();
	 if(g == 'N'||g == 'n') break;
	 }
	
    for (i=0; i<num; i++)    //初始化空关系图
	{ 
		 Gra.vertices[i].firstarc = NULL;
		 Gra.vertices[i].ver.degree = 0; 
         Gra.vertices[i].ver.ve = 0; 
		 Gra.vertices[i].ver.vl = 0; 
	}
	 cout<<"请输入一条弧:"<<endl;
     cout<<"例如:project1 project2 3   表示project1为弧尾 project2为弧头 3为权值"<<endl;
      for(; ;) 
      {
		  p = new ArcNode;
		  p->info.dut = 0;
		  p->info.e = 0;
		  p->info.l = 0;
		  cout<<"请输入:";
          cin>>v11>>v22>>dut;//读入一条弧
		  for(int k =0;k<num;k++)
		  {
			  if(name[k] == v11) v1 = k;
			  if(name[k] == v22) v2 = k;

		  }
          p->adjvex = v2;
		  p->info.dut = dut;
          p->nexttarc = Gra.vertices[v1].firstarc;
		  Gra.vertices[v1].firstarc = p; //插入在链表首部
          Gra.vertices[v2].ver.degree++;  //统计每个顶点的入度
		  arc++;
		  cout<<"是否继续输入 Y/N ";
		  char choose;
		  cin>>choose;
		  if(choose == 'N'||choose == 'n')
			  break;
		  
       } 
      Gra.vexnum = num;
	  Gra.arcnum = arc;
	 
}

int TopologicalSort(ALGraph &Gra,int Stack[],int &Stack_Top)
{
	//有向图G采用邻接表存储结构,求顶点时间的最早发生时间ve
    //若G无回路，则顶点的一个拓扑序列并返回1，否则0。
	//Stack为拓扑排序顶点栈,S为零入度顶点栈
	//若G有回路,则栈T返回一个拓扑系列,否则ERROR
	int S[MAX];  //存放入度为0的顶点的栈 
	Stack_Top = 0;
	int top = 0;
	int num1 = 0;
	int i;
	int out;
	int k;
    ArcNode *p;
	for(i = 0;i < Gra.vexnum ;i++)
	{
      Stack[i] = 0;
	}
    for(i = 0; i < Gra.vexnum ; i++)
          if (Gra.vertices[i].ver.degree == 0)    //入度为0顶点的编号进栈
          { 
               S[top]=i;
               top++;
          }
   while( top > 0)
   { 
          top--; 
          out=S[top]; 
		  Stack[Stack_Top] = out;
          Stack_Top++;
          num1++;
          p = Gra.vertices[out].firstarc;
          while (p != NULL)
          { 
                 k = p->adjvex;
                 Gra.vertices[k].ver.degree--; //顶点入度减1，
                 if (Gra.vertices[k].ver.degree == 0)  //若入度减为0，则入栈
                 {  
					 S[top]=k;
					 top++;
				 }
				 if(Gra.vertices[out].ver.ve + p->info.dut >  Gra.vertices[k].ver.ve) 
				 {
					  Gra.vertices[k].ver.ve = Gra.vertices[out].ver.ve + p->info.dut;
				 }
                 p=p->nexttarc; 
           }
    }
    if (num1 < Gra.vexnum)   return 0;   //该有向图有回路
    else return 1;
}

bool CriticalPath(ALGraph &Gra)
{
	//G为有向网，输出G的各项关键活动
	int Stack[MAX];
	int Stack_Top = 0;
	int out;
	int k;
	int j;
	int dut;
	int min = 32767 ;
    ArcNode *p;
	if(!TopologicalSort(Gra,Stack,Stack_Top)) return false;
	int i = 0;
	for(i = 0;i < Gra.vexnum; i++)
	{
		Gra.vertices[i].ver.vl = Gra.vertices[i].ver.ve;
	}
	while(Stack_Top > 0)
	{
		min = 32767;
        Stack_Top--;
        out = Stack[Stack_Top];
        p = Gra.vertices[out].firstarc;
		while(p)
		{
        k = p->adjvex;
		if(Gra.vertices[k].ver.vl - p->info.dut < min) 
		{
			min = (Gra.vertices[k].ver.vl - p->info.dut);
		}
		p = p->nexttarc;
		if( !p)
		{
		if(min > Gra.vertices[out].ver.vl) 
		{ 
			Gra.vertices[out].ver.vl = min;
		}
		}
	}
	
	}
    for(j = 0;j < Gra.vexnum; ++j)
	  for(p = Gra.vertices[j].firstarc; p ;p = p->nexttarc)
	  {
		  k = p->adjvex;
		  dut = p->info.dut;
		  p->info.e = Gra.vertices[j].ver.ve;
		  p->info.l = Gra.vertices[k].ver.vl - dut;
	  }
	  return true;
   
}

void menu()
{
   system("cls");
   cout<<"1. 建立AOE网的存储结构"<<endl;
   cout<<"2. 查询事件的最早发生时间"<<endl;
   cout<<"3. 查询事件的最迟发生时间"<<endl;
   cout<<"4. 查询活动的最早发生时间"<<endl;
   cout<<"5. 查询活动的最迟发生时间"<<endl;
   cout<<"6. 查询该工程的关键路径"<<endl;
   cout<<"0. 退出"<<endl;
   cout<<"请输入0-6:";

}
void main()
{
   ALGraph Gra;
   string name[MAX];
   ArcNode *p;
   int v1,v2;
   string v11,v22;
   int j;
   int choose;
   int k;
again:
   menu();
   cin>>choose;
   switch(choose)
   {
   case 1:
       create(Gra,name);
       if(!CriticalPath(Gra)) {cout<<"该图有回路 ERROR!建立失败，请重新建立"<<endl;}
	   else
	   {
		   printf("存储结构已建立");
	   }
	    printf("按任意键继续...");
	   getchar();
	   getchar();
	   goto again;
	    break;
   case 2:
       system("cls");
	   cout<<"请输入工程:";
       cin>>v11;
	   for(k =0 ;k<Gra.vexnum;k++)
	   {
		   if(name[k] == v11) v1 = k;
	   } 
       cout<<name[v1]<<"的最早发生时间:"<<Gra.vertices[v1].ver.ve<<endl;
	    printf("按任意键继续...");
	    getchar();
	   getchar();
	   goto again;
	   break;
   case 3:
       system("cls");
	   cout<<"请输入工程:"; 
	   cin>>v11;
	    for(k =0 ;k<Gra.vexnum;k++)
	   {
		   if(name[k] == v11) v1 = k;
	   } 
	   cout<<name[v1]<<"的最迟发生时间:"<<Gra.vertices[v1].ver.vl<<endl;
	    printf("按任意键继续...");
	    getchar();
	   getchar();
	   goto again;
	   break;
   case 4:
       system("cls");
	   cout<<"请输入活动:"<<endl;
	   cout<<"例如porject1 porject2  表示结点porject1 到 结点porject2的活动"<<endl;
	   cout<<"请输入:";
	   cin>>v11>>v22;
	   for(k=0;k<Gra.vexnum;k++)
	   {
		   if(name[k] == v11) v1 = k;
		   if(name[k] == v22) v2 = k;
	   }
	   for(p = Gra.vertices[v1].firstarc; p; p = p->nexttarc)
	   {
		   if(p->adjvex == v2)
			   break;
	   }
	   cout<<"活动"<<name[v1]<<" -> "<<name[v2]<<"  "<<"的最早发生时间: "<<p->info.e<<endl;
	    printf("按任意键继续...");
	    getchar();
	   getchar();
	   goto again;
	   break;
   case 5:
        system("cls");
	   cout<<"请输入活动:"<<endl;
	   cout<<"例如porject1 porject2  表示porject1 到porject2的活动"<<endl;
	   cout<<"请输入:";

	   cin>>v11>>v22;
	   for(k=0;k<Gra.vexnum;k++)
	   {
		   if(name[k] == v11) v1 = k;
		   if(name[k] == v22) v2 = k;
	   }
	   for(p = Gra.vertices[v1].firstarc; p; p = p->nexttarc)
	   {
		   if(p->adjvex == v2)
			   break;
	   }
	   cout<<"活动"<<name[v1]<<" -> "<<name[v2]<<"  "<<"的最迟发生时间: "<<p->info.l<<endl;
	    printf("按任意键继续...");
	    getchar();
	   getchar();
	   goto again;
	   break;
   case 6:
       for(j = 0;j < Gra.vexnum; ++j)
	     if(Gra.vertices[j].ver.ve == Gra.vertices[j].ver.vl) 
		 {
			 cout<<name[j]<<"->";
		 }
		 cout<<"\b\b  "<<endl;
		  printf("按任意键继续...");
	    getchar();
	   getchar();
		 goto again;
	   break;
   case 0:
	   exit(0);
	   break;
   }
 
}