1. #include "stdio.h"    
    2. #include "stdlib.h"   
    3. #include "io.h"  
    4. #include "math.h"  
    5. #include "time.h"
    7. #define OK 1
    8. #define ERROR 0
    9. #define TRUE 1
    10. #define FALSE 0
    12. #define MAXEDGE 30
    13. #define MAXVEX 30
    14. #define INFINITY 65535
    16. typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */  
    18. int *etv,*ltv; /* 事件最早发生时间和最迟发生时间数组，全局变量 */
    19. int *stack2;   /* 用于存储拓扑序列的栈 */
    20. int top2;       /* 用于stack2的指针 */
    22. /* 邻接矩阵结构 */
    23. typedef struct
    24. {
    25.     int vexs[MAXVEX];
    26.     int arc[MAXVEX][MAXVEX];
    27.     int numVertexes, numEdges;
    28. }MGraph;
    30. /* 邻接表结构****************** */
    31. typedef struct EdgeNode /* 边表结点  */
    32. {
    33.     int adjvex;    /* 邻接点域，存储该顶点对应的下标 */
    34.     int weight;        /* 用于存储权值，对于非网图可以不需要 */
    35.     struct EdgeNode *next; /* 链域，指向下一个邻接点 */
    36. }EdgeNode;
    38. typedef struct VertexNode /* 顶点表结点 */
    39. {
    40.     int in;    /* 顶点入度 */
    41.     int data; /* 顶点域，存储顶点信息 */
    42.     EdgeNode *firstedge;/* 边表头指针 */
    43. }VertexNode, AdjList[MAXVEX];
    45. typedef struct
    46. {
    47.     AdjList adjList; 
    48.     int numVertexes,numEdges; /* 图中当前顶点数和边数 */
    49. }graphAdjList,*GraphAdjList;
    50. /* **************************** */
    53. void CreateMGraph(MGraph *G)/* 构件图 */
    54. {
    55.     int i, j;
    56.     /* printf("请输入边数和顶点数:"); */
    57.     G->numEdges=13;
    58.     G->numVertexes=10;
    60.     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    61.     {
    62.         G->vexs[i]=i;
    63.     }
    65.     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    66.     {
    67.         for ( j = 0; j < G->numVertexes; j++)
    68.         {
    69.             if (i==j)
    70.                 G->arc[i][j]=0;
    71.             else
    72.                 G->arc[i][j]=INFINITY;
    73.         }
    74.     }
    76.     G->arc[0][1]=3;
    77.     G->arc[0][2]=4; 
    78.     G->arc[1][3]=5; 
    79.     G->arc[1][4]=6; 
    80.     G->arc[2][3]=8; 
    81.     G->arc[2][5]=7; 
    82.     G->arc[3][4]=3;
    83.     G->arc[4][6]=9; 
    84.     G->arc[4][7]=4;
    85.     G->arc[5][7]=6; 
    86.     G->arc[6][9]=2;
    87.     G->arc[7][8]=5;
    88.     G->arc[8][9]=3;
    90. }
    92. /* 利用邻接矩阵构建邻接表 */
    93. void CreateALGraph(MGraph G,GraphAdjList *GL)
    94. {
    95.     int i,j;
    96.     EdgeNode *e;
    98.     *GL = (GraphAdjList)malloc(sizeof(graphAdjList));
    100.     (*GL)->numVertexes=G.numVertexes;
    101.     (*GL)->numEdges=G.numEdges;
    102.     for(i= 0;i <G.numVertexes;i++) /* 读入顶点信息，建立顶点表 */
    103.     {
    104.         (*GL)->adjList[i].in=0;
    105.         (*GL)->adjList[i].data=G.vexs[i];
    106.         (*GL)->adjList[i].firstedge=NULL;     /* 将边表置为空表 */
    107.     }
    109.     for(i=0;i<G.numVertexes;i++) /* 建立边表 */
    110.     { 
    111.         for(j=0;j<G.numVertexes;j++)
    112.         {
    113.             if (G.arc[i][j]!=0 && G.arc[i][j]<INFINITY)
    114.             {
    115.                 e=(EdgeNode *)malloc(sizeof(EdgeNode));
    116.                 e->adjvex=j;                    /* 邻接序号为j */   
    117.                 e->weight=G.arc[i][j];
    118.                 e->next=(*GL)->adjList[i].firstedge;    /* 将当前顶点上的指向的结点指针赋值给e */
    119.                 (*GL)->adjList[i].firstedge=e;        /* 将当前顶点的指针指向e  */  
    120.                 (*GL)->adjList[j].in++;
    122.             }
    123.         }
    124.     }
    126. }
    129. /* 拓扑排序 */
    130. Status TopologicalSort(GraphAdjList GL)
    131. {    /* 若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */    
    132.     EdgeNode *e;    
    133.     int i,k,gettop;   
    134.     int top=0;  /* 用于栈指针下标  */
    135.     int count=0;/* 用于统计输出顶点的个数 */   
    136.     int *stack;    /* 建栈将入度为0的顶点入栈  */   
    137.     stack=(int *)malloc(GL->numVertexes * sizeof(int) );    
    138.     for(i = 0; i<GL->numVertexes; i++)                
    139.         if(0 == GL->adjList[i].in) /* 将入度为0的顶点入栈 */           
    140.             stack[++top]=i;    
    142.     top2=0;    
    143.     etv=(int *)malloc(GL->numVertexes * sizeof(int) ); /* 事件最早发生时间数组 */    
    144.     for(i=0; i<GL->numVertexes; i++)        
    145.         etv[i]=0;    /* 初始化 */
    146.     stack2=(int *)malloc(GL->numVertexes * sizeof(int) );/* 初始化拓扑序列栈 */
    148.     printf("TopologicalSort:\t");
    149.     while(top!=0)    
    150.     {        
    151.         gettop=stack[top--];        
    152.         printf("%d -> ",GL->adjList[gettop].data);        
    153.         count++;        /* 输出i号顶点，并计数 */ 
    155.         stack2[++top2]=gettop;        /* 将弹出的顶点序号压入拓扑序列的栈 */
    157.         for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
    158.         {            
    159.             k=e->adjvex;            
    160.             if( !(--GL->adjList[k].in) )        /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */                
    161.                 stack[++top]=k; 
    163.             if((etv[gettop] + e->weight)>etv[k])    /* 求各顶点事件的最早发生时间etv值 */                
    164.                 etv[k] = etv[gettop] + e->weight;
    165.         }    
    166.     }    
    167.     printf("\n");   
    168.     if(count < GL->numVertexes)        
    169.         return ERROR;    
    170.     else       
    171.         return OK;
    172. }
    174. /* 求关键路径,GL为有向网，输出G的各项关键活动 */
    175. void CriticalPath(GraphAdjList GL) 
    176. {    
    177.     EdgeNode *e;    
    178.     int i,gettop,k,j;    
    179.     int ete,lte;  /* 声明活动最早发生时间和最迟发生时间变量 */        
    180.     TopologicalSort(GL);   /* 求拓扑序列，计算数组etv和stack2的值 */ 
    181.     ltv=(int *)malloc(GL->numVertexes*sizeof(int));/* 事件最早发生时间数组 */   
    182.     for(i=0; i<GL->numVertexes; i++)        
    183.         ltv[i]=etv[GL->numVertexes-1];    /* 初始化 */        
    185.     printf("etv:\t");   
    186.     for(i=0; i<GL->numVertexes; i++)        
    187.         printf("%d -> ",etv[i]);    
    188.     printf("\n"); 
    190.     while(top2!=0)    /* 出栈是求ltv */    
    191.     {        
    192.         gettop=stack2[top2--];        
    193.         for(e = GL->adjList[gettop].firstedge; e; e = e->next)        /* 求各顶点事件的最迟发生时间ltv值 */        
    194.         {            
    195.             k=e->adjvex;            
    196.             if(ltv[k] - e->weight < ltv[gettop])               
    197.                 ltv[gettop] = ltv[k] - e->weight;        
    198.         }   
    199.     }    
    201.     printf("ltv:\t");   
    202.     for(i=0; i<GL->numVertexes; i++)        
    203.         printf("%d -> ",ltv[i]);    
    204.     printf("\n"); 
    206.     for(j=0; j<GL->numVertexes; j++)        /* 求ete,lte和关键活动 */        
    207.     {            
    208.         for(e = GL->adjList[j].firstedge; e; e = e->next)            
    209.         {                
    210.             k=e->adjvex;                
    211.             ete = etv[j];        /* 活动最早发生时间 */                
    212.             lte = ltv[k] - e->weight; /* 活动最迟发生时间 */               
    213.             if(ete == lte)    /* 两者相等即在关键路径上 */                    
    214.                 printf("<v%d - v%d> length: %d \n",GL->adjList[j].data,GL->adjList[k].data,e->weight);
    215.         }        
    216.     }
    217. }
    220. int main(void)
    221. {    
    222.     MGraph G;    
    223.     GraphAdjList GL;    
    224.     CreateMGraph(&G);
    225.     CreateALGraph(G,&GL);
    226.     CriticalPath(GL);
    227.     return 0;
    228. }