图的关键路径算法
图的关键路径算法(c语言版)
#include
#include
#include
#define max 10
#define S sizeof(struct v)
int a[max][max];
struct v
{
int num;
int len;
struct v *next;
};
struct degree
{
int ind;
struct v *p;
};
void al(int a[][10],int n,struct degree b[])/*邻接表生成函数*/
{
int i,j;
struct v *mov;
for(i=1;i
{
for(j=1;a[i][j]==0;j++);
if(j>n)
{
b[i].p=NULL;
continue;
}
b[i].p=(struct v *)malloc(S);
b[i].p->num=j;
b[i].p->len=a[i][j];
mov=b[i].p;
for(j++;j
if(a[i][j]!=0)
{
mov->next=(struct v *)malloc(S);
mov->next->num=j;
mov->next->len=a[i][j];
mov=mov->next;
}
mov->next=NULL;
}
}
void indegree(int a[][10],int n,struct degree b[])/*入度计算函数*/
{
int i,j;
for(j=1;j
{
b[j].ind=0;
for(i=1;i
if(a[i][j]!=0)
b[j].ind++;
}
}
int toposort(struct degree b[],int n,int topo[])/*拓扑排序函数*/
{
int i;
int circle=0;
int mark[max];
struct v *p;
int j=1;
for(i=1;i
mark[i]=0;
for(i=1;i
{
for(i=1;(b[i].ind!=0||mark[i]==1)&&i
if(i
{
topo[j]=i;
mark[i]=1;
j++;
for(p=b[i].p;p!=NULL;p=p->next)
b[p->num].ind--;
}
else
break;
}
if(j-1
circle=1;
return circle;
}
void etime(struct degree b[],int earlytime[],int n)/*最早开始时间生成函数*/
{
struct v *p;
int i,temp;
for(i=1;i
earlytime[i]=0;
for(i=1;i
{
p=b[i].p;
while(p!=NULL)
{
if((temp=earlytime[i]+p->len)>earlytime[p->num])
earlytime[p->num]=temp;
p=p->next;
}
}
}
void ltime(int topo[],struct degree b[],int n,int lastv,int lasttime[])/*最晚开始时间生成函数*/
{
struct v *p;
int i,temp,j;
for(i=1;i
lasttime[i]=lastv;
for(j=n-1;j>=1;j--)
for(p=b[topo[j]].p;p!=NULL;p=p->next)
if((temp=lasttime[p->num]-p->len)
lasttime[topo[j]]=temp;
}
void compare(int a[],int b[],int n)/*关键路径生成函数*/
{
int i;
printf("组成关键路径的节点有：\n");
for(i=1;i
if(a[i]==b[i])
printf("%3d",i);
printf("\n");
}
void main()
{
FILE *fp;
int i,j,n,circle,lastv;
int earlytime[max];
int lasttime[max];
char c;
struct degree b[max];
struct v *p;
int topo[max];
i=1;
j=1;
n=6;
if((fp=fopen("图.c","r"))==NULL)
{
printf("cannot open file\n");
exit(0);
}
while(!feof(fp))/*导入图的邻接矩阵表示*/
{
if((c=fgetc(fp))!='\n')
{
a[i][j]=c-48;
j++;
}
else
{
i++;
j=1;
}
}
printf("请核对该图的相关信息,a[i][j]表示i到j的路径长\n特别的，a[i][j]为零，则表示i到j不通\n"); for(i=1;i
for(j=1;j
{
printf("%d",a[i][j]);
if(j==n)
printf("\n");
}
printf("****************************\n由邻接矩阵生成该图的邻接表信息如下\n");
al(a,n,b);/*生成图的邻接表表示*/
indegree(a,n,b);
for(i=1;i
{
p=b[i].p;
if(p!=NULL)
printf("第%d个节点入度为%d,其直接后继有: ",i,b[i].ind);
else
printf("第%d个节点没有后继节点\n",i);
while(p!=NULL)
{
printf("节点%d,路径长%d; ",p->num,p->len);
p=p->next;
}
printf("\n");
}
circle=toposort(b,n,topo);/*拓扑排序，将生成的拓扑有序序列保存在topo数组中*/
if(!circle)
{
printf("****************************\n该图的拓扑有序序列如下\n");
for(i=1;i
printf("%3d",topo[i]);
}
else
{
printf("****************************\n对不起，该图存在环结构，无法进行后面的关键路径的相关处理\n"); printf("\n");
exit(0);
}
/*拓扑有序序列生成完毕*/
printf("\n*******************************\n");
printf("生成的各节点的最早开始时间如下\n");
etime(b,earlytime,n);/*生成各节点的最早开始时间*/
for(i=1;i
printf("%3d",earlytime[i]);
printf("\n");
printf("\n*******************************\n");
printf("生成的各节点的最晚开始时间如下\n");
lastv=earlytime[n];
ltime(topo,b,n,lastv,lasttime);/*生成各节点的最早开始时间*/
for(i=1;i
printf("%3d",lasttime[i]);
printf("\n*******************************\n");
compare(earlytime,lasttime,n);
printf("********************************\n谢谢使用本程序，再见\n\n\n");
}