critical_path.c

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,int d[][3])  //n=顶点数，m=边数
{	int i;
	E_node *p;
	for(i=1;i<=n;i++)       //顶点结点初始化
	{	head[i].link=NULL;
		head[i].count=0;   
	}
	for(i=1;i<=m;i++)
	{	
		p=(E_node *)malloc(sizeof(E_node));  //新结点存放w
		p->adjvex=d[i-1][1];    //终点为w的边结点链到第v个链表
		p->act=i;
		p->dur=d[i-1][2];
		p->next=head[d[i-1][0]].link;
		head[d[i-1][0]].link=p;
		(head[d[i-1][1]].count)++;
	}
}

//输出邻接表
void Print(V_node head[],int n)
{	int i;
	E_node *p;
	for(i=1;i<=n;i++)
	{	printf("\nhead[%d]:%d",i,head[i].count);
		if(head[i].link)
		{	p=head[i].link;
			while(p)
			{
				printf("->[%d][%d][%d]",p->adjvex,p->dur,p->act);
				p=p->next;
			}
		}
		printf("\n");
	}
	printf("\n");
}

//计算事件最早发生时间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;
	int n=10,m=15; //T8.7.1
	int dat[][3]={{1,2,3},{1,3,2},{2,4,6},{3,4,3},{2,5,8},
				{4,5,4},{4,6,2},{3,6,7},{5,8,4},{5,7,6},
				{6,7,9},{6,9,6},{7,10,5},{8,10,4},{9,10,8}};
	//int n=9,m=13;//T8.6
	//int dat[][3]={{1,2,5},{1,3,7},{2,4,3},{3,4,6},{3,5,3},
	//			{4,5,4},{4,7,4},{4,6,4},{5,6,2},{5,8,5},
	//			{6,9,5},{7,9,4},{8,9,2}};

	printf("\n邻接表为：");
    adjlist(head,n,m,dat);
	Print(head, n);

	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");
	}
}