1.图的基本概念

• 图由有限顶点集V和有限边(弧)集E组成，顶点集不可为空，边(弧)集可为空
• 有向图：E是有向边(即弧)的有限集合，则图G是有向图。弧是顶点的有序对，记为<v, w>，顶点v是弧尾，顶点w是弧头
• 无向图：E是无向边(即边)的有限集合，则图G是无向图。边是顶点的无序对

• 自环：自环(Loop)是一条顶点与自身连接的边，即一条边的起点终点是同一个顶点

  
  
  自环
• 平行边：
  • 无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边
  • 有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的的方向相同)，称这些边为平行边
    
    平行边
• 多重图：含平行边的图称为多重图
• 简单图：既不含平行边也不包含自环的图称为简单图
• 完全图具有最多的边
  • 无向图边数的取值范围为0 ~ n×(n-1)/2，具有n×(n-1)/2条边的无向图是无向完全图，此时图中任意两个顶点之间都存在边
  • 有向图边数的取值范围为0 ~ n×(n-1)，具有n×(n-1)条弧的有向图是有向完全图，此时图中任意两个顶点之间都存在方向相反的两条弧
• 子图：图G'的顶点集V'和边集E'都是图G的子集，则G'是G的子图。并非V和E的任意子集都能构成G的子图，可能无法构成图
• 生成子图：子图的基础上满足，V' = V的子图G' 是G的生成子图
• 连通：无向图中，从顶点v到顶点w有路径存在，则v 和 w 是连通的
• 连通图：图中任意两个顶点都是连通的，否则为非连通图
• 连通分量：无向图的极大连通子图
• 强连通图：有向图中，v和w之间互有路径，则v 和 w 是强连通的，若图中任意两个顶点都是强连通的，否则为非连通图
• 强连通分量：有向图的极大强连通子图
• 生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图
  • 生成树是针对连通图而言的
  • 顶点数为n的图的生成树，有且仅有n-1条边，若多一条边，则树形结构破坏产生回路，若少一条边，则变成非连通图
• 顶点的度
  • 无向图TD(v)：指依附于顶点v的边的条数
  • 有向图：
    • 入度ID(v)：以顶点v为终点的有向边的数目
    • 出度OD(v)：以顶点v为起点的有向边的数目
  • 无论是有向还是无向图，所有顶点的入度出度之和 = 2e，其中e为边(弧)的个数
• 权值：每条边具有某种含义的数值
• 带权图(网)：边上带有权值的图
• 路径：顶点Vp到顶点Vq之间的一条路径是指顶点序列Vp，Vi1，Vi2，...，Vim，Vq
• 路径长度：路径上边的数目
• 回路(环)：第一个顶点和最后一个顶点相同的路径称为回路
• 简单路径：路径序列中，顶点不重复出现
• 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
• 距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离
• 有向树：仅一个顶点入度为0，其余顶点入度均为1的有向图

2.图的存储结构

• 邻接矩阵法

  • 对于一个具有n个顶点的图G=(V,E)

    • 顶点集合V可用一维数组存放
    • 顶点关系集合E可用n × n的二维数组AdjMatrix[n][n]存储，这个二维数组称为邻接矩阵

  • 无权图的邻接矩阵定义：

    
    
    无权图的邻接矩阵定义
    • 无向图的邻接矩阵是对称的
      
      一个无向图及其邻接矩阵表示法
    • 有向图的邻接矩阵可能不对称，如下图，且矩阵行只表示弧的发射关系
      
      一个有向图及其邻接矩阵表示法

  • 带权图的邻接矩阵定义：

    
    
    带权图的邻接矩阵定义

    • 一个无向带权图的邻接矩阵表示

      
      
      一个无向带权图的邻接矩阵表示
    • 一个有向带权图的邻接矩阵表示
      • 有向带权图的邻接矩阵表示中，顶点i到自身的距离，即A[i][i] = 0，而非∞，即有向带权图的邻接矩阵对角线元素全为0
        
        一个有向带权图的邻接矩阵表示

  • 邻接矩阵法的特点和性质：

    • 无向图顶点Vi的度TD(Vi) = 邻接矩阵第i行(或第i列)元素之和
    • 有向图顶点Vi的出度OD(Vi) = 邻接矩阵第i行元素之和
    • 有向图顶点Vi的出度ID(Vi) = 邻接矩阵第i列元素之和
    • 适合稠密图的存储，对稀疏图而言，存储空间浪费较大
    • 一个图的邻接矩阵表示是唯一的

  • 邻接矩阵法性能分析：

    • 确定边关系的时间复杂度为O(1)，随机访问二维数组A[i][j]就可确定vi,vj的边关系
    • 加入或删除一条边的时间复杂度为O(1)，即将二维数组A[i][j]的值进行更新
    • 寻找一个顶点所有邻接点的时间复杂度 = O(n)，即遍历该行数组全部元素
    • 邻接矩阵法空间复杂度 = O(n^2)，n为图的顶点个数
• 邻接表法
  • 结合了顺序存储和链式存储
  • 对图G中每个顶点Vi建立一个单链表，这个单链表存储所有依附于Vi的边(弧)，称之为边表
  • 边表的头指针(指向边表第一个结点)和顶点的数据信息用顺序存储，称为顶点表
  • 故邻接表中存在两种结点：顶点表结点，边表结点
  • 带权图的边表结点info域可存储权值
    
    顶点表和边表结点结构
    
    
    一个无向图及其邻接表结构
  • 邻接表法的特点和性质：
    • 适合稀疏图
    • 一个图的邻接表表示不唯一
    • 无向图中边表结点个数 = 2 * E，E为图的边的个数
    • 有向图中边表结点个数 = 弧的个数
    • 无向图，顶点vi的度就是其对应邻接链表中结点个数
    • 有向图，顶点vi的出度OD(vi) = vi的邻接链表结点个数，入度ID(vi) = 所有邻接链表adjvex域值为i-1(顶点表下标从0开始)的结点个数
  • 邻接表法的性能分析：
    • 确定边关系的时间复杂度为O(n)，即扫描边的起点对应顶点的邻接链表
    • 加入或删除一条边的时间复杂度为O(n)
    • 寻找一个顶点所有邻接点的时间复杂度为O(n)
    • 无向图所需存储空间为O(n + 2e)，即n个顶点和2e条边
    • 有向图所需存储空间为O(n + e)，即n个顶点和e条弧
• 十字链表法(仅对有向图)
  • 十字链表法的顶点结点和弧结点结构
    • firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表弧结点；
    • firstout 指针用于连接以当前顶点为弧尾的第一个链表弧结点；
    • data 用于存储该顶点中的数据；
      
      顶点结点
    • tailvex 用于存储弧尾的顶点位于数组中的位置下标；
    • headvex 用于存储弧头的顶点位于数组中的位置下标；
    • hlink 指针：指向弧头相同的下一条弧；
    • tlink 指针：指向弧尾相同的下一条弧；
    • info 指针：用于存储与该弧相关的信息，例如权值
      
      弧结点
      
      
      一个有向图及其十字链表表示
  • 一个图的十字链表表示不唯一，但一个给定的十字链表确定一个图
• 邻接多重表法(仅对无向图)
  • 是一种链式存储结构
  • 每条边用一个边结点表示
  • 邻接多重表法的顶点结点和边结点结构
    • data：存储此顶点的数据；
    • firstedge：指针域，指示第一条依附于该顶点的边。
      
      顶点结点
    • mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
    • ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标；
    • ilink：指针域，指向下一条依附于顶点ivex的边
    • jlink：指针域，指向下一条依附于顶点jvex的边
    • info：指针域，用于存储与该边有关的其他信息，比如无向网中各边的权；
      
      边结点

  • 一个无向图及其邻接多重表示

    
    
    一个无向图及其邻接多重表示

3.图的遍历

• 图的遍历：指从图中某一顶点出发，按照一定策略访问图中每一个顶点，且使每个顶点仅被访问一次
• 图的遍历过程需设置Visited[0..n-1]数组，用于标记每个顶点是否被访问过，初值为false，被访问置true，可防止某个顶点被多次访问，遍历算法结束时可检查Visited[0..n-1]数组是否仍有未访问顶点
• DFS深度优先搜索

  • 基本思想

    • 初始状态图中所有顶点都未被访问，选取一个顶点v0开始搜索，访问v0并将其标志位Visited置为true，然后访问v0的未被访问过的邻接点v1
    • 从顶点v1出发递归地按照深度优先搜索遍历
    • 当顶点vi的所有邻接点都被访问过时，回退到调用它的顶点寻找下一个拥有未被访问过的邻接点的顶点vj
    • 再从顶点vj出发递归地按照深度优先搜索遍历
    • 重复上述过程直到从源点v0的所有邻接边都被检测过为止，此时图中所有与源点v0有路径可达的顶点都已被访问过
    • 若此时图中仍有顶点未被访问，则另选图中一个未被访问的顶点作为新源点，重复上述过程直至图中所有顶点都被访问过为止

  • 一个无向图及其深度优先遍历序列

    • 该无向图的深度优先遍历序列为：v1->v2->v4->v8->v5->v3->v6->v7
      
      一个无向图
    • 深度优先搜索遍历一个连通图时，所经过的顶点和边的组合就是图的生成树，DFS遍历非连通图得到生成森林，由于深度优先遍历序列不唯一，故深度优先生成树也不唯一
      
      上面无向图对应的深度优先生成树

  • 一个无向非连通图及其深度优先生成森林

    • 无向非连通图深度优先生成森林的画法：从源点1开始，邻接的未被访问的顶点2作为其生成树中的孩子结点，然后顶点2邻接的未被访问的顶点又作为生成树中2的孩子结点，直至达到最大深度， 然后回退到下一个拥有未被访问过的邻接点，这里是1，它具有顶点3，重复上述过程，于是3在生成树中作为1的另一个孩子，重复此过程直至当前连通分量所有顶点都已加入生成树，然后从另一个连通分量开始重复上述过程直至图中所有顶点都已加入生成森林
      
      一个无向非连通图及其深度优先生成森林

    • 对非连通图的深度优先生成森林可以用左孩子右兄弟法将其转换为一棵二叉树进行存储

      
      
      上图无向非连通图的深度生成森林对应的二叉树

  • 一个有向非连通图及其深度优先生成森林

    • 有向非连通图深度优先生成森林的画法：从源点1开始，邻接的未被访问的顶点2作为其生成树中的孩子结点，然后顶点2邻接的未被访问的顶点6又作为生成树中2的孩子结点，直至达到最大深度， 然后回退到下一个拥有未被访问过的邻接点，这里是1，它具有顶点5，重复上述过程，直至当前强连通分量所有顶点都已加入生成树，然后从另一个未加入生成森林的顶点开始重复上述过程直至图中所有顶点都已加入生成森林
      
      一个有向非连通图及其深度优先生成森林

  • DFS深度优先遍历特点和性能分析：

    • 深度优先遍历序列通常不唯一，对于同一个图，基于邻接矩阵的遍历得到的DFS和BFS序列唯一，但基于邻接表的遍历所得到的DFS和BFS序列通常不唯一
    • 由于递归需借助工作栈，故DFS的空间复杂度为O(n)
    • 遍历图耗费的时间取决于图所用的存储结构，与是DFS还是BFS算法无关，
      • 当采用邻接矩阵存储图时，查找每个顶点的邻接点所需时间为O(n)，故遍历所有顶点所需时间为O(n^2)
      • 当采用邻接表存储图时， 查找所有顶点的邻接点所需时间为O(e)，访问所有顶点所需时间为O(n)，故遍历总共所需时间为O(n+e)，
• BFS广度优先搜索
  • 基本思想：
    • 初始状态图中所有顶点都未被访问，选取一个源点顶点v0开始搜索，访问v0并将其标志位Visited置为true
    • 访问v0所有的直接邻接点
    • 在依次访问完v0的各个邻接点后，再分别按照这些邻接点被访问的先后次序，依次访问与它们邻接的所有未被访问过的顶点，直至图中所有已被访问过的顶点的邻接点都被访问到
    • 若此时图中仍有顶点未被访问，另选一个未被访问的顶点作为新的源点，重复上述过程直至图中所有顶点都被访问
  • 一个无向图及其广度优先遍历序列

    • 该无向图的广度优先遍历序列为：v1->v2->v3->v4->v5->v6->v7->v8
      

      一个无向图
      
      
      该无向图的广度优先生成树

    • 非连通图采用广度优先搜索算法进行遍历时，经过的顶点以及边的集合为该图的广度优先生成森林

      • 无向非连通图广度生成森林的画法：从顶点1开始，1的所有邻接点作为生成树中1的孩子结点，然后按层序对每个结点，其所有未被访问的直接邻接点作为当前结点的孩子结点，直至当前连通分量所有顶点都已加入当前生成树中，然后重新选取另一个连通分量任一顶点，重复上述过程，直至图中所有顶点都已加入生成森林中
        
        一个无向非连通图及其广度优先生成森林

    • 对非连通图的广度优先生成森林可以用左孩子右兄弟法将其转换为一棵二叉树进行存储

      
      
      上图无向非连通图的广度生成森林对应的二叉树
  • 一个有向非连通图及其广度优先生成森林
    • 有向非连通图广度生成森林的画法：从顶点1开始，1为弧尾的所有弧头顶点作为生成树中1的孩子结点，然后按层序对每个结点，所有以其为弧尾的所有未被访问的弧头顶点作为当前结点的孩子结点，直至当前强连通分量所有顶点都已加入当前生成树中，然后重新选取一个尚未加入生成森林的任一顶点，重复上述过程，直至图中所有顶点都已加入生成森林中
      
      一个有向非连通图及其广度优先生成森林

4.图的应用

• 最小生成树
  • 生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图
  • 生成树的代价：∑Weight ei，生成树中所有边的权值之和
  • 最小生成树：代价最小的生成树
  • 有向图和无向图都有最小生成树，只不过有向图的最小生成树叫最小树形图，生成算法比较复杂
  • 无权图有生成树，有权图有最小生成树(此时生成树的代价最小)
  • 最小生成树是基于权值的概念的，无权图讨论最小生成树没什么意义
  • 最小生成树的树形可能不唯一，但所有最小生成树的代价相同
  • 当各边权值互不相等时，最小生成树唯一
  • 最小生成树满足E = V - 1，E为边个数，V为顶点个数
  • 最小生成树的生成算法：
  • Prim算法(扩点法)
    • 初始从图中任取一个顶点加入树T
    • 然后选择一个与当前T中顶点集合距离最近的不属于T的顶点，将该顶点和相应边加入T,直至图中所有顶点都并入T，便得到图的最小生成树
      
      Prim算法构造最小生成树过程
  • Kruskal算法(扩边法)
    • 设G = (V,E)是连通图，其最小生成树T = (U,Et)
    • 初始时：U = V, Et = ∅，
    • 循环：按G的边的权值递增顺序依次从E-Et中选择一条边，若加入这条边后T不构成回路，则将其加入Et，否则舍弃，直到Et中含有n-1条边
      
      Kruskal算法构造最小生成树过程
  • 画生成树时，无论是Prim算法还是Kruskal算法，都在原图的顶点形状结构基础上进行演变

• 最短路径
  • 首先要明确一个概念：带权图的最短路径问题中，路径长度是指路径上各边的权值之和，而不带权的图，路径长度是指路径上边的个数(相当于所有边权值为1)
  • 路径代价：路径上所有边的权值之和
  • 单源最短路径：求从源点vs到图G中其余各个顶点的最短路径，常用Dijkstra算法
  • Dijkstra算法
    • Dijkstra算法基本思想
      • 将图的顶点集划分为两个集合：S和V-S，其中S存放已确定最短路径的终点顶点的集合
      • 初始状态：S只包含源点vs，每求得一条最短路径就将该路径的终点顶点加入集合S，直至图中全部顶点都已加入S中，即S = V
    • 需引入一个辅助数组dist[i]，表示当前所找到的从源点vs到终点vi的最短路径长度
  • Dijkstra算法基本步骤
    • 令S = {vs}，并对dist[i]数组按如下公式赋初值：
      
    • 选择顶点vj，使得
    • vj就是所求出的下一条最短路径的终点顶点，将vj并入集合S中，即S = S ∪ {vj}
    • 对所有vi ∉ S，更新dist[i]数组值，因为并入vj后源点vs到V-S集合中顶点的最短路径长度可能发生变化，即有可能dist[j] + weight(j,i) < dist[i]，此时应使dist[i] = dist[j] + weight(j,i)
    • 重复上述步骤，直到S = V为止，此时就求出了源点vs到其余所有顶点的最短路径
  • 为了存储最短路径序列，需引入另一个辅助数组pre[j]，记录最短路径上vj的前一个顶点vi，即pre[j] = i，对于最短路径(vs,...,vi,vj)，由pre[j]找到vj前一个顶点vi，再由pre[i]找到vi的前一个顶点，以此类推直到找到源点vs为止。这样就可根据pre数组输出所有从vs到其他顶点的最短路径
  • 一个带权有向图使用Dijkstra求最短路径的实现过程
    
    Dijkstra求最短路径的实现过程
  • 多源最短路径：求图中任意两个顶点间的最短路径
  • Floyd算法
    • 基本思想：
      • 从任意顶点vi到任意顶点vj的最短路径只有两种情况：
        • ①直接从vi到vj，中间不经过任何顶点
        • ②从顶点vi经过若干中间顶点到达vj
      • 故设一个顶点集合S表示最短路径上可能包含的中间顶点 ，其初态为空
      • 引入一个二维数组dist[i][j]，其每个分量dist[i][j]存储从vi只经过集合S中的中间顶点到达vj的最短路径长度，初始状态时有如下公式：
        
      • 将图中的所有顶点v1, ... , vn-1依次加入集合S, 每加入一个新顶点就更新dist[i][j]，直到所有顶点都加入S集为止，此时dist n [i][j]就是从vi到vj的最短路径长度
    • 假设当前的S = {v1, ... , vk-1}，此时dist k-1 [i][j]存放的是从vi出发只经过中间顶点{v1, ... , vk-1}到达vj的最短路径长度，则S集加入一个新顶点vk后，新顶点vi到vj的最短路径有两种可能：
      • ①vk为最短路径上的中间结点，此时路径为{vi, ... , vk, ... , vj}，路径长度为dist k-1 [i][k] + dist k-1 [k][j]
      • ②vk不为最短路径上的中间结点，此时路径为{vi, ..., vj}，路径长度为dist k-1 [i][j]
        则可以确定dist k [i][j]的值：
        
    • 引入二维数组path[i][j]，每个分量存放改变路径的中间点，若path[i][j] = k，说明从vi到vj的最短路径经过vk，初始时，path [i][j] = -1，表示vj到vj不经过任何顶点，包括vi无法到达vj，当某个顶点vk加入S后使得dist[i][j]变小时，修改path[i][j] = k
      
      一个带权有向图及其Floyd算法实现过程
  • 根据path数组，可以得到每对顶点的最短路径，上图所示的带权有向图的最短路径表如下图：
    
    上面带权有向图的最短路径

• 有向无环图(DAG图)描述表达式
  • 算法步骤：
    • ① 把各个操作数不重复地排成一排
    • ②标出算术表达式中各个运算符的生效顺序
    • ③运算符按生效顺序作为双亲结点不断加入图中，
    • ④对生成的图添加箭头方向，箭头方向为从运算符指向两个操作数
• 拓扑排序

  • AOV网：若用DAG图表示一个工程，Activity of Vertex，顶点表示活动，用有向边<vi, vj>表示活动vi必须先于vj进行这样一种关系，则这种有向图称为顶点表示活动的网络，记为AOV网，需注意，AOV网不能有回路/环

  • 拓扑排序定义：由一个DAG图顶点组成的序列，当且仅当满足以下条件时，称为该图的一个拓扑排序：

    • 每个顶点出现且仅出现一次(不能有重复)
    • 若序列中，顶点A排在顶点B之前，则图中不存在从顶点B到顶点A的路径

  • AOV网进行拓扑排序算法步骤：

    • ①从AOV网中选择一个入度为0的顶点并输出
    • ② 从网中删除该顶点和所有以它为起点的有向边
    • ③ 重复①②直到当前AOV网为空或当前网中不存在入度为0的顶点(说明有向图中有环)
      
      有向无环图的拓扑排序过程

  • AOV网进行逆拓扑排序算法步骤：

    • ①从AOV网中选择一个出度为0的顶点并输出
    • ② 从网中删除该顶点和所有以它为终点的有向边
    • ③ 重复①②直到当前AOV网为空

  • 若一个顶点有多个直接后继，则拓扑排序结果通常不唯一，但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的

• 关键路径
  • AOE网：Activity of Edge，有向边表示活动，边上的权值表示完成该活动的开销。称之为边表示活动的网络，同AOV网一样，也是DAG图
  • AOE网有向边有权值，AOV网有向边无权值
  • AOE网的两个重要性质：
    • ①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始(事件活动二者同时开始)
    • ②只有进入某顶点的各有向边所代表的活动都结束时，该顶点所代表的事件才能发生
  • AOE网仅有一个入度为0的顶点，称为源点，表示整个工程的开始，仅有一个出度为0的顶点，称为汇点，表示整个工程的结束
  • AOE网中，源点到汇点的有向路径可能有多条，故有些活动可以并行
  • 只有所有路径上的活动都已经完成，整个工程才算结束，这意味着从源点到汇点路径长度最长的路径，即关键路径上的活动关键活动全都完成时，整个工程才算结束，也即完成整个工程的最短时间 = 关键路径长度 = 关键路径上各活动花费开销总和
  • 事件vk的最早发生时间ve(k)
    • 指从源点v1到顶点vk的最长路径长度，ve(k)决定了所有从vk开始的活动能够开工的最早时间，可用如下递归公式计算：
      • ve(源点) = 0
      • ve(k) = Max{ve(j) + weight(vj, vk)}
    • 计算ve(k)值时，按从前往后顺序进行，可以在拓扑排序的基础上进行：
      • ①初始时，令ve[1...n] = 0
      • ②输出一个入度为0的顶点vj时，计算它所有直接后继顶点vk的最早发生时间，若ve[j] + weight(vj, vk) > ve[k]，则令ve[k] = ve[j] + weight(vj, vk)，以此类推直至输出全部顶点
        
        事件 vk 的最早发生时间 ve(k)
  • 事件vk的最迟发生时间vl(k)
    • 指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间，可用如下递归公式计算：
      • vl(汇点) = ve(汇点)
      • vl(k) = Min{vl(j) - weight(vk, vj)}
    • 计算vl(k)值时，按从后往前顺序进行，可以在逆拓扑排序的基础上进行，增设一个栈用以记录拓扑序列，那么从栈顶到栈底就是逆拓扑有序序列：
      • ①初始时，令vl[1...n] = ve[n]
      • ②栈顶顶点vj出栈，计算其所有直接前驱顶点vk的最迟发生时间，若vl[j] - weight(vk, vj) < vl[k]，则令vl[k] = vl[j] - weight(vk, vj)，以此类推直至输出全部顶点
        
        事件 vk 的最迟发生时间 vl(k)
  • 活动ai的最早开始时间e(i)
    • 指该活动弧起点所表示事件的最早发生时间，若边<vk, vj>表示活动ai，则有e(i) = ve(k)
      
      活动 ai 的最早开始时间 e(i)
  • 活动ai的最迟开始时间l(i)
    • 指该活动弧终点所表示事件的最迟发生时间与该活动所需时间之差，若边<vk, vj>表示活动ai，则有l(i) = vl(j) - weight(vk, vj)
      
      活动 ai 的最迟开始时间 l(i)
  • 活动ai的最迟开始时间l(i)和最早开始时间e(i)的差额d(i) = l(i) - e(i)
    • 指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动ai可拖延的时间
    • d(i) = 0的活动ai是关键活动
• 求关键路径的算法步骤：
  • ①从源点出发，令ve(源点) = 0，按拓扑有序求其余顶点最早发生时间ve()
  • ②从汇点出发，令vl(汇点) = ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间vl()
  • ③根据各顶点的ve()值求所有弧的最早开始时间e()
  • ④根据各顶点的vl()值求所有弧的最迟开始时间l()
  • ⑤求AOE网中所有活动的差额d()，d() = 0的活动(边)构成关键路径

• 求关键路径例题

  
  
  一个DAG图
  • 求ve()和vl()

• 求e()和l()，得到d(i)

• 则a2，a5，a7所对应的边对应的顶点构成关键路径，这里是(v1，v3，v4，v6)
  
  求得关键路径
• 关键路径上所有活动都是关键活动，只有加快那些包含在所有关键路径上的关键活动才能达到缩短工期的目的，但也不可任意缩短关键活动，因为一旦缩短到一定程度，该关键活动可能会变成非关键活动