定义与术语特殊的图图的表示邻接矩阵邻接表邻接多重表图的遍历与连通性广度优先遍历BFS算法实现深度优先遍历DFS算法实现连通分量最小生成树定义克鲁斯卡尔Kruskal算法(加边法)Prim算法(加点法)最短路径定义单源最短路问题多源最短路问题迪杰斯特拉Dijkstra算法(逐个考察最近顶点)贝尔曼-福德Bellman-Ford算法(遍历所有边)弗洛伊德Floyed算法(逐个添加中间顶点/跳板)活动网络AOV网络（Activity-on-Vertex Network，点活动网）AOE网络（Activity-on-Edge Network，边活动网）拓扑排序(Topological Sort)
notion image

定义与术语

定义: 顶点的非空集合 + 边的集合
有向图 / 无向图
完全图
顶点的入度和出度
 
notion image
导出子图 → 选出部分点和所有相关边
生成子图 → 选出全部点和部分边
 
路径 → 从顶点 A 到顶点 B 经过的边构成的序列被称为从 A 到 B 的“路径”
简单路径 → 除了头尾没有重复节点
简单环路 → 头尾节点相同的简单通路
连通图 → 从任意顶点出发，可以到达其余任意顶点; 反之对于非连通图，从某个顶点出发，至少有一个顶点无法到达。
极大(强)连通子图 (强)连通分量, 即完整的各非连通子图
强连通 → 顶点两两可达(直接连接)
 
网络 → 加权连通图(有向/无向)
图的生成树: 极小连通子图, 对n个顶点的图有n-1条边(一线连?)

特殊的图

notion image
notion image

图的表示

邻接矩阵

A[i][j] == 1 → 存在从i到j的通路
无向图的邻接矩阵为对称矩阵
邻接矩阵中1的总数为图的度
行和为出度, 列和为入度
💡
算度容易, 算边数困难(只能枚举整个矩阵中1的个数, )
对于加权图, 用权重值代替1, 用Inf代替0
使用邻接矩阵表示图时，我们可以直接访问矩阵元素以获取边，因此增删查改操作的效率很高，时间复杂度均为 (最大优势) 。然而，矩阵的空间复杂度为  ，内存占用较多, 在稀疏图上效率很低, 空间无法承受. 故一般只会在稠密图上使用邻接矩阵.
邻接矩阵只适用于没有重边（或重边可以忽略）的情况。
除以上的邻接矩阵外，还需要一个记录各顶点信息的顶点列表vertices[]，和一个当前的边数
💡
邻接矩阵只起到存储拓扑关系的作用, 每个节点的具体信息需要另外存储.
又因为算边数困难, 所以最好在构建时就维护边数变量eNum.
notion image

邻接表

只存存在的边, 减少空间浪费
邻接表 / 逆邻接表(有向图)
每个节点作为表头, 引出链表 / 可扩展的数组(如vector)为与该节点相连的无向边 / 从该节点出发的有向边
邻接表仅存储实际存在的边，而边的总数通常远小于 ，因此它更加节省空间。然而，在邻接表中需要通过遍历链表来查找边，因此其时间效率不如邻接矩阵。
存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。尤其适用于需要对一个点的所有 出边 进行排序的场合。
notion image
notion image
邻接表结构与哈希表中的“链式地址”非常相似，因此我们也可以采用类似的方法来优化效率。比如当链表较长时，可以将链表转化为 AVL 树或红黑树，从而将时间效率从 优化至 ；还可以把链表转换为哈希表，从而将时间复杂度降至 。
综合来看，邻接矩阵体现了“以空间换时间”的原则，而邻接表体现了“以时间换空间”的原则。

邻接多重表

邻接多重表是一种用于表示图（graph）的存储结构，主要用于表示有向图和无向图。它是一种结合邻接表和边表的结构，可以高效地存储图中顶点和边之间的关系。
结构
邻接多重表是一种基于链表的表示方法，核心是为每条边设置一个节点，节点包含两个方向的邻接信息：
  1. 表头数组（顶点表）：
每个顶点作为一个表头，记录指向该顶点的边的链表信息。
  1. 边表节点：
每条边对应一个边表节点，包含如下内容：
  • 顶点信息：标识该边的两个顶点（通常用两个指针，分别指向边的起点和终点）。
  • 下一条边：在链表中，指向当前顶点关联的下一条边。
  • 边的信息（可选）：例如权值、标记等。
适用场景
  • 稀疏图：邻接多重表对存储稀疏图（边远少于顶点的完全连接数）非常高效。
  • 边的动态操作：支持动态添加和删除边。
  • 双向图：无向图的每条边只存储一次，两个方向的指针可以灵活表达双向关系。
邻接多重表与其他存储结构的对比
  • 邻接矩阵：适合稠密图，但对于稀疏图会浪费大量存储空间。
  • 邻接表：适合稀疏图，但在处理无向图时，需要额外存储两条边。
  • 邻接多重表：克服了邻接表存储无向图的冗余问题，用两个指针处理双向边信息。
优点
  • 结构灵活，支持图的动态操作。
  • 对稀疏图的空间利用率高。
缺点
  • 相比邻接表，结构稍微复杂，遍历和实现难度较大。

图的遍历与连通性

广度优先遍历BFS

广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。如图 9-9 所示，如首先遍历首个顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。

算法实现

BFS 通常借助队列来实现，代码如下所示。队列具有“先入先出”的性质，这与 BFS 的“由近及远”的思想异曲同工。
  1. 将遍历起始顶点 startVet 加入队列，并开启循环。
  1. 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
  1. 循环步骤 2，直到所有顶点被访问完毕后结束。
为了防止重复遍历顶点，我们需要借助一个哈希集合 visited 来记录哪些节点已被访问。
💡
哈希集合可以看作一个只存储key而不存储value的哈希表，它可以在时间复杂度下进行key的增删查改操作。根据key的唯一性，哈希集合通常用于数据去重等场景。
广度优先遍历的序列不唯一, 因为广度优先遍历只要求按“由近及远”的顺序遍历，而多个相同距离的顶点的遍历顺序允许被任意打乱。
💡
向下一层扩散时, 按照上一层扩散的顶点的顺序依次扩散
对有向图而言, 不是从任意顶点出发都能一次广度优先搜索搜完整个图
连通无向图可以一次搜完
非连通无向图需要从多个起点开始, 广搜次数就是连通分量的数量
💡
对于非连通无向图, 执行几次DFS或BFS, 图中就有几个连通分量
notion image

深度优先遍历DFS

notion image
深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。从首个顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。

算法实现

这种“走到尽头再返回”的算法范式通常基于递归来实现。与广度优先遍历类似，在深度优先遍历中，我们也需要借助一个哈希集合 visited 来记录已被访问的顶点，以避免重复访问顶点。
与广度优先遍历类似，深度优先遍历序列的顺序也不是唯一的。给定某顶点，先往哪个方向探索都可以，即邻接顶点的顺序可以任意打乱，都是深度优先遍历。
💡
注意: 对有向图而言, 并不是从任意一个节点出发都可以用一次深度优先遍历完成对整个有向图的遍历(回溯之后也不一定有其他路可走), 可能需要从多个未访问节点出发分别做深度优先遍历.
连通无向图可以一次遍历所有节点
非连通无向图则必然需要选取多个起点, 有几个连通分量就要执行几次深度优先搜索
以树的遍历为例，“根 → 左 → 右”“左 → 根 → 右”“左 → 右 → 根”分别对应前序、中序、后序遍历，它们展示了三种遍历优先级，然而这三者都属于深度优先遍历。

连通分量

以上讨论的是对一个无向的连通图或一个强连通图的有向图进行遍历，得到一棵深度优先或广度优先生成树.但当无向图(以无向图为例)为非连通图时，从图的某一 顶点出发进行遍历(深度，广度)只能访问到该顶点所在 的最大连通子图(即连通分量)的所有顶点. 故对非连通图需要选择多个遍历起点.
体现在代码中, 就是在遍历的入口处加一个循环, 从多个起点开始几趟遍历即可.

最小生成树

notion image

定义

  • 生成树（spanning tree）：一个 连通无向图 的生成子图，同时要求是树。也即在图的边集中选择条(为顶点数)，将所有顶点连通。
      • 💡
      针对连通无向图而设置
      只有连通图才有生成树，而对于非连通图，只存在生成森林。
      💡
      生成树不唯一
  • 定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。
💡
在无向图中求一棵树(n-1条边, 无环, 连通所有点), 而且这棵树的边权最小
用最小的成本去连通所有的节点(修路)
  • Grandy策略: 逐步求解, 贪心思想
      • notion image

克鲁斯卡尔Kruskal算法(加边法)

notion image
Kruskal算法是一种经典的图算法，用于解决最小生成树问题。它的目标是找到一个连通无向图的最小生成树，使得生成树的总权重最小。
💡
先给所有边按权重排序, 再从小到大加边
加边是需要判断边的两端点是否已经在同一个连通分量内, 如果在则不能加(否则有环)
对权重相同的边加入顺序不做限制, 故最小生成树可能不唯一
但是最小生成树的边权和一定是相同的
以边为核心, 与点数无关, 适用于顶点多边少的 稀疏图
Kruskal算法的基本思想：
Kruskal算法是一种贪心算法，它通过以下步骤来构造最小生成树：
  1. 初始化：
      • 创建一个空的最小生成树。
      • 将图中的所有边按权重从小到大排序。
  1. 遍历边：
      • 依次从权重最小的边开始，检查这条边是否会在生成树中形成环。
      • 如果不会形成环，则将这条边加入最小生成树；否则跳过。
  1. 终止条件：
      • 当生成树中的边数达到 （是图的顶点数）时，算法结束。
Kruskal算法的关键步骤：
  1. 边排序：
      • 使用排序算法对边按权重从小到大排序（时间复杂度为 ，是边的数量）。
          • 例如: 可以使用堆排序(小根堆)
  1. 环检测：
      • 使用并查集（Union-Find）数据结构快速检测环的存在，并实现集合合并（合并两个顶点所在的连通分量）。
Kruskal算法的时间复杂度：
  • 边排序的复杂度：。
  • 并查集操作的复杂度：接近 ，其中 是反Ackermann函数，几乎是常数时间。
  • 总复杂度：以上两者相加，通常简化为。
Kruskal算法的伪代码：

Prim算法(加点法)

Prim算法是一种经典的图算法，用于解决最小生成树（Minimum Spanning Tree, MST）问题。与Kruskal算法类似，Prim算法的目标是找到一个连通无向图的最小生成树，使得生成树的总权重最小。
Prim算法的基本思想：
Prim算法是一种贪心算法，从一个顶点开始，逐步扩展生成树，每次选择一条权重最小的、连接树内外顶点的边。
💡
每次加入离生成树部分(点亮部分)最近的节点
距离相同的点加入顺序不做限制, 故求出的最小生成树可能不唯一
但是最小生成树的边权和一定是相同的
以点为核心, 算法效率和边数无关, 更适用于边多顶点少的 稠密图
Prim算法的步骤：
  1. 初始化：
      • 从图中的任意一个顶点出发，将它加入生成树。
      • 维护一个集合，用于存储生成树中的顶点。
      • 使用一个优先队列或数组，记录每个顶点到生成树的最小边权重。
  1. 选择最小边：
      • 在连接生成树内外的所有边中，选择权重最小的边，将对应的顶点加入生成树。
  1. 更新权重：
      • 更新优先队列或数组中的值：检查新加入的顶点，并调整其邻接点的最小边权重。
  1. 重复以上步骤，直到所有顶点都被加入生成树。
Prim算法的关键点：
  • 每次选择权重最小的边可以通过优先队列或最小堆实现，从而优化性能。
  • 和Kruskal算法不同，Prim算法逐步扩展一个连通的子图，而不是通过边的排序构造生成树。
Prim算法的时间复杂度：
  • 若使用邻接矩阵表示图，则每次寻找最小边需要 ，总复杂度为
  • 若使用邻接表和最小堆，则时间复杂度为 ，其中 是边数， 是顶点数。
Prim算法的伪代码：
notion image

最短路径

notion image

定义

顾名思义, 设G=(V,E)是一个带权图（有向/无向），如果从顶点v到顶点w的一条路径为（v,v1 ,v2, …,w)，其路径长度不大于从v到w的所有其它路径的长度，则该路径为从v到w的最短路径。

单源最短路问题

定义：给定一个带权有向图或无向图，以及一个起始顶点 ，要求找到从 到图中所有其他顶点的最短路径。
常见算法：
  • Dijkstra 算法（权值非负）
  • Bellman-Ford 算法（允许权值为负）
  • SPFA 算法（优化的 Bellman-Ford）
例子：
  • 问题：一个城市的交通网络中，每条道路都有一个通行时间（权重），你现在在城市的某个位置（起始点 ），想知道到城市中每个其他地点的最短时间。
  • 解法：将城市的交通网络建模为一个图，使用单源最短路算法从起始点 计算到其他点的最短路径。

多源最短路问题

定义：给定一个带权有向图或无向图，要求找到图中所有顶点对之间的最短路径。
常见算法：
  • Floyd-Warshall 算法（动态规划方法，时间复杂度 ）
  • Johnson 算法（适合稀疏图，利用 Dijkstra 和 Bellman-Ford 的组合）
例子：
  • 问题：在一个配送网络中，每个仓库到其他仓库之间都有一个固定的运输成本（权重）。为了优化整体运输效率，你想知道从任意一个仓库到任意另一个仓库的最短运输成本。
  • 解法：将配送网络建模为一个图，使用多源最短路算法计算所有点对间的最短路径。
两者的主要区别
  1. 起点范围：
  • 单源最短路：从一个固定的起点 出发。
  • 多源最短路：计算所有点对之间的路径。
  1. 复杂性：
  • 单源最短路可以针对具体起点优化计算，只需一个起点的结果。
  • 多源最短路需要更全面的计算，适合全局性需求。
  1. 使用场景：
  • 单源最短路：如导航软件中从当前位置（起点）到所有目标地点的最短路径。
  • 多源最短路：如分析整个交通网络中任意两地的最短通行时间。
对所有点各自作为起点应用一次单源最短路算法，确实可以解决多源最短路问题，但在时间复杂度上可能不如专门针对多源最短路问题设计的算法（例如 Floyd-Warshall 算法或 Johnson 算法）高效，具体情况取决于图的稀疏性和规模。
具体实现
  1. 方法描述：
  • 遍历图中的每个顶点 。
  • 以 为源点，运行单源最短路算法（如 Dijkstra 或 Bellman-Ford），计算从 到所有其他点的最短路径。
  • 将所有结果记录下来，形成一个点对最短路径的矩阵。
  1. 时间复杂度：
  • 如果用 Dijkstra 算法（基于优先队列，复杂度为 ），对每个点应用一次，总时间复杂度为 。
  • 如果图是稠密的（即边数接近 ），上述复杂度可简化为 。
  • 对稀疏图（即边数接近 ），上述复杂度为 。
与专门算法的比较
  1. Floyd-Warshall 算法：
  • 基于动态规划，时间复杂度为 。
  • 适合稠密图，因为其复杂度与边数无关，仅取决于顶点数。
  1. Johnson 算法：
  • 通过重新赋权，将所有边权调整为非负，然后对每个顶点运行一次 Dijkstra 算法。
  • 总复杂度为 ，对稀疏图更高效。
优劣分析
  • 对所有点运行单源最短路的优势：实现简单，尤其是对小规模图，直接调用现有的单源最短路算法即可。
  • 专门算法的优势：更高效，特别是在处理稠密图或大规模图时。
因此，对所有点运行单源最短路算法是可行的，但并不是最优解，具体选择取决于问题规模和图的稀疏性。

迪杰斯特拉Dijkstra算法(逐个考察最近顶点)

💡
适用于: 没有负权边的单源最短路问题
Dijkstra算法是一种经典的图算法，用于求解单源最短路径问题。它的目标是在一个加权图中，找到从单一起始顶点（源点）到所有其他顶点的最短路径（总权重最小）。
Dijkstra算法的特点：
  1. 适用范围：
  • 图的边权重必须为非负数（负权边可能导致算法错误）。
  1. 基本思想：
  • 使用贪心策略，逐步扩展路径，确保每次找到的是当前最短的路径。
    • 贪心:当前新产生的一条最短路径能否使已有路径在一步以内 变短。
Dijkstra算法的步骤：
💡
每次选距离起点最近的点, 用它更新所有点到起点的距离, 用完该点之后归档该点
最终所有的归档节点就是起点到各点的最短路径长度
notion image
  1. 初始化：
  • 设置源点到自身的距离为，到其他所有顶点的距离为。
  • 创建一个优先队列（或最小堆）存储顶点及其当前最短距离。
  • 标记所有顶点为未访问。
  1. 松弛操作：
  • 从优先队列中取出当前离 起点 距离最小的顶点 (出队)。
  • 对 的所有邻接点 进行松弛操作：
其中， 是边 的权重。
  1. 标记顶点：
  • 将 u 标记为访问过，不再更新它的距离。
  1. 重复：
  • 重复步骤 2 和 3，直到优先队列为空，或所有顶点的最短距离都确定。
Dijkstra算法的伪代码：
notion image

贝尔曼-福德Bellman-Ford算法(遍历所有边)

💡
适用于: 任意权值的单源最短路问题
Bellman-Ford算法是一种经典的图算法，用于解决单源最短路径问题，即从一个源点到图中其他所有顶点的最短路径问题。与Dijkstra算法不同，Bellman-Ford算法能够处理带负权边的图（但不能处理负权环）。
Bellman-Ford算法的特点：
  1. 适用范围：
      • 可以用于带负权边的图。
      • 不能用于含有负权环的图，因为在负权环中路径长度可以无限减小。
  1. 基本思想：
      • 利用松弛操作反复更新顶点之间的最短路径信息。
      • 在最多 次迭代后（ 是顶点数），所有最短路径都会得到正确更新。
Bellman-Ford算法的步骤：
  1. 初始化：
      • 设置源点到自身的距离为 ，到其他所有顶点的距离为。
      • 初始化所有边的权重。
  1. 松弛操作：
💡
只要遍历所有边即可, 不需要讲究顺序, 不用维护优先队列
  • 对图中每条边（从到，权重为）执行松弛操作：
      • 💡
      对边 u → v , 比较 1 → v 与 1 → u → v 的长度, 取小者
      每一次更新只使用上一次迭代的结果, 即计算完全部更新结果之后再修改距离数组
      若 , 则
  • 重复此操作次（保证所有最短路径找到）。
      • 💡
      迭代次数是最短路径的最大边数的上界
  1. 检测负权环：
  • 如果不存在负权环, 则执行 次松弛操作后必然有 dist[v] <= dist[u] + w(u, v)
  • 在第 次迭代中，如果还能执行松弛操作，说明图中存在负权环(无限迭代下去则会变为负无穷)。
      • 💡
      n个点的子图中有一条最短路长度大于n → 必然存在环路
💡
最短路问题中一般不允许出现负权回路, 因为无限转下去会使得距离趋于负无穷, 不一定存在最短路径
notion image
Bellman-Ford算法的伪代码：
notion image

弗洛伊德Floyed算法(逐个添加中间顶点/跳板)

💡
依次将每个点作为任意两点之间路径的中间点, 更新最短路径及其长度
💡
适用于任意权值图的任意两个节点之间的最短路问题(任意权值, 单源/多源)
维护两个矩阵, 分别用于存储最短路径长度和最短路径本身(以记录前驱形式存储, 最终通过各个节点的前驱回溯到起点)
弗洛伊德算法（Floyd-Warshall算法）是一种经典的图算法，用于求解任意两点间的最短路径问题。它可以在一个加权图中找到所有顶点对之间的最短路径。
弗洛伊德算法的特点
  1. 适用范围：
  • 适用于有向图或无向图。
  • 可以处理负权边，但不能处理负权环（因为负权环会导致路径长度无限减小）。
  1. 基本思想：
  • 通过逐步加入中间顶点，检查是否可以通过这个顶点让两个顶点之间的路径变得更短。
  • 使用动态规划的方法，将问题分解为更小的子问题逐步求解。
弗洛伊德算法的步骤
  1. 初始化：
  • 如果顶点 i 和 j 之间有边，则初始化距离为边的权重，否则设置为无限大。
  • 自身到自身的距离初始化为 0。
  1. 动态规划：
  • 逐步尝试将每个顶点 k 作为路径的中间顶点。
  • 对于每一对顶点 (i, j)，检查是否可以通过顶点 k 缩短 i 到 j 的路径。如果可以，则更新最短路径的值：
      • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
  1. 输出结果：
  • 完成所有中间顶点的尝试后，dist[i][j] 就是顶点 i 到顶点 j 的最短路径。
弗洛伊德算法的伪代码
时间复杂度
  • 时间复杂度：，其中 是图的顶点数。三个嵌套循环分别遍历中间顶点、起点和终点。
  • 空间复杂度：，需要存储距离矩阵。
示例
假设图中有以下顶点和边：
  • 顶点：A, B, C, D
  • 边及权重：
    • A -> B (1)
    • A -> C (4)
    • B -> C (2)
    • C -> D (1)
    • B -> D (6)
初始化距离矩阵（无边用∞表示）：
A B C D
A 0 1 4 ∞
B ∞ 0 2 6
C ∞ ∞ 0 1
D ∞ ∞ ∞ 0
执行算法逐步更新距离矩阵，最终结果为：
A B C D
A 0 1 3 4
B ∞ 0 2 3
C ∞ ∞ 0 1
D ∞ ∞ ∞ 0

活动网络

活动网络、AOV网络和AOE网络是项目管理中常用于描述项目活动之间关系和调度的一些工具和模型。它们主要用于帮助组织和分析项目的时间表、资源分配和活动依赖关系。
活动网络是描述项目各个活动之间逻辑关系的图形模型。它展示了活动的先后顺序，并通过节点（表示活动）和箭头（表示活动之间的依赖关系）来表示。活动网络有助于识别项目的关键路径，即影响项目总工期的最重要的活动序列。

AOV网络（Activity-on-Vertex Network，点活动网）

AOV网络是一种图形表示方式，其中每个节点代表一个活动，而箭头表示活动之间的依赖关系（即一个活动必须在另一个活动之前完成）。AOV网络的特点是活动的表示方式在顶点（节点）上，这种方式对于明确活动之间的关系和排序非常有效。
 
  • 直接前驱，直接后继：是网中一条弧，则 是 的 直接前驱， 是 的直接后继。
  • 前驱，后继：从顶点 → 顶点 有一条有向路径，则称 是 的前驱， 是 的后继。
  • AOV网中，不应该出现有向环
 
AOV网使用邻接表实现, 使用数组count[]存放各顶点的入度, 并且为了避免每次从头到尾查找入度为0的顶点，建立入度为0的顶点栈，栈顶指针为top，初始化时为-1.
 
在AOV网络（Activity-on-Vertex Network）中，我们使用图的顶点表示活动，边表示活动之间的依赖关系。邻接表是一种常用的图的表示方法，它通过一个数组或者列表来存储每个节点（活动）与其他节点（依赖的活动）之间的关系。
下面是如何使用Java语言实现一个简单的AOV网络的邻接表表示：
Java实现AOV网络
  1. 定义图的结构：我们可以使用一个ArrayList数组，每个ArrayList代表一个节点的邻接表，存储该节点指向的所有邻居节点（即该活动的后继活动）。
  1. 添加活动及依赖关系：每个活动可以通过一个编号或标识符表示，活动之间的依赖关系通过边来表示。
代码示例
代码解析：
  1. AOVNetwork类：这个类表示一个AOV网络，其中adjacencyList是一个ArrayList<List<Integer>>，用于存储每个活动的后继活动。每个活动的邻接表是一个ArrayList<Integer>，存储它依赖的活动（即在其之后执行的活动）。
  1. addEdge方法：该方法用于在活动u和活动v之间添加一条依赖关系，表示活动u必须先完成，才能开始活动v。
  1. printDependencies方法：该方法遍历邻接表并打印每个活动的依赖关系。每个活动列出它的所有后继活动。
  1. Main类：在主函数中，创建一个包含5个活动的AOV网络，并定义各活动之间的依赖关系。最后，调用printDependencies方法输出活动的依赖关系。
输出结果：
总结：
  • 在这个示例中，我们用邻接表存储了AOV网络，其中每个活动及其依赖的活动存储在ArrayList中。
  • addEdge方法用于建立活动之间的依赖关系。
  • printDependencies方法输出每个活动的依赖情况。
这种实现方法是基于邻接表的简单图表示，能够有效地展示活动之间的依赖关系。

AOE网络（Activity-on-Edge Network，边活动网）

💡
针对有向无环图, 因为需要明确的先后顺序
边代表活动, 点代表两个活动之间的中间状态
起点为源, 终点为汇
AOE网络与AOV网络类似，但它的表示方式略有不同。在AOE网络中，每个活动不是通过节点表示，而是通过边（箭头）表示，边的起点和终点代表活动的开始和结束时间(顶点的入边代表活动完成, 出边代表活动完成, 边的权代表活动需要的时间)。AOE网络有助于分析活动之间的时间约束和依赖性，尤其是在需要考虑时间顺序和持续时间的情况下。
在 AOE网络（Activity-on-Edge Network） 中，关键路径（Critical Path）是指从项目开始到项目结束所经过的最长路径，这条路径上的活动决定了项目的最短工期。关键路径上的活动称为 关键活动，这些活动的延迟将直接导致项目的整体延期。
notion image
关键路径与关键活动的定义：
💡
关键活动和关键路径可能不唯一
  1. 关键路径：是指在AOE网络中，起点到终点所经过的最长路径。这个路径上所有活动的总持续时间最长，因此，任何一个活动的延迟都会导致项目的整体工期延长。
      2. 💡
      根据木桶原理, 在并行工作时, 最耗时的路径(最长路)决定整个工程的最终用时, 是为关键路径
      普通活动可以等, 关键活动不能等(必须严格首尾相接才能保证整体时间最短)
      关键活动的最早, 最晚开始(完成)时间相同, 浮动时间为0
      起点和终点必然在关键路径上, 浮动时间必然为0
      边的最晚开始时间实际上是由后一个点向前推出的
  1. 关键活动：是指位于关键路径上的活动。如果关键活动延迟，整个项目的完成时间将被延迟。换句话说，关键活动的持续时间对于项目完成时间至关重要。
如何找出关键活动
💡
先求点(VE和VL), 再用点求边(E和L)
 
求 从源向汇推, 使用拓扑排序(判断节点前面有哪些活动需要完成)
方法很像反过来的迪杰斯特拉?(求最长路)
用上一个节点的最早开始时间加上 最大的 路径长度
取的是拓扑排序作为起点(因为要考虑事件之间的依赖关系), 而不是路径最长的节点, 此处和迪杰斯特拉不同
 
求VL需要从汇向源反推, 使用逆拓扑排序(每次选取出度为0的点, 然后删掉该点及其所有入边)
用上一个节点的最晚开始时间减去 最小的 路径长度
逆拓扑序列一定对应一个反转的拓扑序列。
如果将拓扑序列中的顺序完全颠倒，那么就称之为逆拓扑序列。逆拓扑序列中，节点的排列依然满足原有图中所有边的约束，因为逆序操作不会违反边的方向。
 
再通过点的 和 推边的 和 (由谁发出来, 就等于谁的 ; 指向谁, 就等于谁的 )
 
求得所有 和 , 从而可以根据浮动时间识别出关键活动和关键路径
在AOE网络中，找出关键活动的一般方法是通过以下步骤：
  1. 计算每个活动的最早开始时间（ES）和最晚开始时间（LS）：
  • 最早开始时间（ES）：活动的最早开始时间，表示活动能开始的最早时刻，依赖于前置活动的完成时间。
  • 最晚开始时间（LS）：活动的最晚开始时间，表示活动必须开始的最晚时刻，以确保项目按时完成。
  1. 计算最早完成时间（EF）和最晚完成时间（LF）：
  • 最早完成时间（EF）：是活动完成的最早时间，等于最早开始时间（ES）加上活动的持续时间。
  • 最晚完成时间（LF）：是活动必须完成的最晚时间，等于最晚开始时间（LS）加上活动的持续时间。
  1. 计算浮动时间（Slack Time）：
  • 浮动时间是活动可以延迟的最大时间而不影响项目的整体工期。计算公式是：或
  • 如果浮动时间为，则该活动是 关键活动(起止时间严格确定)。
算法步骤：
  1. 正向扫描（从起点到终点）：
  • 计算每个活动的 最早开始时间（ES） 和 最早完成时间（EF）。
  1. 反向扫描（从终点到起点）：
  • 计算每个活动的 最晚开始时间（LS） 和 最晚完成时间（LF）。
  1. 计算浮动时间：对于每个活动，计算其浮动时间。如果浮动时间为0，则该活动是 关键活动。
💡
以上的计算必须在拓扑有序及逆拓扑有序的前提下进行
求ES[i]必须使 的所有前驱结点的ES都求得, 因为是视什么时候能开始而开始的
求LS[i]必须使 的所有后继结点的LS都求得, 因为是视ddl而开始的
示例算法（简化版）
假设有5个活动，并且每个活动的持续时间已知，同时活动间的依赖关系如下：
  • 活动A -> 活动B
  • 活动A -> 活动C
  • 活动B -> 活动D
  • 活动C -> 活动D
  • 活动D -> 活动E
假设活动的持续时间如下：
  • A: 4天
  • B: 3天
  • C: 2天
  • D: 5天
  • E: 1天
我们将使用Java代码来实现这个算法，找出关键路径并识别关键活动。
Java代码实现：
代码说明：
  1. AOENetwork类：表示AOE网络，包含邻接表、活动持续时间以及活动数量。
  1. 计算最早开始时间（ES）：通过深度优先搜索（DFS）计算每个活动的最早开始时间。
  1. 计算最晚开始时间（LS）：通过反向DFS计算最晚开始时间。
  1. 查找关键活动：对每个活动，检查其最早开始时间和最晚开始时间是否相等。如果相等，则该活动是关键活动。
输出示例：
Critical Activities:
Activity 0 is a critical activity.
Activity 1 is a critical activity.
Activity 3 is a critical activity.
Activity 4 is a critical activity.
总结：
  • 关键路径是从起点到终点的最长期限路径，路径上的活动为 关键活动。
  • 使用正向和反向扫描算法可以计算每个活动的最早开始时间和最晚开始时间，进而找出关键活动。
伪代码版本:

拓扑排序(Topological Sort)

💡
让有向无环图的所有顶点按照先后顺序排成序列
  • 若一个点的序列满足对一个有向图的每条边, 在序列中都出现在的前面, 则称该序列为图的拓扑序列(所有的边在拓扑序列中都是从前指向后), 因此不可以有无向边或环.
💡
拓扑序列可能不唯一, 因为有多个入度为0的点时选取顺序没有明确规定
  • 不是任何有向图的结点都可以排成拓扑序列，有环图是不能排的。无向图更是没有拓扑序列(反映的是偏序关系)
 
Loading...
JAY
JAY
Textbooks shouldn’t require a cryptologist to decode -- welcome to readable software engineering.
目录
0%