#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#include<iostream.h>
#include<malloc.h>
#include<iomanip.h>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
//***************************************************邻接表实现**********************************//
#define MAX 20
#define MVNum 20
typedef int VertexType1;
typedef int Vertexid;
typedef struct node{
int adjvex;
int dut;
struct node *next;
}EdgeNode;
typedef struct vnode{
VertexType1 vertex ;
Vertexid id;
EdgeNode *link;
}VNode,Adjlist[MAX];
typedef Adjlist AOELGraph;
void CreateGraph(AOELGraph &GL,int n,int e)
{
/*n为顶点数,e为图的边数*/
int i,j,k,l;
EdgeNode *p;
cout<<"请读入顶点信息和入度\n";
for(i=1;i<=n;i++)
{
//建立顶点表
cin>>GL[i].vertex;
cin>>GL[i].id;
GL[i].link=NULL;
}
cout<<"输入边<Vi,Vj>的i,j和边上的权值w:\n";
for(k=1;k<=e;k++)
{
cin>>i>>j>>l;
p=(EdgeNode *)malloc(sizeof(EdgeNode));//生成新的边表结点
p->adjvex=j; //将邻接点序号j赋值给新结点的邻接电域
p->dut=l;
p->next=GL[i].link;
GL[i].link=p; //将新结点插入到顶点Vi的边表头部
}
}
void CriticalPath(AOELGraph dig,int n,int e1)
{
int i,j,m,front,rear;
int k=0,x=0;
int flg[MVNum];
int ve[MVNum],vl[MVNum],e[MVNum],l[MVNum];
int tpord[MVNum];
EdgeNode *p;
for(i=1;i<=n;i++)
ve[i]=vl[i]=0;
front=0;
rear=0;
for(i=1;i<=n;i++)
{
if(dig[i].id==0)
{
rear++;
tpord[rear]=i;
}
}
m=0;
while(front!=rear)
{
front++;
j=tpord[front];
m++;
p=dig[j].link;
while(p!=NULL)
{
k=p->adjvex;
dig[k].id=dig[k].id-1;
if(ve[j]+p->dut>ve[k])
ve[k]=ve[j]+p->dut;
if(dig[k].id==0)
{
rear++;tpord[rear]=k;
}
p=p->next;
}
}
if(m<n)
{
cout<<"网中有回路!不能拓扑排序"<<endl;
return;
}
for(i=1;i<=n;i++)
vl[i]=ve[i];
for(i=n-1;i>=1;i--)
{
j=tpord[i];
p=dig[j].link;
while(p!=NULL)
{
k=p->adjvex;
if((vl[k]-p->dut)>vl[j])
vl[j]=vl[k]-p->dut;
p=p->next;
}
}
i=0;
for(j=1;j<=n;j++)
{
p=dig[j].link;
while(p!=NULL)
{
k=p->adjvex;
i++;
e[i]=ve[j];
l[i]=vl[k]-p->dut;
cout<<"顶点 "<<dig[j].vertex<<"到顶点"<<dig[k].vertex;
if(l[i]==e[i])
{cout<<"是关键活动"<<endl;flg[i]=1;}
else
{cout<<"不是关键活动"<<endl;flg[i]=0;}
p=p->next;
}
}
cout<<"这是邻接表存储结构实现"<<endl;
}
//***************************************************邻接矩阵实现**********************************//
typedef struct ArcCell{
int adj;/*顶点关系类型,用1表示相邻,0表示不相邻*/
}ArcCell,**AdjMatrix;/*邻接矩阵*/
typedef struct type{
char data[3];/*顶点值*/
int info;/*弧的长度*/
struct type *next;/*顶点的下一个指针*/
}VertexType;
typedef struct{
VertexType *vexs;/*顶点向量*/
AdjMatrix arcs;/*邻接矩阵*/
int vexnum,arcnum;/*图的顶点数和边数*/
}MGraph;
/* *******************/
typedef int Status;
#define STACK_INIT_SIZE 50
typedef int ElemType;
typedef struct STACK /*定义栈类型*/
{
ElemType *base;
ElemType *top;
int stacksize;
int length;
}SqStack,*Stack;
void InitStack(Stack *S) /*初始化栈*/
{
*S=(SqStack *)malloc(sizeof(SqStack));
(*S)->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!(*S)->base)exit(-1);
(*S)->top=(*S)->base;
(*S)->stacksize=STACK_INIT_SIZE;
(*S)->length=0;
}
Status DestroyStack(Stack *S) /* 销毁栈*/
{
free((*S)->base);
free((*S));
return 1;
}
Status StackEmpty(SqStack S) /*判断栈空否*/
{
if(S.top==S.base) return 1;
else
return 0;
}
void Push(Stack *S,ElemType e) /*把数据压入栈*/
{
if((*S)->top - (*S)->base>=(*S)->stacksize)
{
(*S)->base=(ElemType *) realloc((*S)->base,
((*S)->stacksize + 10) * sizeof(ElemType));
if(!(*S)->base)exit(-1);
(*S)->top=(*S)->base+(*S)->stacksize;
(*S)->stacksize +=10;
}
*((*S)->top++)=e;
++(*S)->length;
}
Status Pop(Stack *S,ElemType *e)/*删除栈顶元素*/
{
if((*S)->top==(*S)->base) return 0;
*e=*((*S)->top-1);
--(*S)->length;
(*S)->top--;
return 1;
}
/* ******************** */
void InitGraph(MGraph *G)/*初始图*/
{
int i,nu,mu;
printf("\n输入顶点的个数和(边)弧的个数:");
scanf("%d%d",&nu,&mu);
G->arcs=(ArcCell **)malloc(nu*sizeof(ArcCell *));
for(i=0;i<nu;i++)/*分配邻接矩阵空间*/
G->arcs[i]=(ArcCell *)malloc(nu*sizeof(ArcCell));
G->vexs=(VertexType *)malloc(nu*sizeof(VertexType));/*分配顶点空间*/
G->vexnum=nu;G->arcnum=mu;/*图的顶点数和边数*/
}
void DestroyGraph(MGraph *G)/* 销毁图*/
{
int i;
free(G->vexs);
for(i=0;i<G->vexnum;i++)
free(G->arcs[i]);
}
void InsertGraph(MGraph *G,int i,VertexType e)
{
if(i<0||i>G->vexnum) return;
G->vexs[i].next=e.next;
G->vexs[i].info=e.info;
strcpy(G->vexs[i].data,e.data);
}
int Locate(MGraph G,VertexType v1)/*确定v1在图顶点中的位置*/
{
int i;
for(i=0;i<G.vexnum;i++)
if(strcmp(v1.data,G.vexs[i].data)==0) return i;
return -1;
}
void CreateUND(MGraph *G)/*采用数组(邻接矩阵)和邻接表表示无向图*/
{
int i,j,k,*p,d,w;
VertexType v1,v2,*q2,*q;
p=(int *)malloc(G->vexnum*sizeof(int));
for(i=0;i<G->vexnum;i++) p[i]=0;
for(i=0;i<G->vexnum;++i)/*初始邻接表*/
{
for(j=0;j<G->vexnum;++j) G->arcs[i][j].adj=0;
}
printf("\n");
printf("按顺序输入顶点(方向)和它们的间长度以及终点:如 'v1 3 v2 ' : \n");
for(k=0;k<G->arcnum;++k)
{
printf("输入第 %d 条弧: \n",k+1);
d=0;
scanf("%s%d%s",v1.data,&w,v2.data);/*输入相邻的两个点值*/
i=Locate(*G,v1);
j=Locate(*G,v2);/*用i 和j来确定它们的位置*/
G->arcs[i][j].adj=1;
q2=(VertexType *)malloc(sizeof(VertexType));/*分配一个空间*/
strcpy(q2->data,
G->vexs[j].data);q2->info=w;
q2->next=NULL;/*以便连接在每个顶点后*/
if(p[i]==0) {
G->vexs[i].next=q2;p[i]++;
}/*i顶点后面还没有*/
else {
q=&(G->vexs[i]);/*i顶点后面有了*/
while(d!=p[i]) {d++;q=q->next;
}/*指到最后一个*/
p[i]++;
q->next=q2;/*接在最后*/
}
}
free(p);
}
void FindInDegree(MGraph G,int *indegree)/*对各顶点求入度,邻接矩阵的列*/
{
int i,j;
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
if(G.arcs[j][i].adj==1) indegree[i]++;
}
int *ve,*vl;/*最早发生时间和最迟发生时间数组,全局的*/
int TopologicalOrder(MGraph G,Stack *T)/*有向图采用邻接表存储结构,无回路返回1*/
{
Stack S;
int i,k,count,*indegree;
VertexType *p;
indegree=(int *)malloc(G.vexnum*sizeof(int));/*度数组空间*/
ve=(int *)malloc(G.vexnum*sizeof(int));/*最早发生时间的数组空间*/
for(i=0;i<G.vexnum;i++)
indegree[i]=0;/*初始化*/
for(i=0;i<G.vexnum;i++)
ve[i]=0;/*初始化*/
FindInDegree(G,indegree);/*求各点入度*/
InitStack(&S);/*初始化栈*/
InitStack(T);
for(i=0;i<G.vexnum;++i)
if(!indegree[i]) Push(&S,i);/*入度为0进栈*/
count=0;/*对输出顶点计数*/
while(!StackEmpty(*S))
{
Pop(&S,&i);/*拿出入度为0 的*/
Push(T,i);/*i号顶点入T栈*/
++count;/*计数*/
p=G.vexs[i].next;/*此层的下一个邻点*/
while(p)
{
k=Locate(G,*p);/*上面这个邻点的位置*/
if(!(--indegree[k])) Push(&S,k);/*减一后为0就入栈*/
if(ve[i]+p->info>ve[k]) ve[k]=ve[i]+p->info;/*在它的所有邻点中找出能使最大*/
p=p->next;/*这一层的其它邻点*/
}
}
DestroyStack(&S);
free(indegree);
if(count<G.vexnum) return 0;/*有向图有回路*/
else return 1;
}
int CriticalPath(MGraph G)/*G为有向网,输出G的各项关键活动*/
{
Stack T;
int j,k,dut,e1,e2;
char tag;
VertexType *p;
if(!TopologicalOrder(G,&T)) return 0;/*有回路就不做*/
vl=(int *)malloc(G.vexnum*sizeof(int));/*最迟发生时间数组空间*/
for(j=0;j<G.vexnum;j++)/*初始化事件的最迟发生时