数据结构-图(二)

每日一言

Magic is anything you can think of. It can be felt in infinite ways… As light, as darkness, as red, as blue. It is living freely, together along side Fairy Tail. – Makarov Dreyar
from Fairy Tail

基础概念

  1. 子图：设有两个图 $G = (V, E), G1 = (V1, E1)$，若 $V1 \subseteq V, E1 \subseteq E$, 则称 $G1$ 是 $G$ 的子图。
  2. 生成子图：由图的全部顶点和部分边组成的子图称为原图的生成子图。
  3. 极小连通图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通
  4. 生成树：包含无向图G所有顶线的极小连通子图
  5. 生成森林：对非连通图，由各个连通分量的生成树的集合

求最小生成树

最小生成树（Minimum Spanning Tree, MST）是一个连通无向图的一个子图，它包含了图中的所有顶点，并且使用的边数最少，且边权和最小。

构造最小生成树的准则

  • 必须只使用该网中的边来构造最小生成树
  • 必须使用且仅用$n-1$条边来联结网络中的n个顶点
  • 不能使用产生回路的边

MST性质

最小边性质（核心思想）

设N=(V,{E})是一个连通的网络，U是V的真子集，若边$(u,v) [u\subseteq U, v \subseteq V-U]$ 是E中所有一个端点在U内，一个端点不在U内的边权值最小的一条边，则一定存在G的一颗生成树包括此边。

关键点：

  1. 顶点集合划分 ：
  • 将图的所有顶点划分为两个不相交的部分：集合 S 和补集 V-S，其中 SSS 是某个子树的顶点集合，V-S 是剩余顶点的集合。
  • 在集合 S 和 V-S 之间的所有边中，找到权值最小的一条边。
  1. 最优性 ：
  • 权值最小的这条边一定是连接 S 和 V-S 的最优选择，加入它不会增加生成树的总权值。
  • 这种性质可以反复应用于生成树的构造过程，确保最小生成树的权值和最小。

Prim（普里姆） 算法

Prim 算法是用于求解最小生成树（MST）的经典贪心算法。它的核心思想是逐步扩展一个初始顶点集合，每次将当前连通部分的邻接边中权值最小的一条边加入生成树，直到覆盖所有顶点。

归并顶点，与边数无关，适合稠密网。

算法核心思想

  1. 从一个顶点开始 ：将其加入生成树（初始生成树为空）。
  2. 贪心选择边 ：从当前生成树的顶点集合出发，选择权值最小且不构成环的一条边。
  3. 重复步骤 2 ：逐步扩展生成树，直到所有顶点都被覆盖。

时间复杂度$O(n^2)$

Kruskal（克鲁斯卡尔）算法

Kruskal 算法是另一种经典的最小生成树（MST）求解算法，适用于连通无向图。它通过对边进行排序并逐步构造生成树，确保每次加入的边不会形成环，从而实现权值最小。

从边入手，适合稀疏图。

算法核心思想

  1. 排序边权值 ：将图中所有边按照权值从小到大排序。
  2. 贪心策略 ：从最小权值的边开始，依次判断是否可以将该边加入到生成树中。
  3. 无环性检查 ：使用并查集（Disjoint Set Union，DSU）快速判断当前边的两个顶点是否已经连通，避免形成环。
  4. 终止条件 ：当生成树的边数达到 ∣V∣−1 时（其中 ∣V∣ 是顶点数），算法结束。

时间复杂度$O(e \log e)$

破圈法

  1. 在图中找到一个回路；
  2. 去掉该回路中权值最大的边；
  3. 反复此过程，直到图中不存在回路为止。

去边法

  1. 将图中所有边按权值从大到小排序；
  2. 去掉权值最大的边，若图不再连通则保留此边，再选取下一权值较大的边去掉；
  3. 反复此过程，直到图中只剩下n-1条边

有向无环图及其应用

拓扑排序

拓扑排序（Topological Sorting）是一种对有向无环图（DAG, Directed Acyclic Graph）进行排序的方法，目的是将图中的所有顶点按照依赖关系排序，使得每个顶点出现在它所有依赖的顶点之前。

简而言之：按照有向图给出的次序关系，将图中顶点排成一个线性序列。

基本要求

  1. 图必须是有向无环图
  2. 排序的结果是一个顶点序列，其中每个顶点在序列中都位列于它所依赖的顶点之前

示例

1734695915151

拓扑排序：

1
ABCD 或 ACBD

无前驱的顶点优先算法

算法原理

在一个拓扑序列中，每个顶点必定出现在它的所有前趋顶点之后。

算法思想

  1. 选择一个入度为0的顶点(无前驱结点)，输出它
  2. 删除该顶点及其所有关联的边

重复上述两个步骤，直到图中不再有入度为0的点为止，若所有的点都被输出，则排序成功；否则图中存在有向环。

该算法也可用于判断该图是否存在回路。

算法步骤

  1. 初始化 ：
    • 计算每个顶点的入度（即指向该顶点的边的数量）。
    • 将所有入度为零的顶点放入一个队列或优先队列（可用队列实现）。
  2. 处理队列 ：
    • 从队列中取出一个入度为零的顶点，并将其加入拓扑排序结果中。
    • 对该顶点的所有出边表顶点进行处理：逐一将它们的入度减1。
    • 如果某个邻接顶点的入度变为零，则将该顶点加入队列。
  3. 检查循环依赖 ：
    • 如果最终所有顶点都被处理完毕，且没有节点剩余，说明图是一个有向无环图（DAG），拓扑排序成功。
    • 如果队列为空，但图中仍有未处理的节点，说明图中存在环路，无法进行拓扑排序。

c实现代码如下；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 图的邻接表表示
int graph[MAX_NODES][MAX_NODES] = {0};  // 邻接矩阵
int in_degree[MAX_NODES];  // 记录每个节点的入度

// 函数：拓扑排序
void topological_sort(int n) {
    // 计算每个节点的入度
    for (int i = 0; i < n; i++) {
        in_degree[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] == 1) {
                in_degree[j]++;
            }
        }
    }

    // 将所有入度为0的节点加入队列
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            enqueue(i);
        }
    }

    int count = 0;  // 记录处理的节点数
    printf("拓扑排序结果：\n");

    while (!is_empty()) {
        int node = dequeue();
        printf("%c ", node + 'A');  // 输出节点（假设节点是字母A-Z）
        count++;
        // 对所有邻接节点的入度减1
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1) {
                in_degree[i]--;
                if (in_degree[i] == 0) {
                    enqueue(i);
                }
            }
        }
    }

    // 如果处理的节点数不足，说明图中存在环路
    if (count != n) {
        printf("\n图中存在环路，无法进行拓扑排序。\n");
    }

在清华大小出版社出版，严蔚敏老师出版的教材p182 页给出的求拓扑排序的算法中，使用数据结构栈而非此处的队列来进行拓扑排序。使用队列还是栈其本质区别是：

  • 栈：选择入度为0的顶点时从大到小依次选择。
  • 队列：选择入度为0的顶点时从小到大依次选择。

复杂度

  • 时间复杂度 ：O(V + E)，其中 V 是节点数，E 是边数。我们需要遍历每个节点和边来计算出度，并在拓扑排序过程中遍历每个节点和边来更新出度。
  • 空间复杂度 ：O(V + E)，用于存储图的邻接矩阵和出度数组。

无后继的顶点优先

算法思想

从图中找出 没有后继的顶点 （即出度为零的节点），优先处理这些顶点。具体来说，这个算法和 无前趋的顶点优先算法 （Kahn算法）类似，只是顺序上不同。

算法思想

  1. 选择一个出度为0的顶点(无后继结点)，输出它
  2. 删去该顶点以及所有关联的入边。

重复上述两个步骤，直到图中不再有出度为0的顶点为止，若所有顶点都被输出，则排序成功；否则图中有有向环。

算法步骤

  1. 计算每个节点的出度 （即指向其他节点的边的数量）。
  2. 初始化 ：找出所有出度为零的节点（即没有后继节点的节点），将它们放入一个队列或栈中。
  3. 处理队列 ：
    • 从队列中取出一个没有后继的节点，将其加入拓扑排序的结果中。
    • 删除该节点以及所有指向该节点的边（即更新它的前驱节点的出度）。
    • 如果某个前驱节点的出度变为零，则将该节点也加入队列，继续处理。
  4. 检查图中是否有环 ：如果最终没有处理完所有节点，则说明图中有环，无法完成拓扑排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 图的邻接矩阵表示
int graph[MAX_NODES][MAX_NODES] = {0};  // 邻接矩阵
int out_degree[MAX_NODES];  // 记录每个节点的出度

// 函数：拓扑排序
void topological_sort(int n) {
    // 计算每个节点的出度
    for (int i = 0; i < n; i++) {
        out_degree[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] == 1) {
                out_degree[i]++;
            }
        }
    }

    // 将所有出度为0的节点加入队列
    for (int i = 0; i < n; i++) {
        if (out_degree[i] == 0) {
            enqueue(i);
        }
    }

    int count = 0;  // 记录处理的节点数
    printf("拓扑排序结果：\n");

    while (!is_empty()) {
        int node = dequeue();
        printf("%c ", node + 'A');  // 输出节点（假设节点是字母A-Z）

        count++;

        // 对所有邻接的节点的出度减1
        for (int i = 0; i < n; i++) {
            if (graph[i][node] == 1) {
                out_degree[i]--;
                if (out_degree[i] == 0) {
                    enqueue(i);
                }
            }
        }
    }

    // 如果排序的节点数不足，说明图中存在环路
    if (count != n) {
        printf("\n图中存在环路，无法进行拓扑排序。\n");
    }
}

复杂度

  • 时间复杂度 ：O(V + E)，其中 V 是节点数，E 是边数。我们需要遍历每个节点和边来计算出度，并在拓扑排序过程中遍历每个节点和边来更新出度。
  • 空间复杂度 ：O(V + E)，用于存储图的邻接矩阵和出度数组。

关键路径

AOE图

AOE图（Activity On Edge graph，边表示活动的图）是一种用于项目管理和调度的网络图。它用有向图的形式表示项目中的任务（活动）及其依赖关系。AOE图通常用于项目的关键路径分析（Critical Path Method，CPM），帮助确定完成项目所需的最短时间，并识别关键任务。

基本概念

  • 活动（Activity）： 表示项目中的一项具体任务，通常用图中的有向边表示。
  • 事件（Event）： 表示任务的开始或结束节点，通常用图中的圆圈（节点）表示。
  • 权重（Weight）： 边上的权值表示完成该活动所需的时间或成本。
  • 源点：入度为0的顶点，即工程的开始点
  • 汇点：出度为0的顶点，即工程的完成点
  • 活动持续时间：活动$a_i$由弧<j,k>表示，用dut(<j,k>)，表示持续时间
  • 关键路径：从源点到汇点的最长路径
  • 关键活动：关键路径上的活动

对应关系

  • 顶点(vertex)用来表示事件(evevt)
  • 弧(edge)用来表示活动(activity)，权值(weight)表示活动所需的事件(time)

求关键路径算法步骤

  1. 列出所有任务 ：
    首先，列出项目中所有需要执行的任务，并确定各任务之间的依赖关系。即哪些任务必须在其他任务之前完成。
  2. 确定每个任务的持续时间 ：
    为每个任务指定预计的工期或持续时间，通常是基于经验或历史数据来估算。
  3. 绘制网络图（AON图） ：
    基于任务之间的依赖关系，绘制项目的网络图。通常使用节点表示任务，箭头表示任务之间的依赖关系。
  4. 计算每个任务的最早开始时间（ES）和最早完成时间（EF） ：
    • 最早开始时间（ES, Earliest Start） ：任务的最早开始时间，取决于其前置任务的最早完成时间。
    • 最早完成时间（EF, Earliest Finish） ：任务的最早完成时间，计算公式为：
      EF=ES+任务工期\text{EF} = \text{ES} + \text{任务工期}EF=ES+任务工期

对所有任务按顺序计算最早开始和最早完成时间，通常从项目开始时间出发，逐步推进。

  1. 计算每个任务的最晚开始时间（LS）和最晚完成时间（LF） ：
    • 最晚完成时间（LF, Latest Finish） ：项目的最晚完成时间，即整个项目可以接受的最晚结束时间。通常是项目的最后一个任务的最晚完成时间。
    • 最晚开始时间（LS, Latest Start） ：任务的最晚开始时间，计算公式为：
      LS=LF−任务工期\text{LS} = \text{LF} - \text{任务工期}LS=LF−任务工期

从项目的最后任务开始，反向推导每个任务的最晚完成时间和最晚开始时间。

  1. 计算总时差（Slack） ：
    总时差（Slack）是指任务可以延迟的最大时间，而不影响整个项目的完成时间。公式为：
    $Slack=LS−ES$
    或
    $Slack=LF−EF$
    对每个任务计算其Slack值，Slack值为零的任务表示它们是关键任务。
  2. 识别关键路径 ：
    关键路径是整个项目中持续时间最长的一条路径，它决定了项目的最短完成时间。关键路径上的所有任务的Slack值为零，即它们的开始时间和完成时间没有灵活性。ES == LS 或 EF == LF
  3. 更新和调整 ：
    在项目执行过程中，可能会发生变化，需定期检查并更新关键路径。任务进度的延误、任务完成时间的变化可能会影响到关键路径。

求最早开始时间

  1. 初始化最早开始时间 ：
    项目的起始任务（即没有前置任务的任务）的最早开始时间通常为 0 。如果有多个起始任务，它们的最早开始时间都是0。

  2. 计算后续任务的最早开始时间 ：
    对于每个任务，最早开始时间是其所有前置任务的最早完成时间中的最大值。即，任务只能在所有前置任务完成后才开始。因此，任务的最早开始时间（ES）可以通过以下公式计算：

    $$
    \text{ES=max(EF of all preceding tasks)}
    $$

    其中，EF是指前置任务的最早完成时间（Earliest Finish Time），可以通过公式计算：

    $$
    EF=ES+任务工期
    $$

  3. 逐步推导

    从项目的开始节点出发，逐个计算每个任务的最早开始时间。对于每个任务，计算其前置任务的最早完成时间，然后选取这些前置任务的最晚完成时间作为当前任务的最早开始时间。

计算示例：

假设有以下任务及其工期和依赖关系：

  • 任务A （工期3天），没有前置任务
  • 任务B （工期2天），前置任务是A
  • 任务C （工期4天），前置任务是A
  • 任务D （工期1天），前置任务是B和C

步骤如下：

  1. 任务A的最早开始时间：
    由于任务A没有前置任务，所以它的最早开始时间为 0 。

    $$
    \text{ES(A)} = 0
    $$

    任务A的最早完成时间为：

    $$
    \text{EF(A)} = 0 + 3 = 3
    $$

  2. 任务B的最早开始时间：
    任务B的前置任务是A。任务B的最早开始时间是任务A的最早完成时间，即3天。

    $$
    \text{ES(B)} = \text{EF(A)} = 3
    $$

    任务B的最早完成时间为：

    $$
    \text{EF(B)} = 3 + 2 = 5
    $$

  3. 任务C的最早开始时间：
    任务C的前置任务是A。任务C的最早开始时间同样是任务A的最早完成时间，即3天。

    $$
    \text{ES(C)} = \text{EF(A)} = 3
    $$

    任务C的最早完成时间为：

    $$
    \text{EF(C)} = 3 + 4 = 7
    $$

  4. 任务D的最早开始时间：
    任务D的前置任务是B和C。任务D的最早开始时间是任务B和C的最早完成时间中的最大值，即任务C的最早完成时间（7天）。

    $$
    \text{ES(D)} = \max(\text{EF(B)}, \text{EF(C)}) = \max(5, 7) = 7
    $$

    任务D的最早完成时间为：

    $$
    \text{EF(D)} = 7 + 1 = 8
    $$

最终结果：

  • 任务A ：ES = 0, EF = 3
  • 任务B ：ES = 3, EF = 5
  • 任务C ：ES = 3, EF = 7
  • 任务D ：ES = 7, EF = 8

求最迟开始时间

  1. 初始化最迟完成时间（LF） ：
    对于项目的最终任务（即没有后续任务的任务），其最迟完成时间通常等于项目的 总工期 ，即项目的整体完成时间。
    如果是多个终止任务，它们的最迟完成时间相同，等于项目的总工期。

  2. 计算最迟完成时间（LF） ：
    对于每个任务，最迟完成时间是其所有后继任务的最迟开始时间中的最小值。即，任务的最迟完成时间不能超过后继任务的最迟开始时间。
    公式为：

    $$
    \text{LF} = \min(\text{LS of all succeeding tasks})
    $$

    如果一个任务没有后继任务，最迟完成时间就是项目的总工期（或者该终止任务的最迟完成时间）。

  3. 计算最迟开始时间（LS） ：
    最迟开始时间是任务的最迟完成时间减去任务的工期。
    公式为：

    $$
    text{LS} = \text{LF} - \text{任务工期}
    $$

  4. 逐步推进 ：
    从项目的最后任务开始，向前计算每个任务的最迟完成时间（LF）和最迟开始时间（LS）。对每个任务，计算其后继任务的最迟开始时间，然后选取这些后继任务的最早开始时间作为当前任务的最迟完成时间。

计算示例

假设我们继续使用之前的例子：

  • 任务A （工期3天），没有前置任务
  • 任务B （工期2天），前置任务是A
  • 任务C （工期4天），前置任务是A
  • 任务D （工期1天），前置任务是B和C

首先，已经计算了任务的最早开始时间（ES）和最早完成时间（EF）：

  • 任务A ：ES = 0, EF = 3
  • 任务B ：ES = 3, EF = 5
  • 任务C ：ES = 3, EF = 7
  • 任务D ：ES = 7, EF = 8

步骤：

  1. 初始化最迟完成时间（LF） ：

    • 任务D是终止任务（没有后续任务），因此它的最迟完成时间就是项目的总工期（假设为8天）。

    $$
    text{LF(D)} = 8
    $$

  2. 计算最迟开始时间（LS） ：
    任务D的最迟开始时间为：

    $$
    \text{LS(D)} = \text{LF(D)} - \text{工期(D)} = 8 - 1 = 7
    $$

  3. 计算任务B的最迟完成时间（LF） ：
    任务B的后继任务是任务D。任务D的最迟开始时间为7天，所以任务B的最迟完成时间是7天。

    $$
    \text{LF(B)} = \text{LS(D)} = 7
    $$

  4. 计算任务B的最迟开始时间（LS） ：
    任务B的最迟开始时间为：

    $$
    \text{LS(B)} = \text{LF(B)} - \text{工期(B)} = 7 - 2 = 5
    $$

  5. 计算任务C的最迟完成时间（LF） ：
    任务C的后继任务是任务D。任务D的最迟开始时间为7天，所以任务C的最迟完成时间是7天。

    $$
    \text{LF(C)} = \text{LS(D)} = 7
    $$

  6. 计算任务C的最迟开始时间（LS） ：
    任务C的最迟开始时间为：

    $$
    \text{LS(C)} = \text{LF(C)} - \text{工期(C)} = 7 - 4 = 3
    $$

  7. 计算任务A的最迟完成时间（LF） ：
    任务A的后继任务是任务B和任务C。任务B的最迟开始时间为5天，任务C的最迟开始时间为3天。任务A的最迟完成时间为这两个值中的最小值，即3天。

    $$
    \text{LF(A)} = \min(\text{LS(B)}, \text{LS(C)}) = \min(5, 3) = 3
    $$

  8. 计算任务A的最迟开始时间（LS） ：
    任务A的最迟开始时间为：

    $$
    \text{LS(A)} = \text{LF(A)} - \text{工期(A)} = 3 - 3 = 0
    $$

最终结果：

  • 任务A ：LS = 0, LF = 3
  • 任务B ：LS = 5, LF = 7
  • 任务C ：LS = 3, LF = 7
  • 任务D ：LS = 7, LF = 8

算法描述：

在课本中：

  • ve数组表示每个任务的最早开始时间
  • vl表示每个数组的最晚开始时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Status TopologicalOrder(ALGraph G, Stack &S) 
// 计算各顶点的最早发生时间ve(全局变量)，并用栈S返回G的一个拓扑序列
{  
  FindInDegree(G, indegree);  // 计算每个顶点的入度（依赖任务数），保存在indegree数组中
  InitStack(S);               // 初始化栈S，用于存储拓扑排序的结果
  count = 0;                   // 记录已经处理的顶点数
  ve[0..G.vexnum-1] = 0;      // 初始化所有顶点的最早发生时间ve为0
  for (i = 0; i < G.vexnum; ++i)  
    if (!indegree[i])          // 如果顶点i的入度为0，表示没有前置任务
      push(S, i);              // 将其入栈S，作为拓扑排序的起点
  InitStack(T);                // 初始化临时栈T，用于存储拓扑排序的顺序
  while (!StackEmpty(S)) {     // 当栈S不为空时，表示还有未处理的顶点
    pop(S, j);                 // 从栈S弹出一个顶点j
    push(T, j);                // 将顶点j加入到临时栈T，表示它已经处理过
    ++count;                   // 已处理顶点数增加
    for (p = G.vertices[j].firstarc; p; p = p->nextarc) {  
      // 遍历与顶点j相连的所有邻接点
      k = p->adjvex;           // 获取邻接点k
      if (! (--indegree[k]))    // 如果邻接点k的入度减1后为0，表示没有前置任务
        push(S, k);             // 将邻接点k入栈S，等待处理
      if (ve[j] + (p->weight) > ve[k])  
        // 更新顶点k的最早发生时间ve[k]
        // ve[k] = max(ve[k], ve[j] + p->weight)，表示如果通过顶点j能早些到达k，则更新k的最早发生时间
        ve[k] = ve[j] + (p->weight);
    } // for
  } // while
  
  if (count < G.vexnum)        // 如果处理的顶点数小于图中的总顶点数，说明图中有环
    return ERROR;              // 返回ERROR，表示拓扑排序失败（图不是DAG）
  else
    return OK;                 // 否则返回OK，表示成功计算了拓扑排序
} // TopologicalOrder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Status CriticalPath(ALGraph G) 
// G为有向网，输出G的各项关键活动
{
  if (!TopologicalOrder(G, T))  // 如果拓扑排序失败（图中有环），返回ERROR
    return ERROR;

  // 初始化最迟发生时间vl，假设项目的总工期为最后一个顶点的最早发生时间
  vl[0.. G.vexnum-1] = ve[G.vexnum-1];  

  // 逆拓扑序列计算每个顶点的最迟发生时间vl
  while (!StackEmpty(T)) {  
    pop(T, j);  // 从栈T弹出一个顶点j
    // 遍历与顶点j相连的所有邻接点
    for (p = G.vertices[j].firstarc; p; p = p->nextarc) { 
      k = p->adjvex;  // 获取邻接点k
      // 更新顶点j的最迟发生时间vl[j]
      if (vl[k] - (p->weight) < vl[j])  
        vl[j] = vl[k] - (p->weight);
    } // for
  } // while

  // 计算并输出每个活动的最早开始时间、最迟开始时间，并确定关键活动
  for (j = 0; j < G.vexnum; ++j) {  
    // 遍历所有顶点的所有出边，计算并输出每个活动的ee、el、tag
    for (p = G.vertices[j].firstarc; p; p = p->nextarc) {
      k = p->adjvex;   // 获取邻接点k
      dut = p->weight;  // 获取活动的持续时间（边的权重）
  
      // 计算最早开始时间ee和最迟开始时间el
      ee = ve[j];  
      el = vl[k] - dut;

      // 如果活动的最早开始时间和最迟开始时间相等，则该活动为关键活动
      tag = (ee == el) ? '*' : ' ';  

      // 输出活动的起点、终点、持续时间、最早开始时间、最迟开始时间和是否关键活动
      printf("%d -> %d  %d  %d  %d  %c\n", j, k, dut, ee, el, tag);
    } // for
  } // for
} // CriticalPath

最短路径

定义

单源最短路径：从某源点到其它所有顶点间的最短路径。

每一对顶点间的最短路径：各顶点到其它所有顶点间的最短路径。

Dijkstra 算法

算法思想

  1. 利用贪心策略，每次选择离起始点最近的未访问节点。
  2. 更新从起始点到其他节点的最短路径。
  3. 重复步骤，直到所有节点都被访问。

算法步骤

  1. 初始化

    • 创建一个数组 dist[]：记录从起始节点到每个节点的最短距离，初始化为与该点直接相连的点的距离，若未直接相连，则记为$\infty$，起始结点距离为0。
    • 创建一个布尔数组 visited[]：记录节点是否已确定最短路径，初始值为 False。
    • 创建一个数组 prev[]（可选）：记录路径的前驱节点，用于还原路径。

  2. 寻找最近的未访问节点

    • 在所有未访问节点中，找到 dist[] 值最小的节点 u。

  3. 更新邻接节点

    • 对于节点 u 的所有邻接节点 v：
      • 如果 v 未访问过，并且通过 u 到达 v 的距离小于 dist[v]：
      • 更新 dist[v] = dist[u] + w(u, v)，其中 w(u, v) 是边的权重。
      • 更新 prev[v] = u（如果需要记录路径）。

  4. 标记节点为已访问

    • 将节点 u 标记为已访问。

  5. 重复步骤 2-4

    • 重复直到所有节点被访问，或者未访问节点的最小距离为 $\infty$（表示无法到达）

示例

1
2
3
4
5
6
 0 ——(4)—→ 1 ——(1)—→ 3
 |         ↘         ↘
(1)        (2)       (3)
 ↓           ↓         ↓
 2 ———(5)——→ 4 ——(6)—→ 5

权重矩阵：

1
2
3
4
5
6
7
8
    0   1   2   3   4   5
0   0   4   1   ∞   ∞   ∞
1   ∞   0   2   1   ∞   ∞
2   ∞   ∞   0   ∞   5   ∞
3   ∞   ∞   ∞   0   3   ∞
4   ∞   ∞   ∞   ∞   0   6
5   ∞   ∞   ∞   ∞   ∞   0

步骤：

  1. 初始化：$dist = [0, 4, 1, \infty , \infty , \infty ]$，visited = [False, False, False, False, False, False]。

  2. 选择 dist[] 最小的未访问节点 2，并标记 visited[2] = True：

    • 更新邻接节点：dist[4] = 1 + 5 = 6。

  3. 选择未访问节点中最小的节点 1 vidited[1] = True：

    • 更新邻接节点：dist[3] = 4 + 1 = 5。

  4. 选择未访问节点中最小的节点 3 visited[3] = True：

    • 更新邻接节点：dist[5] = 5 + 3 = 8。

    继续访问结点4和5。

  5. 终点。

最终结果：dist = [0, 4, 1, 5, 6, 8]。从节点 0 到其他节点的最短距离依次为 0、4、1、5、6、8。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#define MAX 100         // 最大节点数
#define INF INT_MAX     // 表示无穷大

// 找到未访问节点中最小距离的节点
int findMinDistance(int dist[], int visited[], int n) {
    int min = INF, minIndex = -1;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < min) {
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

// Dijkstra算法实现
void dijkstra(int graph[MAX][MAX], int n, int start) {
    int dist[MAX];      // 存储从起点到各节点的最短距离
    int visited[MAX];   // 标记节点是否已访问
    int prev[MAX];      // 用于存储路径信息

    // 初始化距离数组和访问标记
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
        prev[i] = -1;   // 初始化前驱节点为-1（无路径）
    }
    dist[start] = 0;    // 起点到自己的距离为0

    // 遍历所有节点
    for (int i = 0; i < n - 1; i++) {
        // 找到当前未访问节点中距离最小的节点
        int u = findMinDistance(dist, visited, n);
        if (u == -1) break; // 所有节点已访问或不可达

        visited[u] = 1; // 标记该节点为已访问

        // 更新邻接节点的距离
        for (int v = 0; v < n; v++) {
            // 更新条件：v未访问，u到v有边，且通过u到v的距离更短
            if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                prev[v] = u; // 记录前驱节点
            }
        }
    }
}

Floyd算法

Floyd算法是一种用于解决多源最短路径问题的经典算法。它可以在加权图（允许正权重或负权重，但不允许负权环）中计算任意两点之间的最短路径。

算法思想

Floyd算法是基于动态规划的思想，通过不断更新两点之间的最短路径长度，最终找到所有点对之间的最短路径。其核心是逐步引入中间节点，检查通过该中间节点是否可以缩短两点之间的路径。

算法步骤

  1. 初始化距离矩阵 dist[][]：

    • 如果 i == j，则 dist[i][j] = 0。
    • 如果 i 和 j 之间有边，则 dist[i][j] = 边的权重。
    • 如果 i 和 j 之间没有边，则 dist[i][j] = ∞。

  2. 引入中间节点进行更新：

    • 对于每个节点 k，依次将其作为中间节点，更新所有节点对 (i, j) 之间的最短路径。
    • 更新公式：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。

  3. 重复上述步骤，直到所有节点都被引入为中间节点。

示例

1
2
3
4
5
 0 ——(4)—→ 1 ——(1)—→ 3
 |         ↘         ↘
(1)        (2)       (3)
 ↓           ↓         ↓
 2 ———(5)——→ 4 ——(6)—→ 5

权重矩阵：

1
2
3
4
5
6
7
    0   1   2   3   4   5
0   0   4   1   ∞   ∞   ∞
1   ∞   0   2   1   ∞   ∞
2   ∞   ∞   0   ∞   5   ∞
3   ∞   ∞   ∞   0   3   ∞
4   ∞   ∞   ∞   ∞   0   6
5   ∞   ∞   ∞   ∞   ∞   0

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define MAX 100         // 最大节点数
#define INF INT_MAX     // 表示无穷大

// Floyd算法实现
void floyd(int graph[MAX][MAX], int n) {
    int dist[MAX][MAX];
    int next[MAX][MAX];    // 路径前驱矩阵（可选）

    // 初始化距离矩阵和路径矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
            if (graph[i][j] != INF && i != j) {
                next[i][j] = j;
            } else {
                next[i][j] = -1;
            }
        }
    }

    // 动态规划计算最短路径
    for (int k = 0; k < n; k++) {           // 中间节点
        for (int i = 0; i < n; i++) {       // 起点
            for (int j = 0; j < n; j++) {   // 终点
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }
}

复杂度

  • 时间复杂度：O(V^3)，其中 V 是节点数。需要三重循环遍历所有节点对。
  • 空间复杂度：O(V^2)，用于存储距离矩阵。
笔记
#数据结构
数据结构-图(二)
http://blog.ulna520.com/2024/12/19/数据结构-图(二)_20241219_140301/
Veröffentlicht am
December 19, 2024
Urheberrechtshinweis