數據結構之---C語言實現關鍵路徑AOE圖

數據結構之---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;
}

結果：