1.拓扑排序

一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。 所有的工程或者某种流程都可以分为若干个小的工程或者阶段，我们称这些小的工程或阶段为“活动”。 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网（Active On Vertex Network）。
拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1,V2,……,Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。 拓扑排序：所谓的拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

2.关键路径

  1. // 边表结点声明
  2. typedef struct EdgeNode
  3. {
  4.     int adjvex;
  5.     struct EdgeNode *next;
  6. }EdgeNode;
  8. // 顶点表结点声明
  9. typedef struct VertexNode
  10. {
  11.     int in;            // 顶点入度
  12.     int data;
  13.     EdgeNode *firstedge;
  14. }VertexNode, AdjList[MAXVEX];
  16. typedef struct
  17. {
  18.     AdjList adjList;
  19.     int numVertexes, numEdges;
  20. }graphAdjList, *GraphAdjList;
  22. int *etv, *ltv;
  23. int *stack2;            // 用于存储拓扑序列的栈
  24. int top2;                // 用于stack2的栈顶指针
  26. // 拓扑排序算法
  27. // 若GL无回路，则输出拓扑排序序列并返回OK，否则返回ERROR
  28. Status TopologicalSort(GraphAdjList GL)
  29. {
  30.     EdgeNode *e;
  31.     int i, k, gettop;
  32.     int top = 0;        // 用于栈指针下标索引
  33.     int count = 0;        // 用于统计输出顶点的个数
  34.     int *stack;            // 用于存储入度为0的顶点
  36.     stack = (int *)malloc(GL->numVertexes * sizeof(int));
  38.     for( i=0; i < GL->numVertexes; i++ )
  39.     {
  40.         if( 0 == GL->adjList[i].in )
  41.         {
  42.             stack[++top] = i;    // 将度为0的顶点下标入栈
  43.         }
  44.     }
  46.     // 初始化etv都为0
  47.     top2 = 0;
  48.     etv = (int *)malloc(GL->numVertexes*sizeof(int));
  49.     for( i=0; i < GL->numVertexes; i++ )
  50.     {
  51.         etv[i] = 0;
  52.     }
  53.     stack2 = (int *)malloc(GL->numVertexes*sizeof(int));
  55.     while( 0 != top )
  56.     {
  57.         gettop = stack[top--];        // 出栈
  58.         // printf("%d -> ", GL->adjList[gettop].data); 
  59.         stack2[++top2] = gettop;    // 保存拓扑序列顺序 C1 C2 C3 C4 .... C9
  60.         count++;                
  62.         for( e=GL->adjList[gettop].firstedge; e; e=e->next )
  63.         {
  64.             k = e->adjvex;
  65.             // 注意：下边这个if条件是分析整个程序的要点！
  66.             // 将k号顶点邻接点的入度-1，因为他的前驱已经消除
  67.             // 接着判断-1后入度是否为0，如果为0则也入栈
  68.             if( !(--GL->adjList[k].in) )    
  69.             {
  70.                 stack[++top] = k;
  71.             }
  73.             if( (etv[gettop]+e->weight) > etv[k] )
  74.             {
  75.                 etv[k] = etv[gettop] + e->weight;
  76.             }
  77.         }
  78.     }
  80.     if( count < GL->numVertexes )    // 如果count小于顶点数，说明存在环
  81.     {
  82.         return ERROR;
  83.     }
  84.     else
  85.     {
  86.         return OK;
  87.     }
  88. }
  90. // 求关键路径，GL为有向图，输出GL的各项关键活动
  91. void CriticalPath(GraphAdjList GL)
  92. {
  93.     EdgeNode *e;
  94.     int i, gettop, k, j;
  95.     int ete, lte;
  97.     // 调用改进后的拓扑排序，求出etv和stack2的值
  98.     TopologicalSort(GL);
  100.     // 初始化ltv都为汇点的时间
  101.     ltv = (int *)malloc(GL->numVertexes*sizeof(int));
  102.     for( i=0; i < GL->numVertexes; i++ )
  103.     {
  104.         ltv[i] = etv[GL->numVertexes-1];
  105.     }
  107.     // 从汇点倒过来逐个计算ltv
  108.     while( 0 != top2 )
  109.     {
  110.         gettop = stack2[top2--];    // 注意，第一个出栈是汇点
  111.         for( e=GL->adjList[gettop].firstedge; e; e=e->next )
  112.         {
  113.             k = e->adjvex;
  114.             if( (ltv[k] - e->weight) < ltv[gettop] )
  115.             {
  116.                 ltv[gettop] = ltv[k] - e->weight;
  117.             }
  118.         }
  119.     }
  121.     // 通过etv和ltv求ete和lte
  122.     for( j=0; j < GL->numVertexes; j++ )
  123.     {
  124.         for( e=GL->adjList[j].firstedge; e; e=e->next )
  125.         {
  126.             k = e->adjvex;
  127.             ete = etv[j];
  128.             lte = ltv[k] - e->weight;
  130.             if( ete == lte )
  131.             {
  132.                 printf("<v%d,v%d> length: %d , ", GL->adjList[j].data, GL->adjList[k].data, e->weight );
  133.             }
  134.         }
  135.     }
  136. }