#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;
}
评论