critical_path.cpp

C++的电子教程

#include<stdio.h>
#include<stdlib.h>
#define Max 50

typedef struct e_node
{	int adjvex;      //邻结点
    int dur;         //活动持续时间(权值)    
	int act;         //活动的编号(a1,a2等)
	struct e_node *next;
}E_node;

typedef struct v_node
{	int count;
	E_node *link;
}V_node;

V_node head[Max];
int ee[Max],le[Max],tpv[Max],e[Max],l[Max];
//ee存放各事件最早发生时间，tpv存放拓扑序列
//e存放活动最早开始时间，l存放活动最迟开始时间

//邻接表的建立
void adjlist(V_node head[],int n,int m)  //n=顶点数，m=边数
{	int i,u,v,d;
	E_node *p;
	for(i=1;i<=n;i++)       //顶点结点初始化
	{	head[i].link=NULL;
		head[i].count=0;   
	}
	for(i=1;i<=m;i++)
	{	
		printf("Input Edge %d's start point : ",i);
		scanf("%d",&u);
		printf("==> end point : ");
		scanf("%d",&v);
		if((v>n) || (u>n))
		{	printf("Error! Input again.");
			continue;
		}
		printf("权值为：");
		scanf("%d",&d);
		p=(E_node *)malloc(sizeof(E_node)); //新结点存放w
		p->act=i;
		p->dur=d;
		p->adjvex=v;    //终点为w的边结点链到第v个链表
		p->next=head[u].link;
		head[u].link=p;
		(head[v].count)++;
	    printf("Edge %d : (v%d,v%d)\n",i,u,v);  //输出第i条边
	}
}

//计算事件最早发生时间ee
int c_ee(V_node adj[],int tpv[],int ee[],int n)     //n表示顶点总数
{
	int i,j,k;
	int top=0;
	E_node *t;
	for (i=1;i<=n;i++)
		if (adj[i].count==0)
		{
			adj[i].count=top;
			top=i;
		}
	i=0;
	while (top!=0)
	{
		j=top;
		top=adj[top].count;
		tpv[++i]=j;
		t=adj[j].link;
		while (t!=NULL)
		{
			k=t->adjvex;
			if (ee[k]<ee[j]+t->dur)
				ee[k]=ee[j]+t->dur;  //ee(k)计算公式
			if (--(adj[k].count)==0)
			{
				adj[k].count=top;
				top=k;
			}
			t=t->next;
		}
	}
	return i;
}

//计算事件最迟发生时间le
void c_le(V_node adj[],int tpv[],int le[],int path_len,int n)
//path_len为关键路径长度(即ee(n)的值)
{
	int i,j,k;
	E_node *t;
	for (i=1;i<=n;i++)
		le[i]=path_len;                //对le[i]赋初值为ee[n]
	for (i=n-1;i>0;i--)                //按拓扑序列逆序处理
	{
		k=tpv[i];                      //取边的开始顶点
		t=adj[k].link;;
		while (t!=NULL)
		{
			j=t->adjvex;                //取边的结束顶点
			if (le[k]>le[j]-(t->dur))
				le[k]=le[j]-(t->dur);   //le(k)计算公式
			t=t->next;
		}
	}
}

//计算活动的最早开始时间e
void c_e(V_node adj[],int ee[],int e[], int n)
{
	int i,j;
	E_node *t;
	for (j=1;j<n;j++)
	{
		t=adj[j].link;
		while (t!=NULL)
		{
			i=t->act;
			e[i]=ee[j];
			t=t->next;
		}
	}
}

//计算活动的最迟开始时间
void c_l(V_node adj[],int le[],int l[],int n)
{
	int i,j,k;
	E_node *t;
	for (k=1;k<=n;k++)
	{
		t=adj[k].link;
		while (t!=NULL)
		{
			j=t->adjvex;            //取边的终点
			i=t->act;               //取活动编号
			l[i]=le[j]-(t->dur );   //l[i]计算公式
			t=t->next;
		}
	}
}

//主函数
void main()
{
	int i,count,n,m;
    printf("\n 请输入图的顶点数n 边数m的值：");
	scanf("%d%d",&n,&m);
	adjlist(head,n,m);
	count=c_ee(head,tpv,ee,n);
	if (count<n)
		printf("AOE网中存在环路!\n");
	else
	{
		printf("\n 事件的最早发生时间ee为:  ");
		for (i=1;i<=n;i++)
			printf("%d ",ee[i]);
		c_le(head,tpv,le,ee[n],n);
		printf("\n 事件的最迟发生时间le为:  ");
        for (i=1;i<=n;i++)
			printf("%d ",le[i]);
		c_e(head,ee,e,n);
		printf("\n 活动的最早开始时间e为: ");
		for (i=1;i<=m;i++)
			printf("%d  ",e[i]);
		c_l(head,le,l,n);
		printf("\n 活动的最迟开始时间l为: ");
		for (i=1;i<=m;i++)
			printf("%d  ",l[i]);
		printf("\n 活动余量l[i]-e[i]为: ");
		for (i=1;i<=m;i++)
			printf("%d,  ",l[i]-e[i]);
		printf("\n 关键活动为: ");
		for (i=1;i<=m;i++)
			if (e[i]==l[i])
				printf("a%d,  ",i);
		printf("\n");
	}
}