数据结构之图的应用

最小生成树

在图论中，生成树是一个连通图中包含所有顶点且只含有尽可能少的边的子图。对于一个带权的连通无向图 $ G = (V, E) $，最小生成树（Minimum Spanning Tree, MST）是所有生成树中权值和最小的那棵树。生成树的特点和最小生成树的性质包括：

最小生成树的性质

唯一性：
- 最小生成树并不一定是唯一的；在图中可能存在多棵最小生成树。
- 如果图中所有边的权值互不相等，则最小生成树是唯一的。
- 如果图本身是一棵树（即边数 $ E = V - 1 $），则最小生成树就是这棵树本身。
权值和的唯一性：
- 尽管最小生成树可能有多种形状，但其对应的边的权值之和是唯一的，并且是最小的。
边数：
- 最小生成树的边数等于顶点数减一，即 $ |E| = |V| - 1 $。
贪心性质：
- 对于一个带权连通无向图 $ G = (V, E) $ 和顶点集 $ U $ 的一个非空子集，若边 $ (u, v) $ 是从 $ U $ 到 $ V - U $ 的最小权值边，则必定存在一棵最小生成树包含该边。

通用的最小生成树算法

通用的最小生成树算法可以描述为：

GENERIC MST(G):
T = NULL; // 初始化生成树为空
while T 未形成一棵生成树: // 循环直到形成生成树
    找到一条最小代价边 (u, v)，并且加入 T 后不会产生回路
    T = T ∪ {(u, v)} // 将边加入生成树

Prim 算法

Prim 算法是一种用于构造带权无向连通图的最小生成树（MST）的贪心算法。它的执行过程与 Dijkstra 算法求最短路径的方法非常相似。

算法思想

Prim 算法的基本思路是从一个顶点出发，逐步将图中的顶点加入最小生成树，每次加入距离当前树最“近”的顶点及其对应的最小边，直到所有顶点都被纳入生成树。

具体步骤

初始化：
- 选择图中的任意一个顶点作为起始顶点，将其加入生成树。
- 设定一个空树 $ T = (U, E') $，其中 $ U $ 是已被加入生成树的顶点集合，$ E' $ 是生成树中的边集合。
- 初始时，$ U $ 只包含一个顶点，$ E' = $。
循环：
- 每次从图中选择一条连接 $ U $ 集合内的顶点和 $ V-U $ 集合中的顶点的最小权值边 $ (u, v) $。
- 将这条边加入生成树，即 $ E' = E' {(u, v)} $，并将顶点 $ v $ 加入集合 $ U $。
- 重复上述步骤，直到所有顶点都被加入 $ U $ 中。
结束：
- 当 $ U $ 包含了所有顶点时，生成树构建完成，算法终止。

算法实现

下面是 Prim 算法的简单实现伪代码：

void Prim(Graph *G, Tree *T) {
    T = ∅;  // 初始化空树
    U = {w};  // 从任意顶点 w 开始
    
    while (U 不等于 V) {  // 当树中未包含所有顶点时
        // 选择一条最小权值边 (u, v)，其中 u ∈ U 且 v ∉ U
        找到最小的 (u, v);
        
        // 将 (u, v) 加入生成树
        T = T ∪ {(u, v)};
        
        // 将顶点 v 加入集合 U
        U = U ∪ {v};
    }
}

时间复杂度

Prim 算法的时间复杂度为 $ O(V^2) $，其中 $ V $ 是图中的顶点数。该复杂度独立于边数 $ E $，因此 Prim 算法适用于边稠密的图。

如果使用最小堆等数据结构进行优化，算法的时间复杂度可以降低到 $ O(E V) $，但这会增加实现的复杂性。

Prim 算法的执行过程图示

假设有一个带权连通无向图，Prim 算法的执行过程可以通过以下步骤构造最小生成树：

从图中选择一个起始顶点，例如顶点 1，将其加入树 $ T $。
查找与顶点 1 相邻的最小权值边，并将该边及其顶点加入生成树。
重复此过程，直到所有顶点都被加入生成树。

图 6.15 所示的是 Prim 算法构造最小生成树的过程。

总结

Prim 算法逐步扩展最小生成树，每次从树中找到一个最小的边，将其连接到树中的顶点。
该算法适合于边稠密的图，因为其时间复杂度为 $ O(V^2) $，与图的边数无关。
通过使用合适的数据结构可以优化 Prim 算法的性能。

Kruskal 算法

Kruskal 算法是一种用于构造带权连通无向图的最小生成树（MST）的贪心算法。与 Prim 算法不同，Kruskal 算法是从边的角度来构造最小生成树的，通过不断选择当前未被选择且权值最小的边来连接不同的连通分量，最终形成一棵最小生成树。

算法思想

Kruskal 算法的核心思想是从一棵森林开始，每个顶点自成一个连通分量，然后按边的权值从小到大依次选择边，将其加入生成树中。如果这条边连接的顶点属于不同的连通分量，则加入生成树，否则舍弃，直到所有顶点被连接为一个连通分量。

具体步骤

初始化：
- 设定一个初始森林 $ T $，其中每个顶点都是一个独立的连通分量。
- 将所有的边按权值递增顺序排序。
循环：
- 依次选择最小权值的边 $ (u, v) $。
- 如果 $ u $ 和 $ v $ 属于不同的连通分量，将这条边加入生成树，并合并这两个连通分量。
- 如果 $ u $ 和 $ v $ 属于相同的连通分量，舍弃该边，继续选择下一条边。
- 重复上述过程，直到生成树包含 $ n-1 $ 条边。
结束：
- 当生成树 $ T $ 包含 $ n-1 $ 条边时，算法终止，得到的 $ T $ 就是最小生成树。

算法实现

下面是 Kruskal 算法的简单实现伪代码：

void Kruskal(Graph *G, Tree *T) {
    T = ∅;  // 初始化空树，T 仅含顶点
    numS = n;  // 初始连通分量数等于顶点数
    
    while (numS > 1) {  // 当连通分量数大于 1 时
        // 选择权值最小的边 (u, v)
        (u, v) = 选择权值最小的边;
        
        if (u 和 v 属于不同的连通分量) {
            // 将 (u, v) 加入生成树
            T = T ∪ {(u, v)};
            // 连通分量数减 1
            numS--;
        }
    }
}

时间复杂度

Kruskal 算法的时间复杂度为 $ O(E E) $，其中 $ E $ 是图中的边数。主要的开销来自于：

对边按权值排序需要 $ O(E E) $。
每次选择最小权值边和合并连通分量可以使用并查集（Union-Find）来实现，每次操作的时间复杂度为 $ O(E) $。

因此，Kruskal 算法适合于边稀疏的图（即边数较少但顶点较多的图）。

并查集优化

在 Kruskal 算法中，判断两个顶点是否属于同一个连通分量，以及合并不同的连通分量，可以通过并查集（Union-Find）数据结构来优化。并查集支持高效的查找和合并操作，能够快速确定两个顶点是否在同一个集合中。

Kruskal 算法的执行过程图示

图 6.16 所示的是 Kruskal 算法构造最小生成树的过程：

初始时，图中每个顶点都是一个独立的连通分量。
按权值递增顺序选择边，逐步将不同连通分量连接起来。
当所有顶点形成一个连通分量时，生成树构造完成。

总结

Kruskal 算法通过按权值递增顺序选择边，逐步将连通分量合并成一棵树。
该算法适合于边稀疏的图，时间复杂度为 $ O(E E) $，通过使用并查集可以进一步优化。
Kruskal 算法的优势在于其实现简单、效率较高，特别适合于顶点多但边相对较少的图。

最短路径

带权图的最短路径概念

在带权图中，路径的权值之和被定义为路径的带权路径长度。最短路径是带权路径长度最小的路径。求解最短路径的问题通常依赖于以下性质：两点之间的最短路径也包含了路径上其他顶点间的最短路径。

最短路径问题可以分为两类：

单源最短路径：从图中某一顶点到其他各顶点的最短路径，使用 Dijkstra 算法求解。
每对顶点间的最短路径：使用 Floyd 算法求解。

1. Dijkstra 算法

Dijkstra 算法用于求解单源最短路径问题。它通过逐步扩展已找到的最短路径顶点集合 $ S $，每次选择最小路径长度的顶点加入 $ S $，并不断更新到剩余顶点的最短路径长度。该算法的核心步骤如下：

算法步骤

初始化：
- 设置集合 $ S $ 仅包含源点。
- 数组 dist[] 记录从源点到各顶点的当前最短路径长度，初始时：
  - 如果从源点 $ u $ 到顶点 $ v $ 有直接边，则 dist[v] = arcs[u][v]（边的权值）。
  - 否则，dist[v] = \infty。
循环选择最短路径顶点：
- 每次从 $ V - S $ 中选择当前最短路径的顶点 $ v $，加入集合 $ S $。
- 更新从源点到 $ V - S $ 中顶点的路径长度：若通过 $ v $ 到某顶点的路径更短，则更新该顶点的 dist[] 值。
重复上述步骤直到所有顶点都加入集合 $ S $。

代码示例

void Dijkstra(int n, int arcs[][], int dist[], int path[], int start) {
    bool S[n] = {false};  // 记录已找到最短路径的顶点
    for (int i = 0; i < n; i++) {
        dist[i] = arcs[start][i];
        if (dist[i] < ∞) path[i] = start;
        else path[i] = -1;
    }
    S[start] = true;
    
    for (int i = 1; i < n; i++) {
        // 选择当前最短路径的顶点
        int min = ∞, u = -1;
        for (int j = 0; j < n; j++) {
            if (!S[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        S[u] = true;
        
        // 更新 dist[]
        for (int v = 0; v < n; v++) {
            if (!S[v] && dist[u] + arcs[u][v] < dist[v]) {
                dist[v] = dist[u] + arcs[u][v];
                path[v] = u;
            }
        }
    }
}

示例

假设图的邻接矩阵如下（图 6.17）：

i j	1	2	3	4	5
1	∞	10	∞	∞	5
2	∞	∞	1	∞	2
3	∞	∞	∞	4	∞
4	7	∞	6	∞	∞
5	∞	3	9	2	∞

从顶点 1 出发，Dijkstra 算法的执行过程如下：

初始化：
- 集合 $ S = {1} $
- dist[] 初值：dist[1] = 0, dist[2] = 10, dist[3] = ∞, dist[4] = ∞, dist[5] = 5
第 1 轮：
- 选择 dist[5] = 5，将顶点 5 加入 $ S $。
- 更新 dist[]：dist[2] = 8, dist[4] = 7
第 2 轮：
- 选择 dist[4] = 7，将顶点 4 加入 $ S $。
- 更新 dist[]：dist[3] = 13
第 3 轮：
- 选择 dist[2] = 8，将顶点 2 加入 $ S $。
- 更新 dist[]：dist[3] = 9
第 4 轮：
- 选择 dist[3] = 9，将顶点 3 加入 $ S $。

最终，最短路径长度为：

从顶点 1 到 2：路径 1 → 5 → 2，长度为 8。
从顶点 1 到 3：路径 1 → 5 → 2 → 3，长度为 9。
从顶点 1 到 4：路径 1 → 5 → 4，长度为 7。
从顶点 1 到 5：路径 1 → 5，长度为 5。

Dijkstra 与 Prim 算法的相似性

Dijkstra 和 Prim 算法在步骤上具有相似性：都使用贪心策略，逐步选择当前最小权值的顶点或边。然而，Prim 算法用于构造最小生成树，而 Dijkstra 算法用于求解单源最短路径。

负权值限制

Dijkstra 算法不适用于含有负权边的图，因为一旦某顶点的最短路径被确定，它就无法再被更新，而负权边可能导致路径长度的变化。

Floyd算法求解所有顶点之间的最短路径问题

问题描述：

给定一个带权有向图，权值均大于0。对于任意两个顶点 $ v_i v_j $，要求计算从 $ v_i $ 到 $ v_j $ 的最短路径及其长度。

Floyd算法的基本思想：

Floyd算法通过引入中间顶点来逐步优化任意两个顶点之间的最短路径。算法的核心是更新一个矩阵，其中每个元素表示从某个顶点到另一个顶点的当前已知最短路径长度。经过多轮迭代，最终得到所有顶点对之间的最短路径。

算法的步骤如下：

初始化：建立一个初始矩阵 $ A^{(0)} $，其中每个元素 $ A^{(0)}[i][j] $ 表示顶点 $ v_i $ 到顶点 $ v_j $ 的初始路径长度：
- 如果 $ v_i $ 和 $ v_j $ 之间有边，则 $ A^{(0)}[i][j] $ 等于该边的权值。
- 如果 $ v_i $ 和 $ v_j $ 之间没有边，则 $ A^{(0)}[i][j] = $。
- 如果 $ i = j $，即为顶点自身，则 $ A^{(0)}[i][j] = 0 $。
迭代更新：对于每个中间顶点 $ v_k $，更新矩阵中的所有路径长度：$ A^{(k)}[i][j] = (A^{(k-1)}[i][j], A^{(k-1)}[i][k] + A^{(k-1)}[k][j]) $ 即，检查是否通过顶点 $ v_k $ 可以找到更短的路径。如果可以，则更新路径长度。
最终结果：经过 $ n $ 轮迭代（$ n $ 为顶点数），得到的矩阵 $ A^{(n-1)} $ 中的每个元素就是从 $ v_i $ 到 $ v_j $ 的最短路径长度。

拓扑排序

拓扑排序 是针对有向无环图（DAG，Directed Acyclic Graph）的顶点排序，使得在排序结果中，若顶点 $ A $ 在顶点 $ B $ 之前出现，则在图中不存在从 $ B $ 到 $ A $ 的路径。换句话说，拓扑排序确保如果有一条从顶点 $ A $ 到顶点 $ B $ 的路径，则在排序结果中 $ A $ 必须在 $ B $ 之前出现。

拓扑排序的应用场景

拓扑排序常用于 AOV网（Activity on Vertex） 中。AOV 网用于表示工程任务调度问题，其中顶点表示任务，边表示任务之间的先后关系，即一项任务必须在另一项任务之前完成。在 AOV 网中，若存在环，则任务依赖关系存在循环，意味着任务调度不可能完成。拓扑排序可以检查这种任务依赖的正确性，并为无环的任务依赖关系生成有效的调度顺序。

拓扑排序算法步骤

从图中选择一个 入度为 0 的顶点并输出。入度为 0 的顶点表示没有依赖的任务，或者依赖的任务都已经完成。
删除该顶点和所有以它为起点的边。
重复步骤 1 和 2，直到图为空或不存在入度为 0 的顶点为止。如果图中存在环，则无法继续排序。

示例

图 6.22 展示了一个有向无环图及其拓扑排序过程。每一轮选择一个入度为 0 的顶点并输出，然后删除它和它的所有边，最后得到的拓扑排序序列为 {1, 2, 4, 3, 5}。

算法实现

拓扑排序可以通过以下算法实现，基于栈结构来处理入度为 0 的顶点：

bool TopologicalSort(Graph G) {
    // 初始化栈，存储所有入度为0的顶点
    InitStack(S);
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0) {
            // 将入度为0的顶点入栈
            Push(S, i);
        }
    }
    
    int count = 0; // 记录输出的顶点数
    while (!IsEmpty(S)) {
        Pop(S, i); // 栈顶元素出栈
        print[count++] = i; // 输出顶点 i
        
        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
            // 将所有与顶点i相邻的顶点的入度减1
            v = p->adjvex;
            if (--indegree[v] == 0) {
                Push(S, v); // 若入度为0，入栈
            }
        }
    }
    
    // 如果排序完成后顶点数少于图中顶点总数，说明图中有环
    if (count < G.vexnum) {
        return false; // 拓扑排序失败，有环
    } else {
        return true; // 拓扑排序成功
    }
}

算法解释

初始化栈：将所有入度为 0 的顶点入栈。入度为 0 的顶点表示当前没有其他任务依赖它，可以作为起始任务进行处理。
栈操作：每次从栈中弹出一个顶点，输出该顶点后，将所有与之相邻的顶点的入度减 1。若减完入度后某个顶点的入度变为 0，则将该顶点压入栈，表示它可以被调度。
循环结束条件：当栈为空时，拓扑排序完成。如果输出的顶点数少于图中的顶点数，说明图中存在环，排序失败。