aoe.cpp

里面有一自已设计的AOE和Kruska的算法,已通过运行,大家可以看看.

#include<iostream.h>
typedef int elemtype;
const int n=9;           //顶点数
const int e=11;          //弧数
class link
{
public:
	elemtype data;       //顶点序号
	int w;               //权值
	link *next;
};
class node
{
public:
	int ve[n+1],vl[n+1];  //顶点的最早开始,最迟开始时间
	int s1[100],s2[100];  
	int top1,top2;
	link a[n+1];
	void creatlink(node&g);
	void topsort(node&g);
	void critical_path(node &g);
};
//建立带入度的邻接表
void node::creatlink(node &g)
{
	int i,j,k,w;
	link *s;
	for(i=1;i<=n;i++)
	{
		g.a[i].data=0;
		g.a[i].next=NULL;
		g.a[i].w=0;
	}
	for(k=1;k<=e;k++)
	{
		cout<<"请输入第"<<k<<"条弧的具体情况"<<endl;
		cout<<"第"<<k<<"条弧的起点为:"<<'\t';
		cin>>i;
		cout<<"第"<<k<<"条弧的终点为:"<<'\t';
		cin>>j;
		cout<<"第"<<k<<"条弧的权值为:"<<'\t';
		cin>>w;
		cout<<endl;
		s=new link;
		s->data=j;s->w=w;
		s->next=g.a[i].next;
		g.a[i].next=s;
		g.a[j].data++;
	}
}
//求顶点的最早开始时间
void node::topsort(node &g)
{
	int j,k,m=0;link *p;
	top1=0;top2=0;
	for(int x=1;x<=n;x++)ve[x]=0;
	for(int i=1;i<=n;i++)
	{
		if(g.a[i].data==0)
		{
			top1++;
			s1[top1]=i;
		}
	}
	while(top1>0)
	{
		j=s1[top1--];
		s2[++top2]=j;
		m++;
		p=g.a[j].next;
		while(p!=NULL)
		{
			k=p->data;
			g.a[k].data--;
			if(g.a[k].data==0)s1[++top1]=k;
			if(ve[j]+p->w>ve[k])ve[k]=ve[j]+p->w;
			p=p->next;
		}
	}
}
//求关键路径
void node::critical_path(node &g)
{
	int j,k,kk,ee,el;
	link *p;
	for(int y=1;y<=n;y++)vl[y]=ve[n];
	while(top2>0)
	{
		j=s2[top2--];p=g.a[j].next;
		while(p!=NULL)
		{
			k=p->data;kk=p->w;
			if(vl[k]-kk<vl[j])vl[j]=vl[k]-kk;
			p=p->next;
		}
	}
	cout<<"关键路径为:";
	for(j=1;j<=n;j++)
	{
		p=g.a[j].next;
		while(p!=NULL)
		{
			k=p->data;kk=p->w;
			ee=ve[j];el=vl[k]-kk;
			if(ee==el)
			{
				cout<<"顶点"<<j<<"到顶点"<<k<<" ";
			}
			p=p->next;
		}
	}
	cout<<endl;
}
void main()
{
	node g;
	g.creatlink(g);
	g.topsort(g);
	g.critical_path(g);
}