数据结构之---C语言实现关键路径AOE图

//关键路径AOE
//杨鑫
#include   
#include 
#include 
//定义邻接表
typedef struct node  
{  
 	int  adjvex;  
 	int  w;  
 	struct node *nextedge;  
 }edgenode; 

//定义边集 
typedef struct
{  
      char     data;
      int      id;  
      edgenode  *firstedge;  
 }vexnode;   

void CreateGraph(vexnode* Graph,int vexnumber,int arcnumber)  
{  
     int i = 0, j = 0, k = 0;
	 int begin,end,duttem; 
	 char ch;
     edgenode *p;  
     for(i=0;i
);  
    for(k=0;kadjvex =end-1;  
        p->w =duttem;  
        Graph[end-1].id ++;
        p->nextedge =Graph[begin-1].firstedge ;  
        Graph[begin-1].firstedge =p;  
	}  
}
int SearchMapPath(vexnode* Graph,int vexnumber,int arcnumber)  
{  
	    int totaltime=0;
		int m=0;
    	int i,j,k,t; 
		char sv[100];
        int front,rear; 
		int *topology_queue,*vl,*ve,*el,*ee;
		front=rear=-1; 
		t=0;
        topology_queue=(int*)malloc(vexnumber*sizeof(int));    
        vl=(int*)malloc(vexnumber*sizeof(int));               
        ve=(int*)malloc(vexnumber*sizeof(int));               
        el=(int*)malloc(arcnumber*sizeof(int));           
        ee=(int*)malloc(arcnumber*sizeof(int));    
        edgenode *p;   
        for(i=0;iadjvex ;  
            Graph[k].id --;  
            if(ve[j]+p->w >ve[k])  
               ve[k]=ve[j]+p->w ;  
            if(Graph[k].id ==0) 
				topology_queue[++rear]=k;  
            p=p->nextedge ;  
		   }  
		}  
		if(m=0;i--)
	   {  
             j=topology_queue[i];
             p=Graph[j].firstedge;  
             while(p)
			 {  
               k=p->adjvex ;  
               if((vl[k]-p->w )w;  
               p=p->nextedge;  
			 }  
		}   
    	printf(| 起点 | 终点 | 最早开始时间 | 最迟开始时间 | 差值 | 是否为关键路径 
);  
		i=0; 
    	for(j=0;jadjvex;  
          		ee[++i]=ve[j];  
          		el[i]=vl[k]-p->w;  
 				printf(| %4c | %4c | %12d | %12d | %4d |,Graph[j].data ,Graph[k].data ,ee[i],el[i],el[i]-ee[i]);  
          		if(el[i]==ee[i]) 
				{ 
          			printf( 此弧为关键活动 ); 
		  			sv[t]=Graph[j].data;t++;
		  		}
          		printf(
); 
          		p=p->nextedge;  
	   		}
		}  
	  	printf(关键路径节点为：);
	  	sv[t]=Graph[vexnumber-1].data;
	  	for(i=0;i<=t;i++)
		{
		   printf(%c,sv[i]);
		   if(sv[i]!=Graph[vexnumber-1].data)
		    	printf(--->);
		}
	  	printf(
);
	  	printf(关键路径长度为：%d个单位时间
,totaltime); 
      	return 1;  
}  
int main( )  
{  
        int vexnumber,arcnumber,totaltime=0;    
        printf(请输入这个图中的节点数:);  
        scanf(%d,&vexnumber);  
        printf(请输入这个图中的弧数:);  
        scanf(%d,&arcnumber);
        vexnode* Graph=(vexnode*)malloc(vexnumber*sizeof(vexnode)); 
	    CreateGraph(Graph,vexnumber,arcnumber);  
        SearchMapPath(Graph,vexnumber,arcnumber);
		return 0;
}

 

结果：