#define max 20#include<iostream>#include<stdio.h>#include<malloc.h>using namespace std;typedef struct ArcNode//定义表结点{int adjvex;//该弧所指向顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 int info;//该弧的权值}ArcNode;typedef struct VNode//定义头结点{int data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[max];typedef struct//定义ALGraph{AdjList vertices; int vexnum,arcnum;//图的当前顶点数和弧数 int kind;//图的种类标志}ALGraph;typedef struct//定义栈 {int *base;//栈底 int *top;//栈顶}stack; void initstack(stack &s)//建立空栈{s.base=(int*)malloc(max*sizeof(int)); s.top=s.base;} int stackempty(stack s)//判断是否为空栈{if(s.base==s.top) return 1; else return 0;} int stackfull(stack s)//判断是否为满栈{if(s.top-s.base>=max)  return 1; else return 0;} int pop(stack &s)//进行出栈{int e;//出栈先进行赋值，后移动指针 if(!stackempty(s)) {e=*(s.top-1);  s.top--;  return e; } else return NULL;} void push(stack &s,int e)//进行入栈{if(!stackfull(s)){s.top++;//进栈先移动指针，后进行赋值 *(s.top-1)=e;}} void CreateDG(ALGraph &G)//创建邻接表的图{int k,i,j; char tag; cout<<"请输入图的顶点数目:"<<endl;//输入顶点数目 cin>>G.vexnum;    cout<<"请输入图的弧的数目:"<<endl;//输入弧的数目 cin>>G.arcnum;    cout<<"请确认是否输入弧的权值(y/n):"<<endl; cin>>tag; for(i=1;i<=G.vexnum;++i) {G.vertices[i].data=i;//初始化顶点值  G.vertices[i].firstarc=NULL;//初始化指针 }   cout<<"请输入弧的相关信息arc(V1-->V2)"<<endl;//构造弧 for(k=1;k<=G.arcnum;++k) {cout<<endl<<"请输入弧头"<<"[1,"<<G.vexnum<<"]:";  cin>>i;      cout<<"请输入弧尾"<<"[1,"<<G.vexnum<<"]:";  cin>>j;      while(i<1||i>G.vexnum||j<1||j>G.vexnum)//如果弧头或弧尾不合法,重新输入 {cout<<endl<<"请再次输入弧头"<<"[1,"<<G.vexnum<<"]:";  cin>>i;  cout<<"请再次输入弧尾"<<"[1,"<<G.vexnum<<"]:";  cin>>j;  }   ArcNode *p;  p=(ArcNode*)malloc(sizeof(ArcNode));//分配内存  if(!p)  {cout<<"Overflow!";//如果没有足够的空间,则退出  }  p->adjvex=j;//对弧结点的弧顶点数据域赋值  p->nextarc=G.vertices[i].firstarc;//对弧结点下一条弧指针域赋值  p->info=0;    // 对弧结点相关信息指针域赋值  G.vertices[i].firstarc=p; // 将弧结点插入到对应的单链表  if(tag=='y')  {cout<<"请输入弧的权值:";   cin>>p->info;  }  } } void ShowMGraph(ALGraph G)//输出图 G{int j; ArcNode *p; for(j=1;j<=G.vexnum;++j) {if(G.vertices[j].firstarc)  cout<<G.vertices[j].data<<"->";  else cout<<G.vertices[j].data<<">";  for(p=G.vertices[j].firstarc;p;p=p->nextarc)  cout<<p->adjvex<<" "<<p->info<<" "<<p->adjvex<<"->";  cout<<endl; }} int degree(ALGraph G,int i)//求各顶点的入度{int *indegree,j,k; indegree=(int*)malloc((G.vexnum+1)*sizeof(int)); ArcNode *p; for(j=1;j<=G.vexnum;j++) indegree[j]=0; for(j=1;j<=G.vexnum;j++){for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p->adjvex;  ++indegree[k]; }} return indegree[i]; } void critical(ALGraph G)//输出关键活动{ArcNode *p; int i,k,r,j,*ve,*vl,ee,el,count=0; int *indegree,length; indegree=(int*)malloc(G.vexnum*sizeof(int)); ve=(int*)malloc((G.vexnum+1)*sizeof(int)); vl=(int*)malloc((G.vexnum+1)*sizeof(int)); stack S,T; initstack(T); initstack(S); //一，求各顶点的入度for(j=1;j<=G.vexnum;j++)indegree[j]=degree(G,j);   //二，求各顶点最早发生的时间ve for(j=1;j<=G.vexnum;j++)//入度为零则进栈 if(indegree[j]==0) push(S,j);  for(j=1;j<=G.vexnum;j++)//对该数组初始化 ve[j]=0;  while(!stackempty(S)){i=pop(S); push(T,i); ++count; for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex; //顶点位置 if(--indegree[k]==0)  push(S,k); r=p->info; if(ve[i]+r>ve[k])    ve[k]=ve[i]+r; }//for结束}//while结束  if(count<G.vexnum) //判断AOE是否网有回路 {cout<<"AOE网有回路!"<<endl;  return; } //三，求各顶点的最迟时间 for(j=1;j<=G.vexnum;j++)//对vl数组进行初始化 vl[j]=ve[G.vexnum]; while(!stackempty(T)){j=pop(T); for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p->adjvex;  r=p->info;  if(vl[k]-r<vl[j])   vl[j]=vl[k]-r; }} //四，对活动的最早时间和最迟时间比较 cout<<"=============================================================="<<endl; printf(" 起点 终点 最早开始时间  最迟完成时间      差值    备注 \n"); for(j=1;j<=G.vexnum;j++) for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p->adjvex;  r=p->info;  ee=ve[j]; el=vl[k]-r;  printf("%4d  %4d   %4d             %4d        %4d ",j,k,ve[j],vl[k]-r,vl[k]-r-ve[j]);  if(ee==el)  cout<<"  是关键活动"<<endl;  else  cout<<"  不是关键活动"<<endl;  }//for结束 cout<<"=============================================================="<<endl; length=ve[G.vexnum]; cout<<endl<<"2.关键路径长度为："<<endl; cout<<" "<<length<<endl;//路径长度等于图最后顶点的最早时间} int main()//主函数{ALGraph G; cout<<"=============================="<<endl; cout<<"======1.创建邻接表图=========="<<endl; cout<<"======2.输出邻接表图=========="<<endl; cout<<"======3.寻找关键活动=========="<<endl; cout<<"======4.退出=================="<<endl; cout<<"=============================="<<endl; cout<<"请选择操作:"<<endl; int a; l1: {cin>>a; } system("cls"); while(a<=4) {switch(a) {case 1:      cout<<"请正确创建邻接表图:"<<endl;         CreateDG(G);          cout<<"Create ALGraph success !"<<endl;   cout<<"请选择操作:"<<endl;   goto l1;   break;  case 2:      cout<<"输出该邻接表图如下:"<<endl;   cout<<"=================="<<endl;         ShowMGraph(G);   cout<<"该图输出完毕!"<<endl;         cout<<"=================="<<endl;         cout<<"请选择操作:"<<endl;   goto l1;   break;  case 3:      cout<<"1.输出关键活动如下:"<<endl;         critical(G);         cout<<"请选择操作:"<<endl;         goto l1;      break;  case 4:      return 0; } } return 0;}  

评论