数据结构第六章-图

发表于 | 更新于: | 分类于 |
字数统计: 20k | 阅读时长 ≈ 1:14

数据结构第六章 图

计算机学科基础：数据结构第六章图的学习笔记

1.图的定义（✪）

  • 定义

    • 图G由顶点集V和边集E组成，记为G=(V,E)
    • 其中V(G)表示图G中顶点的有限非空集（称为图的阶）；E(G)表示图G中顶点之间的关系（边）集合。
    • 图不能是空图，顶点集不能为空，但是边集可以为空
    • 对于一个具有n个顶点和e条边的图，若采用边集数组表示，则边集数组中的单元数至少为2e个

  • 一些关于图的概念

    • 无向图：若E是无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)。
    • 有向图：若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是项点的有序对，记为，
      其中v,w是顶点，v称为弧尾，w称为弧头，称为从v到w的弧，也称v邻接到w。
    • 简单图、多重图：不存在重复边且不存在顶点到自身的边，则图G即为简单图，否则为多重图
    • 度
      • 对于无向图，顶点v的度是指依附于顶点v的边的条数，
        无向图的全部顶点的度的和等于边数的两倍（无向图所有顶点的度之和为偶数）
      • 对于有向图，顶点v的度分为入度和出度，有向图的全部顶点的入度之和与出度之和相等，并且等于边数。
      • 例题
        • 此时直接利用相关的关系，所有顶点的度数之和等于边数量的两倍（4*5+3*4+2(n-9)=23\2）选D
          • pCIG4Ln.png
    • 路径与回路
      • 路径：由顶点和相邻顶点序偶构成的边所形成的序列
        • 注意：由不同顶点所形成的序列不是路径的定义
      • 回路（环）：第一个顶点和最后一个顶点相同的路径称为回路或环
        • 有n个顶点和n条边的无向图一定是有环的
        • 如果有向图中存在拓扑排序，则其一定是无环的
      • 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
        • 最短路径一定是简单路径
      • 简单回路：除第一个项点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
      • 路径长度：路径上边的数目
      • 点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。
        若从u到v根本不存在路径，则记该距离为无穷(∞)。
    • 连通与强连通
      • 无向图中，若从项点v到项点w有路径存在，则称顶点v和顶点w之间是连通的
      • 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的（可以去和回）
    • 连通图与强连通图
      • 连通图：任意两个顶点之间都是连通的无向图，则称为连通图否则为非连通图。
        • 对于n个顶点的无向图G，若G是连通图，则最少有n-1条边
          • 注意理解：是G为连通图可以推导出该无向图至少有n-1条边
          • 此题选D
            • pCIJKFf.png
          • 此题选D，这时肯定构成了回路，但是不一定是连通图
            • pCI1Bq0.png
        • 若其为非连通图无向图，则最多可能有$\frac {n ( n - 1 ) } {2} $条边
          • 如果出现由n-1个完全无向图与另外一个单独顶点的极端情况，此时只需加1，
            则可以确保这n个顶点可以构成无向连通图
            • 本题即为（5*4）/2+1=11，选DpCIGGa6.png
      • 强连通图：任意一对顶点之间都是强连通的有向图。
        • 对于n个顶点的有向图G，若其为强连通图，则最少有n条边（形成回路）
    • 连通分量与强联通分量
      • 连通分量：无向图的极大连通子图（必须连通且尽可能包含更多的顶点和边）
        • pCIKLDK.png
      • 强连通分量：有向图的极大强连通子图（必须强连通且尽可能包含更多的边）
        • 注：若一个图存在环，则其一定含有顶点数大于1的强连通分量
        • pCIKOHO.png
    • 子图与生成子图
      • 设有两个图G=(V,E)和G1=(V1,E1),若V1是V的子集，且E1是E的子集，则称G1是G的子图。
        • 此时需要V1和E1先相互对应，即构成了图。如下面的描述错误pCI3ffg.png
      • 若有满足V(G)=V(G1)的子图G,则称其为G的生成子图。
        • pCIKRBT.png
    • 生成树与生成森林
      • 连通图的生成树是包含图中全部顶点的一个极小连通子图
        • pCIMCvt.png
      • 生成森林
        • 非连通图中，连通分量的生成树构成了非连通图的生成森林
          • pCIMFDf.png
      • 边的权、带权图（网）
        • 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
        • 带权图/网：边上带有权值的图称为带权图，也称网。
        • 带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
    • 几种特殊的图
      • 完全图
        • 无向完全图：无向图中任意两个顶点之间都存在边，共有条$\frac {n ( n - 1 ) } {2} $边
        • 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧，共有$n(n-1)$条边
        • 讨论拥有n个顶点的无向图需要多少条边才能确保形成一个连通图，
          此时常常考虑为由n-1个顶点之间形成的完全无向图与另外一个单独结点的组合时，再添加一条边，使这两部分相连。
        • 图片
          • pCI8Obt.png
      • 树：不存在回路，且连通的无向图，n个顶点的树，必有n-1条边。n个顶点的图，若边大于n-1,则一定有回路
      • 有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图

2.图的存储（✪）

  • 邻接矩阵法（二维数组实现的顺序存储方式✪）

    • 使用邻接矩阵存储，是指用一个一维数组存储图中项点的信息，
      用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。

    • 代码表示

      1
      2
      3
      4
      5
      6
      #define MaxVertexNum 100 	//顶点数目的最大值
      typedef struct{
          char Vex[MaxVertexNum]; 	//顶点表
          int Edge[MaxVertexNum][MaxVertexNum]; 	//临接矩阵，存放边的关系
          int vexnum,arcnum; 		//图的当前顶点数和边数、弧数
      }MGraph;

    • 邻接矩阵存储有向图与无向图

      • 值为1时边之间有关系，为0时无关系
      • 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。（只需存储上下三角矩阵的元素）
      • 对于无向图，邻接矩阵的第i行(或第i列)非零元素的个数正好是顶点的度数
      • 对于有向图，邻接矩阵的第i行非零元素的个数正好是顶点i的出度，第i列非零元素的个数正好是顶点i的入度
      • 邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(n)
      • 图片
        • pCI0HFs.png

    • 邻接矩阵存储带权图

      • ∞元素和0元素表示两边之间不邻接，非零数表示相应的权值
      • pCIB1pt.png

    • 邻接矩阵的相关性质

      • 邻接矩阵表示法的空间复杂度为O($n^{2}$),其中n为图的顶点数。
      • 稠密图适合使用邻接矩阵的存储表示。
      • 邻接矩阵关于利用矩阵乘法计算路径条数的的重要性质
        • 矩阵的平方相当于求路径长度为2的路径条数：此时从B到B路径长度为2的路径条数为3
          • pCIBakj.png
        • 矩阵的立方相当于求路径长度为3的路径条数，此时从B到C路径长度为3的路径条数为4
          • pCIBD10.png

  • 邻接表法（顺序+链式存储✪）

    • 对图G中的每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点$v_{i}$的边(对于有向图则是以顶点为尾的弧)，
      这个单链表就称为顶点$v_{i}$的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）
    • 顶点表结点由顶点域(data)和指向第一条邻接边的指针(firstarc)构成，
      边表（邻接表）结点由邻接点域(adivex)和指向下一条邻接边的指针域(nextarc)构成。
    • 图片
      • 存储无向图
        • pCI2btS.png
      • 存储有向图
        • pCIRrcj.png
    • 特点
      • 若G为无向图，则所需的存储空间为O(V+2E)，若G为有向图，则所需的存储空间为O(V+E)。
        前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。（n个顶点的无向图的邻接表最多含有n(n-1)个边表顶点）
      • 对于稀疏图，采用邻接表表示将极大地节省存储空间。
      • 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。
        • 在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)
        • 如果要确定两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
      • 在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数，
        但求其顶点的入度则需要遍历全部的邻接表（在有向图的邻接表中，顶点v在边表的出现次数等于顶点v的入度）
      • 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，
        它取决于建立邻接表的算法及边的输入次序。
    • 邻接表与邻接矩阵的对比
      • pCIRw4S.png

  • 十字链表（只能用于存储有向图）

    • 空间复杂度为O(V+E)，此时要找顶点的出边顺着绿色路线，要找入边顺序橙色路线。
    • pCoFIu4.png

  • 邻接多重表（只能用于存储无向图）

    • 空间复杂度为O(V+E)，删除边和顶点很方便
    • pCoAAoR.png

3.图的遍历（选择题考点，代码了解即可✪）

  • 定义：图的遍历是从图的某一顶点出发，按照某种搜索方法沿着图中的边对图的所有顶点访问一次且仅访问一次。

  • 广度优先搜索（BFS）

    • 特点
      • 与二叉树的层序遍历完全一致，都是利用队列进行遍历操作，出队时将其相邻元素入队
        （使用数组标记已经入队的顶点不用在入队）
      • 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一
      • 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一
      • 空间复杂度最坏情况下为：O(V)
    • 要点
      • 找到与一个顶点相邻的所有顶点
      • 标记哪些顶点被访问过（visited数组）
      • 需要一个辅助队列，用队列来暂存刚访问过的结点
    • 代码实现
      • pCoeoDO.png
      • pCoef81.png
    • 时间复杂度分析
      • 采用邻接表时
        • 访问 |V| 个顶点需要O(|V|)的时间
        • 查找各个顶点的邻接点共需要O(|E|)的时间, 时间复杂度${=O(|V|+|E|)}$
      • 采用邻接矩阵时
        • 访问${|\mathbf{V}|}$个顶点需要${O(|\mathbf{V}|)}$的时间
        • 查找每个顶点的邻接点都需要${O(|V|)}$的时间, 而总共有${|\mathbf{V}|}$个顶点的时间复杂度${=O\left(|V|^{2}\right)}$
    • 广度优先生成树
      • 同一个图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，
        但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。
      • pConPOK.png
  • 深度优先搜索（DFS）
    • 特点：与树的先序遍历类似，采用根左右的顺序，需要借助于栈，最坏的空间复杂度为O(V)
    • 要点：此时不需要队列，但是需要借助于函数调用栈以及标记哪些顶点被访问过的visited数组
    • 代码实现
      • pColTSJ.png
    • 时间复杂度分析
      • 采用邻接矩阵：查找每个顶点的邻接点所需的时间为${O(| V|)}$，故总的时间复杂度为${O\left(| V^{2}\right)}$。
      • 采用邻接表：查找所有顶点的邻接点所需的时间为${O(|E|)}$, 访问顶点所需的时间为${O(|V|)}$,
        此时, 总的时间复杂度为${O(|V|+|E|)}$。
    • 利用邻接表找出深度优先遍历的顺序
      • 此时的具体方法是，首先找到开始的顶点的那条链，遍历一个之前没有遍历到的元素时，从此元素的链继续开始遍历，
        如果此链遍历完成，那么退回上一个链继续进行上述有关操作。
        • pCo1MXn.png
    • 深度优先生成树
      • 同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一
      • 同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一
  • 图的遍历与图的连通性
    • 对于无向图遍历调用BFS/DFS函数的次数
      • 若其为连通的，只需要一次遍历即可
      • 若其为非连通的，此时的遍历次数为其连通分量的数量。
    • 对于有向图遍历调用BFS/DFS函数的次数
      • 此时情况不确定，若起始顶点到其他各顶点都有路径，则只需调用次1BFS/DFS函数
      • 对于强连通图，从任一结点出发都只需调用1次BFS/DFS

4.图的应用（✪）

  • 求最小生成树问题（✪）

    • 最小生成树的概念
      • 对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。
        若T为R中边的权值之和最小的那棵生成树，则T称为G的最小生成树(Minimum-Spanning-Tree,MST)。
      • 最小生成树可能不是唯一的，树形可能不唯一（因为图中可能存在权值相等的边）
        • 只要无向连通图中没有权值相同的边，则其最小生成树唯一，此说法正确
        • 只要无向连通图中有权值相同的边，则其最小生成树一定不唯一，此说法错误
          （此时若无向图本身就是一颗树，则最小生成树就是其本身，此时唯一）
      • 最小生成树的边的权值之和总是唯一的（代价唯一且最小）
      • 最小生成树的边数为顶点数量减一
      • 最小生成树的算法基于贪心算法的策略
    • Prim算法
      • 概述：从某一个顶点开始构建生成树，之后选择一个与当前树中的集合距离最近的顶点纳入生成树，
        直到所有顶点都纳入为止。
      • 此时若顶点数量为n，则此时生成的最小生成树的边数为n-1
      • 图片
        • pCo6e4e.png
      • 普里姆算法的特点
        • 时间复杂度：O($V^{2}$)，只与顶点有关，不依赖于边
        • 适合求解边稠密图的最小生成树
    • kruskal算法
      • 概述：按边来构建最小生成树，每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）
        直到所有结点都连通
      • 图片：如此图中，第二次选择的边为权值最小的边，权值为2
        • pCo6dvn.png
      • 克鲁斯卡尔算法的特点
        • 时间复杂度：O($|E|log_{2}E$)，只与边的数量有关，与顶点的数量无关
        • 适合求边稀疏图而顶点多的图的最小生成树

  • 求最短路径问题（✪）

    • 最短路径的定义

      • 从一个顶点到图中其余任意一个顶点的一条路径（可能不止一条）所经过边上的权值之和，
        定义为该路径的（带权）路径长度，（带权）路径长度最短的称为最短路径
      • 最短路径一定是简单路径

    • 求单源最短路径（分为有权图和无权图的求法）

      • BFS(广度优先)算法求无权图的单源最短路径问题（无权图相当于每一条边的权值都为1）

        • 概述：就是对广度优先搜索的小修改，在visit访问一个顶点时，修改其最短路径长度d【】并在path【】记录前驱结点

        • 代码实现

          • 由顶点2开始时，2到8的最短路径长度=d[8]=3，通过path数组可知，2到8的最短路径为：8<一7<一6<一2
          • pCogyp4.png

      • Dijkstra算法求有权图单源最短路径问题

        • 概述
          • 首先需要设置三个数组（与起始顶点相邻的点的最短路径长度修改为边上的权值，并修改路径前驱为起始点，
            其余的都设置为最短路径长度为无穷（起始点自身的最短路径长度设置为0），路径前驱为-1）
            • pCoRPPO.png
          • 第一轮：循环遍历所有顶点，优先选择还没有确定最短路径长度并且此时的最短路径长度最小的点进行修改，
            此时此点为V4，将final值设置为true。并且再进行对其它相邻点的遍历，
            此时V1需要变动（最短路径长度修改为8，路径前驱修改为4，但是这个时候还不能修改其标志位）
            • pCoRwJU.png
          • 第二轮，在V4遍历完成以后，此时应该开始优先遍历第二个最短路径长度最小的顶点V3，
            V3修改其标志位，在V3处可以将V2的最短路径的值修改为13，此时前驱变为V3。
            • pCoRfJO.png
          • 第三轮，在V3遍历完成之后，选择V1进行遍历，此时修改其标志位，
            并且此时可以修改V2的最短路径长度为9，并将其前驱改变为V3.
            • pCoRqTP.png
          • 求最短路径的长度时，即为dist数组中的值，求最短路径经过的顶点序列时，根据path数组的值往前推出
            • pCTbyAe.png
        • 特点
          • 时间复杂度为O(|$V^{2}$|)
          • 不适用于边上带有负权值的图

    • Floyd算法求各顶点之间最短路径问题

      • 概述：使用的是动态规划的思想，通过设置中转点依次来求解，
        此时需要两个矩阵（一个表示最短路径，另一个表示中转点）
      • 特点
        • 时间复杂度为O($V^{3}$)
        • 可以用于计算负权值带权图的计算，但是不适用于带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径
      • 最短路径的表中首先把存在直接联系的的路径长度写上，之后将中转点矩阵中的值均设为-1
        • pCo4AtP.png
      • 之后规定可以将V0作为中转点，按照表格依次进行遍历，需要满足两个顶点之间经过此中转点之后的路径长度小于原来的长度。此时v2到v1的路径可以修改为11，并且中转矩阵所对应的相关值修改为中转点0
        • pCo43t0.png
      • 遍历完成后，之后规定可以将V1,V0作为中转点，此时可以修改v0到v2的相关值
        • pCo4w7R.png
      • 最后将v0、v1、v2均设置为中转点，此时可以将v1到v0的相关值进行修改
        • pCo4Dtx.png
      • 代码实现
        • pCo4T9f.png

    • 三种求最短路径的算法之间的差异

      • pCo593T.png

  • 求有向无环图描述表达式问题（DAG图，了解）

    • 有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图(Directed Acyclic Graph)

    • 有向无环图可以描述含有公共子式的表达式。并可将重复出现的子表达式共享，节省存储空间

    • 解题思路

      • 首先根据规则先画好基本的有向无环图
        • pCTGNzF.png
      • 之后逐层的合体相同的运算符（该层的运算符的两个指向边都分别对应到相同的元素就合并）
        • pCTGWsH.png

  • 求拓扑排序问题（主要是会手算✪）

    • AOV网 （一种有向无环图）
      • 顶点表示活动的网络的有向图，有向边${}$表示活动${V_{i}}$必须先于活动${V_{j}}$进行
    • 拓扑排序：找到做事的先后顺序（同时可以判断图中是否存在回路）
      • 拓扑排序的特点（当且仅当满足以下的条件时）
        • 每个顶点出现且只出现一次
        • 若顶点A在序列中排在顶点B的前面，则在图中不存在从J顶点B到顶点A的路径。
      • 拓扑排序的流程
        • 从AOV网中选择一个没有前驱(入度为0)的顶点并输出。
        • 从网中删除该顶点和所有以它为起点的有向边。
        • 重复之前的操作直到当前的AOV网为空或当前网中不存在无前驱的顶点（说明此时存在回路）为止。
      • 拓扑排序算法代码实现（DFS(深度优先遍历)也可以得出相应的拓扑排序序列，了解）
        • 建立两个数组，分别表示当前顶点的入度情况以及记录生成拓扑的序列，
          且用一个栈保存度为0的待处理顶点，也可以用队列
          首先填写入度表中的各顶点的值，并将有向无序图中入度为0的点依次入栈，该图中有两个顶点0、2可依次入栈
          • pCTYbrQ.png
        • 之后首先弹出栈顶的顶点2，将拓补序列的第一号位修改为2并移动计数指针（序列的第一号即为2）
          ，此时将2的后继结点“3、4”的入度减一，由于此时3、4的入度还不为0，因此暂时不能入栈）
          • pCTtZPx.png
        • 按照上述过程，此时再将栈顶的顶点0弹出，此时顶点1的入度减一，作为入度为0的顶点入栈，
          之后依次类推，最后的拓扑顺序为：2、0、1、3、4
        • 进行如果最后的计数指针的数量等于顶点数，此时就得到了相应的拓扑排序序列，
          否则说明有向无序图中存在环路，无法进行排序，不是AOV网
      • 时间复杂度：采用邻接表时为${O(|V|+|E|)}$，若采用邻接矩阵, 则需${O\left(|V|^{2}\right)}$
    • 逆拓扑排序则是以没有出度的顶点开始排序，此时可以使用DFS(深度优先遍历)的算法进行操作得出逆拓扑排序序列，
      此时在顶点退栈前输出序列
    • 拓扑排序算法的相关注意事项
      • 入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
      • 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一（但是也不是绝对的，如下面的例题中有经典的反例）
      • 若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的
        • 判断：若有向无环图的拓扑序列唯一，则可以唯一确定此图（X），可举出下面的反例
          • pCTLOmV.png
      • 由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，
        生成AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵
      • 但对于一般的图来说，若其邻接矩阵是三角矩阵（不存在环），则存在拓扑序列，反之则不一定成立。
        • 反之成立的条件是此有向图的拓扑排序序列是有序的
    • 例题
      • 例题1：本题选D，此时可以举出一个经典的反例如下图
        • pCTL3i4.png
          • pCTLsWd.png
      • 例题2：此题选D，此时不能排成一个拓扑序列说明该图中存在环，AC选项用一个三角形环就可以排除；
        对于B选项，连通图是指需要任意两个端点之间可以互相到达的图，如果此时用一个三角形环外加从外面指向一个单独顶点的线，
        此时该单独顶点无法到达其它顶点，故不是强连通图。只有D满足相关的情况
        • 若一个有向图的顶点不能排成一个拓扑序列（即存在环路），则可以判定该有向图含有顶点数大于1的强连通分量。
          这是因为环路中的顶点构成了至少一个强连通分量，并且强连通分量中的顶点数大于1。
        • pCTO4nx.png
      • 例题3，找到拓扑排序的所有序列，用逐次列举的方法来找，不用去考虑机算方法，可以通过画圈辅助判断
        • pCTvBnI.png

  • 求关键路径问题（✪）

    • AOE网概念（一种有向无环图）
      • 在带权有向图中, 以顶点表示事件, 以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），
        称之为用边表示活动的网络,简称AOE网 (Activity On Edge NetWork)
      • 图片
        • pCTUdEj.png
    • AOE网的两个性质
      • 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
      • 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
        另外，有些活动是可以并行进行的
    • 源点与汇点
      • 在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；
      • 也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
    • 关键路径与关键活动（求关键路径是以拓扑排序为基础的）
      • 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径
      • 关键路径上的活动称为关键活动，它是决定整个工程的关键因素
      • 完成整个工程的最短时间就是关键路径的长度（关键路径上各活动花费开销的总和），
        若关键活动不能按时完成，则整个工程的完成时间就会延长（在关键路径上的活动的时间延长多少，整个工程的时间也就随之延长多少）
      • 可以通过加快关键活动（减少关键活动的时间）来缩短整个工程的工期。
        但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
      • 网络图的关键路径并不唯一，且对于有几条关键路径的网，
        缩短关键路径上任意一个或多个只包括在一条关键路径的关键活动的持续时间并不能缩短关键路径的长度，
        需要缩短那些包括在所有关键路径上的关键活动的持续时间才能缩短关键路径的长度。
        • 关于缩短关键路径长度的例题
          • 例题1，本题选择C，对于关键路径长度来说，增加是可以增大关键路径长度的，
            但是缩短需要在一定的条件下才能缩短关键路径长度
            • pCTomM8.png
          • 例题2，本题选择C，该题的关键路径经过计算得出为：b,d,c,g；b,d,e,h；b,f,h。
            此时只有C选项的f与d可以同时作用到三条关键路径上，其它的选项只能作用到其中的一条或两条。
            • pCTonsS.png
    • 求关键路径与关键活动以及相关的参数（求关键路径同时也可以判断图中是否存在回路）
      • 注意区别事件(顶点)的最早/最迟开始时间与活动(弧)的最早/最迟开始时间。
        • 时间余量=下一个顶点的最迟开始时间-活动持续时间—起始顶点的最早开始时间
        • 顶点（事件）的最迟开始时间等于=起始顶点的最早开始时间+时间余量
        • 弧（活动）的最早开始时间等于：弧的起始顶点的最早开始时间
        • 弧（活动）的最迟开始时间等于：下一个顶点的最迟发生时间—该活动的持续时间
      • pCTHwdg.jpg
-------------本文结束-------------