数据结构——6.4 图的应用

6.4 图的应用

• 概念

1. 最小生成树

   2. 对于一个带权连通无向图G =( E)，生成树不同，每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树 (Minimum-Spannimg-Tree.MST)

      1. 最小生成树可能有多个，但边的权值之和总是唯一且最小的

      2. 最小生成树的边数 = 顶点数 - 1。砍掉一条则不连通，增加一条边则会出现回路

      3. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身

      4. 只有连通图才有生成树，非连通图只有生成森林

   3. Prim 算法(普里姆)：同一个图可能有多个最小生成树

      1. 从某一个顶点开始构建生成树;

      2. 每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

      3. 总结：循环：点—该点最短边—点

   4. Kruskal 算法(克鲁斯卡尔)

      1. 每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)

      2. 直到所有结点都连通

      3. 总结：循环：全局最短边构成一片片岛屿—最后岛屿相连成大陆

   5. 两个算法的比较

克鲁斯卡尔算法和普林姆算法都是用于求解加权连通图的最小生成树的经典算法，但它们在实现方式和特点上有所不同。

克鲁斯卡尔算法的基本思想是按照权值从小到大的顺序选择n-1条边，并保证这些边不构成回路。它首先构造一个只含n个顶点的森林，然后根据权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。克鲁斯卡尔算法的时间复杂度为O(eloge)，其中e为网中的边数，因此它适合于求边稀疏的网的最小生成树。

普林姆算法则是从一个起始节点开始，不断选择与当前集合相连且权值最小的边，并将其加入到集合中。在这个过程中，不断扩大当前集合的规模，直到所有的节点都被加入到集合中为止。普林姆算法的时间复杂度与图中顶点的数量有关，因此它在某些情况下可能比克鲁斯卡尔算法更高效。

总的来说，克鲁斯卡尔算法和普林姆算法都是有效的求解最小生成树的算法，它们各有特点，可以根据具体问题的特点选择适合的算法。对于边数较少的稀疏图，克鲁斯卡尔算法可能更为合适；而对于顶点数较少的图，普林姆算法可能更具优势。在实际应用中，可以根据具体情况选择适合的算法进行求解。

2. 最短路径问题

   2. BFS求无权图的单源最短路径（无权图）

      1. 即构建以出发顶点为根的广度优先生成树

      2. 结点的高度即为最短路径长度

      3. 原理：广度优先生成树的高度是最低的

      4. 缺点：只适用于各边权值相等的图或无权图，即求的是最短的边数

   3. Dijkstra算法：求带权图的单源最短路径（带权图、无权图）

      1. 标记起点为完成路径寻找，起点到起点的距离为0

      2. 列出其他所有点到当前标记点的距离，不直接相连的顶点距离设置为∞

      3. 将距离加在目标点到起点的距离上，若小于原来的路径数据，则更新成最小值

      4. 移到未被标记且距离值最小的点上，重复②③，直到完成。

      6. 与Prim算法的对比

         1. Prim算法每次寻找最短边，不做加法

         2. Dijkstra算法寻找短边要更新最短路径

         3. 二者执行过程相似，复杂度都是O(n²)，即O(v²)

      7. 带负权值边的图中Dijkstra算法没有用

   4. Floyd算法求各顶点间最短路径（带权图、无权图）

      1. 列出图的临界矩阵

      2. 考虑一个顶点作为中转点的情况，将邻接矩阵的边更新为最小边，更新边在path矩阵的相应位置填入中转点

      3. 更新后的矩阵继续进行②，直到所有顶点都考虑过，算法完成

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

   1. 有向无环图简化描述算式

   3. (https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=media%2Fimage49.png&pos_id=img-TCL4uiTJ-1707574201371)

4. AOV网

   2. AOV网中不允许存在环路（本质是DAG图）

   3. 拓扑排序

      1. 实现

         1. 从AOV网中选择一个没有前驱 (入度为0) 的顶点并输出

         2. 从网中删除该顶点和所有以它为起点的有向边。

         3. 重复1) 和2) 直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（说明有回路）。

      2. 定义

         1. 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

            1. 每个顶点出现且只出现一次。

            2. 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

         2. 或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。

         3. 每个AOV网都有一个或多个拓扑排序序列

      3. 时间复杂度

         1. 时间复杂度:O(V+E)

         2. 若采用邻接矩阵，则需O(V²)

      4. 逆拓扑排序

         1. 从AOV网中选择一个没有后继 (出度为0) 的顶点并输出

         2. 从网中删除该顶点和所有以它为终点的有向边。

         3. 重复1) 和2) 直到当前的AOV网为空

      5. 逆邻接表：

         1. 正常的邻接表，边表是顶点指向的点，

         2. 逆邻接表，边表是指向顶点的点

      6. DFS算法实现逆拓扑排序

5. 关键路径

   1. AOE网的概念与性质

      1. 概念：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)

      2. AOE网具有以下两个性质

         1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;

         2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

         3. 另外，有些活动是可以并行进行的

   2. AOE网的关键路径

      1. 在AOE网中

         1. 仅有一个入度为0的顶点，称为开始顶点 (源点)，它表示整个工程的开始;

         2. 也仅有一个出度为0的顶点，称为结束顶点 (汇点)，它表示整个工程的结束

      2. 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动

      3. 完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长

   3. 求AOE网关键路径（事件：顶点，活动：边）

      1. 两个最早：（从前往后推）

         1. 事件v_(k)的最早发生时间ve(k)——决定了所有从v_(k)开始的活动能够开工的最早时间

         2. 活动a_(i)的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间

      2. 两个最迟：（从后往前推）

         1. 事件v_(k)的最迟发生时间vl(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间

         2. 活动a_(i)的最迟开始时间1(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差

      3. 活动a_(i)的时间余量：d(i)=1(i)-e(i)——表示在不增加完成整个工程所需总时间的情况下，活动a_(i)可以拖延的时间

      4. 若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即1(i)=e(i)的活动a_(i)是关键活动

      5. 由关键活动组成的路径就是关键路径

      6. 求关键路径的方法

      7. 关键活动、关键路径的特性

         1. 若关键活动耗时增加，则整个工程的工期将增长

         2. 缩短关键活动的时间，可以缩短整个工程的工期

         3. 当缩短到一定程度时，关键活动可能会变成非关键活动

         4. 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

• 理解

1. 最短路径一定是简单路径

2. 最小生成树的算法基于贪心策略，每次都选取权值最小且满足条件的边，如果各边权值不同，则每次选择的新顶点也是唯一的，因此最小生成树也唯一

3. 求关键路径过程的描述

   1. 事件最早发生时间Ve：起点为0，其他点取各入度路径长度中最大的（上一个指向该点的点的最早时间加上边的长度的最大值）

   2. 事件最晚发生时间Vl：终点为其最早发生时间，其他为各出度路径长度中最小的（上一个由该点指向点的最晚时间减去边长度的最小值）

   3. 活动最早发生时间e：边的最早发生时间，即为该有向边起点（无箭头一端）的最早发生时间

   4. 活动最晚发生时间l：边的最晚发生时间，即为该有向边终点（有箭头一端）的最晚发生时间减去该边的权值

• 技巧

1. 无向连通图存在权值相同的多条边时，最小生成树可能不是唯一的

2. 无向连通图的最小生成树一定存在

3. Dijkstra算法适合求解有回路的带权图的最短路径，也可以求两个顶点的最短路径

4. Floyd算法求两个顶点的最短路径时，当最短路径发生改变，path_(k)会在path_(k-1)的基础上更新，因此二者会失去子集关系

5. 能判断有向图是否有环的方法

   1. 深度优先遍历：生成树上：下一个结点是当前结点的父节点

   2. 拓扑排序：存在入度消不掉的点

6. 若有向图的拓扑有序序列唯一，每个顶点的入度和出度不一定为1，例如下图：

7. 拓扑排序中每一次操作都溢出当前入度为0的结点，如果一次移除若干个结点，这些结点的先后顺序不影响正确性，因此如果需要暂存，使用栈或队列都可以

8. 顶点数大于1的强连通分量=环

9. 若一个有向图具有有序的拓扑排序序列（0，1，2，3，…）则邻接矩阵一定上三角

10. 有向图的邻接矩阵中，主对角线以下元素均为0，则该图的拓扑序列，存在且不唯一，例如：三点两边有向图：①→②，①→③，有两个拓扑序列

11. 强连通分量数目的计算：

    1. 当一个顶点没有入度时表明没有别的点能够到达它，因此该点组成一个强连通分量

    2. 环构成一个强连通分量

12. Dijkstra算法高度相似Prim算法，但是Dijkstra算法在求生成树时，未必能求到最小生成树