图的存储结构与遍历算法详解

目录

图的定义和基本术语

定义

基本术语

图的类型定义

图的存储结构

一、邻接表（Adjacency List）

1. 结构原理

2. 示例（无向图 vs 有向图）

3. 实现（C++ 简化版）

4. 优缺点

5. 适用场景：稀疏图（边数少，如社交网络、路由拓扑）。

二、邻接矩阵（Adjacency Matrix）

1. 结构原理

2. 示例（无向图 vs 有向图）

3. 实现（C++ 简化版）

4. 优缺点

5. 适用场景：稠密图（边数多，如完全图、电路连接图）。

三、十字链表（Orthogonal List）

1. 结构原理

2. 示意图

3. 优缺点

4. 适用场景：有向图，且需频繁处理入边（如任务调度图）。

四、邻接多重表（Adjacency Multilist）

1. 结构原理

2. 示意图

3. 优缺点

4. 适用场景：无向图，且需频繁增删边（如交通网络实时路况更新）。

总结：存储结构的选择

图的遍历

一、遍历的核心问题

二、深度优先搜索（DFS）

1. 核心思想

2. 实现步骤（以邻接表为例）

3. 示例（无向图）

4. 代码实现（邻接表 + 递归）

三、广度优先搜索（BFS）

1. 核心思想

2. 实现步骤（以邻接表为例）

3. 示例（同上述无向图）

4. 代码实现（邻接表 + 队列）

四、DFS 与 BFS 的对比

五、关键注意事项

图的应用

最小生成树

一、Kruskal 算法实现（基于并查集）

二、Prim 算法实现（基于优先队列）

三、测试用例与运行结果

最短路径

一、Dijkstra 算法（单源最短路径，非负权重）

算法步骤

二、Floyd-Warshall 算法（多源最短路径）

算法步骤：

三、Bellman-Ford 算法（单源最短路径，支持负权重）

算法步骤：

四、测试用例与运行结果

拓扑排序

一、核心概念与适用条件

二、经典算法：Kahn 算法（基于入度与队列）

算法思路

三、另一种实现：基于 DFS 的拓扑排序

算法思路

四、测试用例与运行结果

关键路径

一、核心概念

二、关键参数定义

三、算法步骤

四、 代码实现

五、测试用例与运行结果

---

图的定义和基本术语

定义

组成要素：包含非空顶点集 V（元素称为顶点或结点）和边集 E（元素称为边，用于连接两个顶点）。核心分类：无向图的边无方向，记为 (u,v)；有向图的边有方向，记为 < u,v>，其中 u 是起点、v 是终点。

基本术语

顶点相关：度数是顶点关联的边数，无向图中直接计数，有向图分入度（指向顶点的边数）和出度（背离顶点的边数）；孤立点是度数为 0 的顶点。边相关：环是两端连接同一顶点的边；平行边是无向图中连接同一对顶点的多条边，有向图需方向相同时才称为平行边。图的分类：简单图是无环、无平行边的图；完全图是任意两个顶点间都有边的简单图；子图是顶点集和边集均为原图集子集的图。路径与连通性：路径是顶点序列中相邻顶点间均有边连接；回路是起点与终点相同的路径；连通图（无向）是任意两顶点间都存在路径，有向图中对应强连通（任意两顶点间双向有路径）。

图的类型定义

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <stdexcept>
#include <vector>
#include <functional>  // 用于函数对象
 
 
// --------------------------- 抽象基类：定义图的ADT接口 ---------------------------
template <typename VertexType, typename WeightType = int>
class Graph {
public:
    using Vertex = VertexType;
    using Weight = WeightType;
    using AdjacentMap = std::unordered_map<Vertex, Weight>;  // 邻接顶点→权重映射
 
    // 析构函数（基类必须为虚析构，确保子类析构正确）
    virtual ~Graph() = default;
 
    // 顶点操作
    virtual bool addVertex(const Vertex& v) = 0;              // 添加顶点
    virtual bool removeVertex(const Vertex& v) = 0;           // 删除顶点（及关联边）
    virtual bool hasVertex(const Vertex& v) const = 0;        // 判断顶点是否存在
    virtual size_t vertexCount() const = 0;                   // 获取顶点总数
    virtual std::unordered_set<Vertex> allVertices() const = 0; // 获取所有顶点
 
    // 边操作
    virtual bool addEdge(const Vertex& u, const Vertex& v, const Weight& w = Weight()) = 0; // 添加边
    virtual bool removeEdge(const Vertex& u, const Vertex& v) = 0; // 删除边
    virtual bool hasEdge(const Vertex& u, const Vertex& v) const = 0; // 判断边是否存在
    virtual Weight getEdgeWeight(const Vertex& u, const Vertex& v) const = 0; // 获取边权重
    virtual size_t edgeCount() const = 0;                     // 获取边总数
 
    // 邻接关系
    virtual AdjacentMap getAdjacent(const Vertex& v) const = 0; // 获取顶点的所有邻接顶点及权重
 
    // 遍历操作（使用函数对象，支持lambda）
    virtual void dfs(const Vertex& start, const std::function<void(const Vertex&)>& visit) const = 0;
    virtual void bfs(const Vertex& start, const std::function<void(const Vertex&)>& visit) const = 0;
};
 
 
// --------------------------- 邻接表实现：有向图 ---------------------------
template <typename VertexType, typename WeightType = int>
class DirectedGraph : public Graph<VertexType, WeightType> {
public:
    using Vertex = typename Graph<VertexType, WeightType>::Vertex;
    using Weight = typename Graph<VertexType, WeightType>::Weight;
    using AdjacentMap = typename Graph<VertexType, WeightType>::AdjacentMap;
 
    // 顶点操作
    bool addVertex(const Vertex& v) override {
        if (hasVertex(v)) {
            return false; // 顶点已存在，添加失败
        }
        adjList_[v] = AdjacentMap(); // 初始化空邻接表
        return true;
    }
 
    bool removeVertex(const Vertex& v) override {
        if (!hasVertex(v)) {
            return false; // 顶点不存在，删除失败
        }
 
        // 1. 删除顶点v的邻接表（所有从v出发的边）
        edgeCount_ -= adjList_[v].size();
        adjList_.erase(v);
 
        // 2. 删除所有指向v的边（其他顶点的邻接表中包含v的条目）
        for (auto& [u, neighbors] : adjList_) {
            if (neighbors.erase(v)) { // 若u有边指向v，删除并减少边数
                edgeCount_--;
            }
        }
 
        return true;
    }
 
    bool hasVertex(const Vertex& v) const override {
        return adjList_.find(v) != adjList_.end();
    }
 
    size_t vertexCount() const override {
        return adjList_.size();
    }
 
    std::unordered_set<Vertex> allVertices() const override {
        std::unordered_set<Vertex> vertices;
        for (const auto& [v, _] : adjList_) {
            vertices.insert(v);
        }
        return vertices;
    }
 
    // 边操作
    bool addEdge(const Vertex& u, const Vertex& v, const Weight& w) override {
        // 检查顶点是否存在
        if (!hasVertex(u) || !hasVertex(v)) {
            throw std::invalid_argument("Vertex u or v does not exist");
        }
        // 检查边是否已存在
        if (hasEdge(u, v)) {
            return false;
        }
        adjList_[u][v] = w; // 添加u→v的边
        edgeCount_++;
        return true;
    }
 
    bool removeEdge(const Vertex& u, const Vertex& v) override {
        if (!hasVertex(u) || !hasVertex(v)) {
            return false;
        }
        // 从u的邻接表中删除v
        if (adjList_[u].erase(v)) {
            edgeCount_--;
            return true;
        }
        return false;
    }
 
    bool hasEdge(const Vertex& u, const Vertex& v) const override {
        auto it = adjList_.find(u);
        if (it == adjList_.end()) {
            return false;
        }
        return it->second.find(v) != it->second.end();
    }
 
    Weight getEdgeWeight(const Vertex& u, const Vertex& v) const override {
        if (!hasEdge(u, v)) {
            throw std::invalid_argument("Edge u->v does not exist");
        }
        return adjList_.at(u).at(v);
    }
 
    size_t edgeCount() const override {
        return edgeCount_;
    }
 
    // 邻接关系
    AdjacentMap getAdjacent(const Vertex& v) const override {
        if (!hasVertex(v)) {
            return AdjacentMap(); // 顶点不存在，返回空
        }
        return adjList_.at(v);
    }
 
    // 深度优先遍历（递归实现）
    void dfs(const Vertex& start, const std::function<void(const Vertex&)>& visit) const override {
        if (!hasVertex(start)) {
            throw std::invalid_argument("Start vertex does not exist");
        }
        std::unordered_set<Vertex> visited; // 记录已访问顶点
        dfsRecursive(start, visit, visited);
    }
 
    // 广度优先遍历（队列实现）
    void bfs(const Vertex& start, const std::function<void(const Vertex&)>& visit) const override {
        if (!hasVertex(start)) {
            throw std::invalid_argument("Start vertex does not exist");
        }
        std::unordered_set<Vertex> visited;
        std::queue<Vertex> q;
 
        q.push(start);
        visited.insert(start);
 
        while (!q.empty()) {
            Vertex current = q.front();
            q.pop();
            visit(current); // 访问当前顶点
 
            // 遍历所有邻接顶点，未访问则入队
            for (const auto& [neighbor, _] : adjList_.at(current)) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }
 
private:
    std::unordered_map<Vertex, AdjacentMap> adjList_; // 邻接表：顶点→{邻接顶点→权重}
    size_t edgeCount_ = 0; // 边总数（缓存，避免每次计算）
 
    // DFS递归辅助函数
    void dfsRecursive(const Vertex& current, const std::function<void(const Vertex&)>& visit, 
                     std::unordered_set<Vertex>& visited) const {
        visit(current); // 访问当前顶点
        visited.insert(current);
 
        // 递归访问所有未访问的邻接顶点
        for (const auto& [neighbor, _] : adjList_.at(current)) {
            if (!visited.count(neighbor)) {
                dfsRecursive(neighbor, visit, visited);
            }
        }
    }
};
 
 
// --------------------------- 邻接表实现：无向图（继承有向图，重写边操作） ---------------------------
template <typename VertexType, typename WeightType = int>
class UndirectedGraph : public DirectedGraph<VertexType, WeightType> {
public:
    using Vertex = typename DirectedGraph<VertexType, WeightType>::Vertex;
    using Weight = typename DirectedGraph<VertexType, WeightType>::Weight;
 
    // 无向图添加边：同时添加u→v和v→u（权重相同）
    bool addEdge(const Vertex& u, const Vertex& v, const Weight& w = Weight()) override {
        if (u == v) {
            throw std::invalid_argument("Undirected graph does not support self-loops");
        }
        // 先检查边是否已存在（u→v或v→u存在即视为已存在）
        if (this->hasEdge(u, v)) {
            return false;
        }
        // 调用父类方法添加双向边（注意边数：父类会+1，这里需手动+1）
        DirectedGraph<VertexType, WeightType>::addEdge(u, v, w);
        DirectedGraph<VertexType, WeightType>::addEdge(v, u, w);
        return true;
    }
 
    // 无向图删除边：同时删除u→v和v→u
    bool removeEdge(const Vertex& u, const Vertex& v) override {
        bool removed1 = DirectedGraph<VertexType, WeightType>::removeEdge(u, v);
        bool removed2 = DirectedGraph<VertexType, WeightType>::removeEdge(v, u);
        return removed1 || removed2; // 至少删除一条即成功
    }
};
 
 
// --------------------------- 使用示例 ---------------------------
int main() {
    // 示例1：有向图测试（顶点为字符串，权重为int）
    std::cout << "=== 有向图测试 ===" << std::endl;
    DirectedGraph<std::string, int> digraph;
 
    // 添加顶点
    digraph.addVertex("A");
    digraph.addVertex("B");
    digraph.addVertex("C");
    digraph.addVertex("D");
    std::cout << "顶点数：" << digraph.vertexCount() << "（预期：4）" << std::endl;
 
    // 添加边
    digraph.addEdge("A", "B", 2);
    digraph.addEdge("A", "C", 5);
    digraph.addEdge("B", "C", 1);
    digraph.addEdge("C", "D", 3);
    std::cout << "边数：" << digraph.edgeCount() << "（预期：4）" << std::endl;
 
    // 测试邻接关系
    auto adjA = digraph.getAdjacent("A");
    std::cout << "A的邻接顶点：";
    for (const auto& [v, w] : adjA) {
        std::cout << v << "(" << w << ") "; // 预期：B(2) C(5)
    }
    std::cout << std::endl;
 
    // DFS遍历（从A开始）
    std::cout << "DFS遍历（A开始）：";
    digraph.dfs("A", [](const std::string& v) { std::cout << v << " "; }); 
    // 可能结果：A B C D （取决于哈希表存储顺序，只要是深度优先即可）
    std::cout << std::endl;
 
    // BFS遍历（从A开始）
    std::cout << "BFS遍历（A开始）：";
    digraph.bfs("A", [](const std::string& v) { std::cout << v << " "; }); 
    // 可能结果：A B C D （层次遍历：A→B、C→D）
    std::cout << std::endl;
 
 
    // 示例2：无向图测试（顶点为int，权重为double）
    std::cout << "
=== 无向图测试 ===" << std::endl;
    UndirectedGraph<int, double> undigraph;
 
    // 添加顶点
    undigraph.addVertex(1);
    undigraph.addVertex(2);
    undigraph.addVertex(3);
    undigraph.addVertex(4);
    std::cout << "顶点数：" << undigraph.vertexCount() << "（预期：4）" << std::endl;
 
    // 添加边
    undigraph.addEdge(1, 2, 1.5);
    undigraph.addEdge(1, 3, 2.0);
    undigraph.addEdge(2, 4, 3.2);
    std::cout << "边数：" << undigraph.edgeCount() << "（预期：3）" << std::endl;
 
    // 测试边的双向性
    std::cout << "是否有边2→1：" << (undigraph.hasEdge(2, 1) ? "是" : "否") << "（预期：是）" << std::endl;
    std::cout << "边2→1的权重：" << undigraph.getEdgeWeight(2, 1) << "（预期：1.5）" << std::endl;
 
    // BFS遍历（从1开始）
    std::cout << "BFS遍历（1开始）：";
    undigraph.bfs(1, [](int v) { std::cout << v << " "; }); 
    // 可能结果：1 2 3 4 （层次：1→2、3→4）
    std::cout << std::endl;
 
    // 删除顶点2（同时删除关联的边1-2、2-4）
    undigraph.removeVertex(2);
    std::cout << "删除顶点2后，边数：" << undigraph.edgeCount() << "（预期：1）" << std::endl;
    std::cout << "是否有边1→2：" << (undigraph.hasEdge(1, 2) ? "是" : "否") << "（预期：否）" << std::endl;
 
    return 0;
}

图的存储结构

一、邻接表（Adjacency List）

1. 结构原理

核心思想：为每个顶点建立一个链表（或哈希表），存储其所有邻接顶点及边的信息（如权重）。组成： 顶点表：存储所有顶点（可通过数组或哈希表实现）。边表：每个顶点对应的链表，记录 “从该顶点出发的边”（终点 + 权重）。

2. 示例（无向图 vs 有向图）

无向图：边 (u, v) 会同时出现在 u 的边表和 v 的边表中（双向存储）。有向图：边 <u,v> 仅出现在 u 的边表中（单向存储）。

// 示意图（顶点为int，权重为int）
无向图：顶点1连接2（权3）、3（权5）
顶点表：[1, 2, 3]
1的边表：→ (2,3) → (3,5)
2的边表：→ (1,3)
3的边表：→ (1,5)
 
有向图：顶点1指向2（权3）、3（权5）
1的边表：→ (2,3) → (3,5)
2的边表：（空）
3的边表：（空）

3. 实现（C++ 简化版）

// 邻接表节点（存储邻接顶点和权重）
template <typename V, typename W>
struct EdgeNode {
    V to;       // 邻接顶点
    W weight;   // 权重
    EdgeNode* next;  // 下一个邻接顶点
    EdgeNode(V t, W w) : to(t), weight(w), next(nullptr) {}
};
 
// 邻接表存储结构
template <typename V, typename W>
struct AdjacencyList {
    std::unordered_map<V, EdgeNode<V, W>*> vertices;  // 顶点→边表头指针
};

4. 优缺点

优点： 空间效率高：存储稀疏图时，空间复杂度为 O(V+E)" role="presentation">O(V+E)$O(V+E)$（V 顶点数，E 边数）。遍历邻接顶点快：访问某顶点的所有邻接顶点仅需遍历其边表（O(k)" role="presentation">O(k)$O(k)$，k 为邻接顶点数）。 缺点： 判断两顶点是否有边：需遍历其中一个顶点的边表（O(k)" role="presentation">O(k)$O(k)$，效率低于邻接矩阵）。无向图中边需存储两次，略有冗余。

5. 适用场景：稀疏图（边数少，如社交网络、路由拓扑）。

二、邻接矩阵（Adjacency Matrix）

1. 结构原理

核心思想：用 V&#x00D7;V" role="presentation">V×V$V\times V$ 的二维数组（矩阵）表示图， matrix[i][j] 表示顶点 i 与 j 的关系。值定义： 无权图： matrix[i][j] = 1 表示有边， 0 表示无边。加权图： matrix[i][j] = 权重值（无边时用特殊值如 &#x221E;" role="presentation">∞$\mathrm{\infty }$ 表示）。自环： matrix[i][i] 表示顶点 i 的自环。

2. 示例（无向图 vs 有向图）

无向图：矩阵对称（ matrix[i][j] = matrix[j][i]）。有向图：矩阵不对称（ matrix[i][j] 与  matrix[j][i] 独立）。

// 示例：3个顶点的图（顶点0,1,2）
无向加权图（边0-1权2，1-2权3）：
[
 [0, 2, ∞],
 [2, 0, 3],
 [∞, 3, 0]
]
 
有向加权图（边0→1权2，1→2权3）：
[
 [0, 2, ∞],
 [∞, 0, 3],
 [∞, ∞, 0]
]

3. 实现（C++ 简化版）

template <typename W>
struct AdjacencyMatrix {
    int vertexCount;               // 顶点数
    std::vector<std::vector<W>> matrix;  // 邻接矩阵
 
    // 初始化：顶点数n，无边时默认为INF
    AdjacencyMatrix(int n, W INF = W()) : vertexCount(n), matrix(n, std::vector<W>(n, INF)) {
        for (int i = 0; i < n; ++i) {
            matrix[i][i] = 0;  // 顶点到自身距离为0（无自环时）
        }
    }
};

4. 优缺点

优点： 操作简单：判断两顶点是否有边（O(1)" role="presentation">O(1)$O(1)$），添加 / 删除边（O(1)" role="presentation">O(1)$O(1)$）。适合稠密图：当 E&#x2248;V2" role="presentation">E≈V2$E\approx V^2$ 时，空间效率接近邻接表。 缺点： 空间复杂度高：O(V2)" role="presentation">O(V2)$O(V^2)$（即使边很少，也需存储整个矩阵）。遍历邻接顶点慢：需扫描一行（O(V)" role="presentation">O(V)$O(V)$），效率低于邻接表。

5. 适用场景：稠密图（边数多，如完全图、电路连接图）。

三、十字链表（Orthogonal List）

1. 结构原理

核心思想：专为有向图设计，解决邻接表中 “查找入边” 效率低的问题。组成： 顶点节点：存储顶点信息，含两个指针： firstOut：指向该顶点的第一条出边（从该顶点出发的边）。 firstIn：指向该顶点的第一条入边（指向该顶点的边）。 边节点：存储一条有向边 &#x27E8;u,v&#x27E9;" role="presentation">⟨u,v⟩$⟨u,v⟩$，含 4 个域： from：起点 u 的索引； to：终点 v 的索引。 weight：权重。 nextOut：指向 u 的下一条出边； nextIn：指向 v 的下一条入边。

2. 示意图

顶点节点：[data, firstOut, firstIn]
边节点：[from, to, weight, nextOut, nextIn]
 
例：有向边0→1、0→2、1→2
- 顶点0的firstOut → 边0→1，边0→1的nextOut → 边0→2
- 顶点1的firstOut → 边1→2
- 顶点2的firstIn → 边0→2，边0→2的nextIn → 边1→2

3. 优缺点

优点： 兼顾出边和入边的高效访问：查询某顶点的所有出边 / 入边均为 O(k)" role="presentation">O(k)$O(k)$（k 为边数）。适合频繁需要 “入边操作” 的有向图（如拓扑排序、关键路径分析）。 缺点： 结构复杂，实现难度高。空间开销略大于邻接表。

4. 适用场景：有向图，且需频繁处理入边（如任务调度图）。

四、邻接多重表（Adjacency Multilist）

1. 结构原理

核心思想：专为无向图设计，解决邻接表中 “删除边需操作两个节点” 的问题（无向图每条边在邻接表中存两次）。组成： 顶点节点：存储顶点信息， firstEdge 指向该顶点的第一条边。边节点：每条边仅用一个节点表示，含 5 个域： mark：标记（如是否被访问）。 vertex1/ vertex2：边的两个顶点。 next1：指向与  vertex1 相关的下一条边。 next2：指向与  vertex2 相关的下一条边。

2. 示意图

边节点：[mark, vertex1, vertex2, next1, next2]
 
例：无向边(0-1)、(0-2)、(1-2)
- 边(0-1)的next1 → 边(0-2)（0的下一条边）
- 边(0-1)的next2 → 边(1-2)（1的下一条边）
- 边(0-2)的next2 → 边(1-2)（2的下一条边）

3. 优缺点

优点： 边的操作统一：删除一条边只需操作一个边节点（无需像邻接表那样删除两次）。适合需频繁删除边的无向图（如网络拓扑动态变化场景）。 缺点： 结构较复杂，实现难度高于邻接表。

4. 适用场景：无向图，且需频繁增删边（如交通网络实时路况更新）。

总结：存储结构的选择

存储结构	空间复杂度	适合图类型	核心优势	典型应用场景
邻接表	O(V+E)	稀疏图（有 / 无向）	空间高效，遍历邻接顶点快	社交网络、路由表
邻接矩阵	O()	稠密图（有 / 无向）	判断边存在性快，实现简单	电路连接图、完全图
十字链表	O(V+E)	有向图	兼顾出边和入边的高效访问	任务调度、拓扑排序
邻接多重表	O(V+E)	无向图	边操作统一，适合频繁增删边	交通网络、动态拓扑图

实际开发中，邻接表是最常用的存储结构（平衡了空间和效率），而邻接矩阵在稠密图或需快速判断边存在性的场景中更优。

图的遍历

图的遍历是指从图中某一顶点出发，按照某种规则访问图中所有可达顶点，且每个顶点仅被访问一次的过程。由于图可能存在环或非连通结构，遍历的核心是记录已访问顶点，避免重复访问。常见的遍历算法有两种：深度优先搜索（DFS） 和广度优先搜索（BFS）。

一、遍历的核心问题

避免重复访问：通过 “已访问” 标记（如数组、哈希表）记录访问过的顶点。处理非连通图：若图不连通，需对所有未访问的顶点分别启动遍历，才能覆盖全部顶点。

二、深度优先搜索（DFS）

1. 核心思想

“一条路走到黑”：从起点出发，优先沿着一条路径深入访问，直到无法继续（所有邻接顶点均已访问），再回溯到上一顶点，选择未访问的邻接顶点继续深入。

2. 实现步骤（以邻接表为例）

递归版：

访问当前顶点，标记为 “已访问”。对当前顶点的每个未访问的邻接顶点，递归执行 DFS。

非递归版（栈模拟）：

初始化栈，将起点压入栈，标记为 “已访问”。弹出栈顶顶点，访问该顶点。将该顶点的所有未访问的邻接顶点压入栈（顺序不影响正确性，但可能改变访问顺序），并标记为 “已访问”。重复步骤 2-3，直到栈为空。

3. 示例（无向图）

假设有无向图如下（顶点 A 连接 B、C；B 连接 A、D；C 连接 A、D；D 连接 B、C）：

    A
   / 
  B   C
    /
    D

DFS 起点为 A的访问顺序（可能结果）：A → B → D → C（递归深入 B 的路径，到 D 后回溯，再访问 C）。

4. 代码实现（邻接表 + 递归）

// 图的邻接表存储：unordered_map<顶点, 邻接顶点列表>
using Graph = std::unordered_map<char, std::vector<char>>;
 
// 递归DFS
void dfs(const Graph& graph, char start, std::unordered_set<char>& visited) {
    // 访问当前顶点
    std::cout << start << " ";
    visited.insert(start);
 
    // 遍历所有邻接顶点
    for (char neighbor : graph.at(start)) {
        if (!visited.count(neighbor)) { // 未访问则递归
            dfs(graph, neighbor, visited);
        }
    }
}
 
// 处理非连通图：对所有未访问顶点执行DFS
void dfsAll(const Graph& graph) {
    std::unordered_set<char> visited;
    for (const auto& [vertex, _] : graph) {
        if (!visited.count(vertex)) {
            dfs(graph, vertex, visited);
        }
    }
}

三、广度优先搜索（BFS）

1. 核心思想

“层层扩散”：从起点出发，先访问起点的所有直接邻接顶点（第一层），再访问这些邻接顶点的未访问邻接顶点（第二层），以此类推，按层次顺序访问。

2. 实现步骤（以邻接表为例）

初始化队列，将起点入队，标记为 “已访问”。队首顶点出队，访问该顶点。将该顶点的所有未访问的邻接顶点入队，并标记为 “已访问”。重复步骤 2-3，直到队列为空。

3. 示例（同上述无向图）

BFS 起点为 A的访问顺序（唯一结果，因层次固定）：A → B → C → D（先访问 A 的直接邻接 B、C，再访问 B 和 C 的邻接 D）。

4. 代码实现（邻接表 + 队列）

// 队列BFS
void bfs(const Graph& graph, char start, std::unordered_set<char>& visited) {
    std::queue<char> q;
    q.push(start);
    visited.insert(start);
 
    while (!q.empty()) {
        char current = q.front();
        q.pop();
        // 访问当前顶点
        std::cout << current << " ";
 
        // 邻接顶点入队
        for (char neighbor : graph.at(current)) {
            if (!visited.count(neighbor)) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}
 
// 处理非连通图：对所有未访问顶点执行BFS
void bfsAll(const Graph& graph) {
    std::unordered_set<char> visited;
    for (const auto& [vertex, _] : graph) {
        if (!visited.count(vertex)) {
            bfs(graph, vertex, visited);
        }
    }
}

四、DFS 与 BFS 的对比

维度	深度优先搜索（DFS）	广度优先搜索（BFS）
数据结构	栈（递归本质是调用栈）	队列
访问顺序	深度优先（可能跳跃层次）	层次优先（按距离起点的远近顺序）
空间复杂度	最坏 O (V)（递归栈 / 栈存储顶点）	最坏 O (V)（队列存储顶点）
时间复杂度	O (V + E)（V 顶点数，E 边数）	O(V + E)
适用场景	拓扑排序、连通分量、路径探索	最短路径（无权图）、层次遍历
特点	可能不找最短路径，但内存占用较稳	能找到最短路径（无权图）

五、关键注意事项

有向图遍历：邻接顶点仅包含 “出边指向的顶点”，逻辑与无向图一致，但可达顶点范围可能更小。非连通图：必须遍历所有连通分量（通过 dfsAll/ bfsAll），否则会遗漏顶点。存储结构影响：邻接表遍历邻接顶点效率为 O (k)（k 为邻接顶点数），邻接矩阵为 O (V)（需扫描整行），但不影响整体 O (V+E) 复杂度。

图的应用

最小生成树

一、Kruskal 算法实现（基于并查集）

Kruskal 算法的核心是 “排序边 + 并查集避环”，适合稀疏图。

#include <iostream>
#include <vector>
#include <algorithm>  // 用于排序
using namespace std;
 
// 并查集（Union-Find）数据结构：用于检测环
struct UnionFind {
    vector<int> parent;  // 父节点数组
    vector<int> rank;    // 秩（用于优化合并）
 
    // 初始化：每个节点的父节点是自己，秩为1
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
 
    // 查找根节点（路径压缩优化）
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // 递归压缩路径
        }
        return parent[x];
    }
 
    // 合并两个集合（按秩合并优化）
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;  // 已在同一集合（有环）
        }
        // 秩小的树合并到秩大的树
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
        return true;
    }
};
 
// Kruskal算法：返回MST的总权重和选中的边
pair<int, vector<vector<int>>> kruskal(int n, vector<vector<int>>& edges) {
    // 1. 按边的权重从小到大排序
    sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];  // a[2]和b[2]是权重
    });
 
    UnionFind uf(n);
    vector<vector<int>> mstEdges;  // 存储MST的边
    int totalWeight = 0;
 
    // 2. 遍历排序后的边，选不形成环的边
    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int w = edge[2];
        if (uf.unite(u, v)) {  // 若u和v不在同一集合（无环）
            mstEdges.push_back(edge);
            totalWeight += w;
            if (mstEdges.size() == n - 1) {  // 选够n-1条边（覆盖所有顶点）
                break;
            }
        }
    }
 
    // 检查是否形成MST（适用于连通图，非连通图会失败）
    if (mstEdges.size() != n - 1) {
        return {-1, {}};  // 图不连通，无MST
    }
    return {totalWeight, mstEdges};
}

二、Prim 算法实现（基于优先队列）

Prim 算法的核心是 “从起点逐步扩展，用优先队列选最小边”，适合稠密图。

#include <queue>  // 优先队列（最小堆）
#include <unordered_map>
using namespace std;
 
// Prim算法：返回MST的总权重和选中的边（邻接表存储图）
pair<int, vector<vector<int>>> prim(int n, const vector<vector<pair<int, int>>>& adj) {
    // adj: 邻接表，adj[u] = [(v1, w1), (v2, w2)...] 表示u到v的边权重为w
    vector<bool> inMST(n, false);  // 标记顶点是否已加入MST
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> pq;
    // 优先队列存储：(权重, (u, v))，小根堆（权重最小的先出）
 
    // 1. 从顶点0开始（可任选起点）
    pq.push({0, {-1, 0}});  // (-1表示无父节点，0是起点，权重0)
    int totalWeight = 0;
    vector<vector<int>> mstEdges;
 
    while (!pq.empty() && mstEdges.size() < n - 1) {
        auto [w, uv] = pq.top();
        pq.pop();
        int u = uv.first;   // 已在MST中的顶点
        int v = uv.second;  // 待加入的顶点
 
        if (inMST[v]) {
            continue;  // v已在MST中，跳过
        }
 
        // 2. 将v加入MST，记录边
        inMST[v] = true;
        totalWeight += w;
        if (u != -1) {  // 跳过起点的虚拟边
            mstEdges.push_back({u, v, w});
        }
 
        // 3. 将v的所有邻接边加入队列（只考虑未加入MST的顶点）
        for (auto& [neighbor, weight] : adj[v]) {
            if (!inMST[neighbor]) {
                pq.push({weight, {v, neighbor}});
            }
        }
    }
 
    // 检查是否形成MST
    if (mstEdges.size() != n - 1) {
        return {-1, {}};  // 图不连通
    }
    return {totalWeight, mstEdges};
}

三、测试用例与运行结果

int main() {
    // 测试图：4个顶点（0-3），边为：
    // 0-1(2), 0-2(3), 1-2(1), 1-3(4), 2-3(5)
    int n = 4;  // 顶点数
 
    // ------------- Kruskal测试 -------------
    vector<vector<int>> edges = {
        {0, 1, 2},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 4},
        {2, 3, 5}
    };
    auto [kruskalWeight, kruskalEdges] = kruskal(n, edges);
    cout << "Kruskal算法结果：" << endl;
    cout << "MST总权重：" << kruskalWeight << endl;  // 预期：1+2+4=7
    cout << "选中的边：";
    for (auto& e : kruskalEdges) {
        cout << "(" << e[0] << "-" << e[1] << ", " << e[2] << ") ";
    }
    cout << endl;  // 预期：(1-2,1) (0-1,2) (1-3,4)
 
 
    // ------------- Prim测试 -------------
    // 邻接表表示图：adj[u]存储(u的邻接顶点, 权重)
    vector<vector<pair<int, int>>> adj(n);
    adj[0].emplace_back(1, 2);
    adj[0].emplace_back(2, 3);
    adj[1].emplace_back(0, 2);
    adj[1].emplace_back(2, 1);
    adj[1].emplace_back(3, 4);
    adj[2].emplace_back(0, 3);
    adj[2].emplace_back(1, 1);
    adj[2].emplace_back(3, 5);
    adj[3].emplace_back(1, 4);
    adj[3].emplace_back(2, 5);
 
    auto [primWeight, primEdges] = prim(n, adj);
    cout << "
Prim算法结果：" << endl;
    cout << "MST总权重：" << primWeight << endl;  // 预期：7
    cout << "选中的边：";
    for (auto& e : primEdges) {
        cout << "(" << e[0] << "-" << e[1] << ", " << e[2] << ") ";
    }
    cout << endl;  // 预期：(1-2,1) (0-1,2) (1-3,4)（或顺序略有不同）
 
    return 0;
}

最短路径

一、Dijkstra 算法（单源最短路径，非负权重）

适用场景：从一个起点到其他所有顶点的最短路径，边权重为非负数（如交通网络中距离、时间均为非负）。核心思想：贪心策略，每次从 “未确定最短路径的顶点” 中选择距离起点最近的顶点，并用它更新其他顶点的距离。

算法步骤

初始化：起点距离为 0，其他顶点距离为∞；用优先队列（最小堆）存储 “顶点 - 当前距离”，优先弹出距离最小的顶点。迭代： 弹出距离最小的顶点 u，若 u已处理过则跳过（避免重复计算）。对 u的每个邻接顶点 v，若通过 u到达 v的距离（ dist[u] + 权重）小于当前 dist[v]，则更新 dist[v]，并将 v加入优先队列。 终止：优先队列为空时，所有顶点的最短距离已确定。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>  // 用于INT_MAX
using namespace std;
 
// Dijkstra算法：返回从start到所有顶点的最短距离
vector<int> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int start) {
    // adj: 邻接表，adj[u] = [(v, w)] 表示u→v的边权重为w
    vector<int> dist(n, INT_MAX);  // 存储起点到各顶点的最短距离
    dist[start] = 0;  // 起点到自身距离为0
 
    // 优先队列：(距离, 顶点)，小根堆（距离最小的先出）
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
 
    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();
 
        // 若当前距离大于已知最短距离，说明已处理过，跳过
        if (currentDist > dist[u]) {
            continue;
        }
 
        // 遍历u的所有邻接顶点，更新距离
        for (auto [v, w] : adj[u]) {
            if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {  // 避免溢出
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});  // 加入队列，可能有重复条目，但不影响结果
            }
        }
    }
 
    return dist;
}

二、Floyd-Warshall 算法（多源最短路径）

适用场景：求所有顶点对之间的最短路径（如规划多个景点之间的最优路线）。核心思想：动态规划，通过中间顶点逐步优化任意两点的最短路径，即 “从 i到 j的最短路径是否经过 k”。

算法步骤：

初始化：用邻接矩阵 dist存储距离， dist[i][j]为 i到 j的直接边权重（无直接边则为∞， dist[i][i] = 0）。迭代：对每个中间顶点 k（0 到 n-1），更新所有 i和 j的距离： dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])终止：所有 k处理完毕后， dist[i][j]即为 i到 j的最短路径。

#include <vector>
#include <climits>
using namespace std;
 
// Floyd-Warshall算法：返回所有顶点对的最短距离矩阵
vector<vector<int>> floydWarshall(int n, const vector<vector<int>>& graph) {
    // graph: 邻接矩阵，graph[i][j]为i→j的直接权重（∞表示无直接边）
    vector<vector<int>> dist = graph;  // 初始化距离矩阵
 
    // 中间顶点k
    for (int k = 0; k < n; ++k) {
        // 起点i
        for (int i = 0; i < n; ++i) {
            // 终点j
            for (int j = 0; j < n; ++j) {
                // 若i→k和k→j可达，且经过k的路径更短，则更新
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX 
                    && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
 
    return dist;
}

三、Bellman-Ford 算法（单源最短路径，支持负权重）

适用场景：单源最短路径，边权重可负（如金融交易中的盈亏），且能检测负环（若存在负环，最短路径无意义，因可无限绕环减小距离）。核心思想：松弛操作，对所有边重复 n-1次松弛（ n为顶点数），最后再检查一次是否仍能松弛（若能，则存在负环）。

算法步骤：

初始化：起点距离为 0，其他顶点距离为∞。松弛迭代：重复 n-1次，对每条边 (u, v, w)，若 dist[v] > dist[u] + w，则更新 dist[v]。负环检测：对所有边再做一次松弛，若仍能更新，则存在从起点可达的负环。

#include <vector>
#include <climits>
using namespace std;
 
// Bellman-Ford算法：返回起点到各顶点的最短距离，若存在负环则返回空
vector<int> bellmanFord(int n, const vector<vector<int>>& edges, int start) {
    // edges: 边列表，每条边为[u, v, w]（u→v，权重w）
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
 
    // 松弛n-1次（最多n-1条边组成最短路径）
    for (int i = 0; i < n - 1; ++i) {
        bool updated = false;  // 优化：若未更新，提前退出
        for (auto& e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;
    }
 
    // 检测负环：若还能松弛，说明存在负环
    for (auto& e : edges) {
        int u = e[0], v = e[1], w = e[2];
        if (dist[u] != INT_MAX && dist[v] > dist[u] + w) {
            return {};  // 存在负环，返回空
        }
    }
 
    return dist;
}

四、测试用例与运行结果

int main() {
    // 测试图：4个顶点（0-3），边为：
    // 0→1(4), 0→2(1), 1→3(1), 2→1(2), 2→3(5)
    int n = 4;
    int start = 0;
 
    // ------------- Dijkstra测试 -------------
    vector<vector<pair<int, int>>> adj(n);
    adj[0].emplace_back(1, 4);
    adj[0].emplace_back(2, 1);
    adj[1].emplace_back(3, 1);
    adj[2].emplace_back(1, 2);
    adj[2].emplace_back(3, 5);
 
    vector<int> dijkstraDist = dijkstra(n, adj, start);
    cout << "Dijkstra算法（起点" << start << "）：" << endl;
    for (int i = 0; i < n; ++i) {
        if (dijkstraDist[i] == INT_MAX) {
            cout << "到" << i << "的距离：不可达" << endl;
        } else {
            cout << "到" << i << "的距离：" << dijkstraDist[i] << endl;
        }
    }
    // 预期结果：
    // 到0的距离：0
    // 到1的距离：3（0→2→1：1+2=3）
    // 到2的距离：1
    // 到3的距离：4（0→2→1→3：1+2+1=4）
 
 
    // ------------- Floyd-Warshall测试 -------------
    // 邻接矩阵初始化（INT_MAX表示不可达）
    vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < n; ++i) graph[i][i] = 0;
    graph[0][1] = 4; graph[0][2] = 1;
    graph[1][3] = 1;
    graph[2][1] = 2; graph[2][3] = 5;
 
    vector<vector<int>> floydDist = floydWarshall(n, graph);
    cout << "
Floyd-Warshall算法（所有顶点对）：" << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (floydDist[i][j] == INT_MAX) {
                cout << "[" << i << "→" << j << "]: 不可达 ";
            } else {
                cout << "[" << i << "→" << j << "]:" << floydDist[i][j] << " ";
            }
        }
        cout << endl;
    }
    // 预期结果（部分）：
    // [0→1]:3 [0→3]:4；[2→3]:3（2→1→3：2+1=3）
 
 
    // ------------- Bellman-Ford测试（含负权重） -------------
    // 边列表：加入一条负权重边1→2(-1)，无负环
    vector<vector<int>> edges = {
        {0,1,4}, {0,2,1}, {1,3,1}, {2,1,2}, {2,3,5}, {1,2,-1}
    };
    vector<int> bellmanDist = bellmanFord(n, edges, start);
    cout << "
Bellman-Ford算法（含负权重，无负环）：" << endl;
    if (bellmanDist.empty()) {
        cout << "存在负环！" << endl;
    } else {
        for (int i = 0; i < n; ++i) {
            if (bellmanDist[i] == INT_MAX) {
                cout << "到" << i << "的距离：不可达" << endl;
            } else {
                cout << "到" << i << "的距离：" << bellmanDist[i] << endl;
            }
        }
    }
    // 预期结果：到1的距离为2（0→2→1→2→1：1+2-1+2=4？不，正确路径0→2→1：1+2=3，因1→2(-1)后2→1(2)会形成环，但松弛n-1次后稳定）
 
 
    // 测试负环：添加边3→1(-5)，形成1→3→1的环（1→3(1)，3→1(-5)，总权重-4 <0）
    edges.push_back({3,1,-5});
    vector<int> bellmanWithCycle = bellmanFord(n, edges, start);
    cout << "
Bellman-Ford算法（含负环）：" << endl;
    if (bellmanWithCycle.empty()) {
        cout << "存在负环！" << endl;  // 预期输出
    }
 
    return 0;
}

拓扑排序

一、核心概念与适用条件

定义：对于有向无环图（DAG），拓扑排序是顶点的一个线性排列，满足：若图中存在边 u&#x2192;v" role="presentation">u→v$u\to v$，则 u 在排列中一定位于 v 之前。适用条件：必须是有向无环图（DAG）。若图中存在环（如 u&#x2192;v&#x2192;w&#x2192;u" role="presentation">u→v→w→u$u\to v\to w\to u$），则不存在拓扑排序（环中顶点互相依赖，无法确定先后顺序）。

二、经典算法：Kahn 算法（基于入度与队列）

算法思路

入度（In-degree）：顶点的入度是指向该顶点的边的数量（即 “前置依赖” 的数量）。核心步骤： 初始时，将所有入度为 0的顶点（无前置依赖）加入队列。每次从队列中取出一个顶点 u，将其加入拓扑序列。对 u 的所有邻接顶点 v，将其入度减 1（表示 “依赖 u 已完成”）。若 v 的入度变为 0，则加入队列。重复上述步骤，直到队列为空。若拓扑序列的长度等于顶点总数，则排序成功（图为 DAG）；否则，图中存在环，排序失败。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
 
// 拓扑排序（Kahn算法）：返回拓扑序列，若有环则返回空
vector<int> topologicalSort(int n, const vector<vector<int>>& adj) {
    // adj: 邻接表，adj[u]存储u的所有邻接顶点（u→v）
    vector<int> inDegree(n, 0);  // 记录每个顶点的入度
    queue<int> q;                // 存储入度为0的顶点
    vector<int> result;          // 拓扑序列
 
    // 1. 计算所有顶点的入度
    for (int u = 0; u < n; ++u) {
        for (int v : adj[u]) {
            inDegree[v]++;
        }
    }
 
    // 2. 初始化队列：入度为0的顶点入队
    for (int u = 0; u < n; ++u) {
        if (inDegree[u] == 0) {
            q.push(u);
        }
    }
 
    // 3. 处理队列中的顶点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);  // 加入拓扑序列
 
        // 遍历u的邻接顶点，入度减1
        for (int v : adj[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {  // 入度为0时入队
                q.push(v);
            }
        }
    }
 
    // 4. 检测是否有环（若序列长度不等于顶点数，则有环）
    if (result.size() != n) {
        return {};  // 有环，返回空
    }
    return result;
}

三、另一种实现：基于 DFS 的拓扑排序

算法思路

利用深度优先搜索（DFS）的递归特性，在访问完顶点的所有邻接顶点后，将该顶点加入结果列表，最后反转列表得到拓扑序列。

需通过 “访问状态” 检测环： 0：未访问；1：正在访问（递归栈中）；2：已访问。若在 DFS 中遇到状态为 1 的顶点，说明存在环（递归栈中形成回路）。

#include <vector>
#include <algorithm>  // 用于reverse
using namespace std;
 
// DFS辅助函数：返回是否有环，并用result存储逆拓扑序列
bool dfs(int u, const vector<vector<int>>& adj, vector<int>& state, vector<int>& result) {
    state[u] = 1;  // 标记为正在访问（递归栈中）
    for (int v : adj[u]) {
        if (state[v] == 1) {
            return true;  // 遇到正在访问的顶点，有环
        } else if (state[v] == 0) {
            if (dfs(v, adj, state, result)) {  // 递归访问v，若有环则返回true
                return true;
            }
        }
    }
    state[u] = 2;  // 标记为已访问
    result.push_back(u);  // 所有邻接顶点访问完后，加入结果
    return false;
}
 
// 基于DFS的拓扑排序：返回拓扑序列，若有环则返回空
vector<int> topologicalSortDFS(int n, const vector<vector<int>>& adj) {
    vector<int> state(n, 0);  // 0:未访问，1:正在访问，2:已访问
    vector<int> result;       // 存储逆拓扑序列（需反转）
 
    // 遍历所有未访问的顶点（处理非连通图）
    for (int u = 0; u < n; ++u) {
        if (state[u] == 0) {
            if (dfs(u, adj, state, result)) {  // 若有环，返回空
                return {};
            }
        }
    }
 
    reverse(result.begin(), result.end());  // 反转得到拓扑序列
    return result;
}

四、测试用例与运行结果

int main() {
    // 测试图1：DAG（课程依赖）
    // 顶点0-4表示课程，边表示依赖：0→1，0→2，1→3，2→3，3→4
    int n1 = 5;
    vector<vector<int>> adj1 = {
        {1, 2},   // 0→1, 0→2
        {3},      // 1→3
        {3},      // 2→3
        {4},      // 3→4
        {}        // 4无出边
    };
 
    // Kahn算法测试
    vector<int> kahnResult = topologicalSort(n1, adj1);
    cout << "Kahn算法（DAG）拓扑序列：";
    for (int u : kahnResult) {
        cout << u << " ";  // 可能结果：0 1 2 3 4 或 0 2 1 3 4 等（合法即可）
    }
    cout << endl;
 
    // DFS算法测试
    vector<int> dfsResult = topologicalSortDFS(n1, adj1);
    cout << "DFS算法（DAG）拓扑序列：";
    for (int u : dfsResult) {
        cout << u << " ";  // 可能结果同上
    }
    cout << endl;
 
 
    // 测试图2：有环图（1→2→3→1）
    int n2 = 3;
    vector<vector<int>> adj2 = {
        {},        // 0无出边
        {2},       // 1→2
        {3},       // 2→3（注意：顶点3实际不存在，这里简化为n2=3，实际应为3→1形成环）
        {1}        // 修正：若n2=3，顶点编号0-2，则环为1→2→1：
        // 正确adj2应为：{ {}, {2}, {1} }
    };
    adj2 = { {}, {2}, {1} };  // 1→2→1，形成环
 
    vector<int> kahnCycle = topologicalSort(n2, adj2);
    cout << "
Kahn算法（有环图）：";
    if (kahnCycle.empty()) {
        cout << "存在环，无拓扑序列" << endl;  // 预期输出
    }
 
    vector<int> dfsCycle = topologicalSortDFS(n2, adj2);
    cout << "DFS算法（有环图）：";
    if (dfsCycle.empty()) {
        cout << "存在环，无拓扑序列" << endl;  // 预期输出
    }
 
    return 0;
}

关键路径

关键路径（Critical Path）是针对AOE 网（Activity On Edge Network，边表示活动的有向无环图） 的一种重要分析方法，用于确定项目的最短完成时间和影响工期的关键活动。

一、核心概念

AOE 网：一种有向无环图（DAG），其中：

顶点表示 “事件”（如 “任务 A 完成”“开始阶段结束”）。有向边表示 “活动”，边的权重表示活动的持续时间。存在唯一的源点（入度为 0 的起点，如 “项目开始”）和唯一的汇点（出度为 0 的终点，如 “项目结束”）。

关键路径：从源点到汇点的最长路径（路径上所有活动的持续时间之和最大）。这条路径的总权重即为项目的最短完成时间（任何活动都不延误时的最少时间）。

关键活动：关键路径上的活动，其特点是：

最早开始时间 = 最迟开始时间（若延误，会直接延长总工期）。

二、关键参数定义

为计算关键路径，需先确定 4 个参数：

事件的最早发生时间（ve [i]）：从源点到事件 i 的最长路径长度（事件 i 最早能发生的时间）。事件的最迟发生时间（vl [i]）：在不延误总工期的前提下，事件 i 最晚能发生的时间。活动的最早开始时间（e [k]）：活动 k（边 <u, v>）的最早开始时间，等于事件 u 的最早发生时间（ve [u]）。活动的最迟开始时间（l [k]）：活动 k（边 <u, v>）的最迟开始时间，等于事件 v 的最迟发生时间减去活动持续时间（vl [v] - weight (u, v)）。

关键活动判定：若 e [k] == l [k]，则活动 k 是关键活动。

三、算法步骤

拓扑排序：对 AOE 网进行拓扑排序，确保图是 DAG（若有环则无法计算）。计算事件最早发生时间（ve）： 源点 ve [源点] = 0。按拓扑序遍历事件，对每个事件 u，其邻接事件 v 的 ve [v] = max (ve [v], ve [u] + weight (u, v))。 计算事件最迟发生时间（vl）： 汇点 vl [汇点] = ve [汇点]（总工期等于汇点的最早发生时间）。按逆拓扑序遍历事件，对每个事件 v，其前驱事件 u 的 vl [u] = min (vl [u], vl [v] - weight (u, v))。 识别关键活动：对每条边 <u, v>（活动），计算 e = ve [u]，l = vl [v] - weight (u, v)，若 e == l，则为关键活动。提取关键路径：由关键活动组成的从源点到汇点的路径。

四、 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
using namespace std;
 
// AOE网边结构：<起点u, 终点v, 权重w>
struct Edge {
    int u, v, w;
    Edge(int u_, int v_, int w_) : u(u_), v(v_), w(w_) {}
};
 
// 关键路径算法：返回关键活动列表和总工期
pair<vector<Edge>, int> criticalPath(int n, const vector<Edge>& edges, int source, int sink) {
    // 1. 构建邻接表和逆邻接表（用于逆拓扑序）
    vector<vector<pair<int, int>>> adj(n);  // adj[u] = [(v, w)]
    vector<vector<pair<int, int>>> reverseAdj(n);  // reverseAdj[v] = [(u, w)]
    vector<int> inDegree(n, 0);  // 入度（用于拓扑排序）
 
    for (const auto& e : edges) {
        adj[e.u].emplace_back(e.v, e.w);
        reverseAdj[e.v].emplace_back(e.u, e.w);
        inDegree[e.v]++;
    }
 
    // 2. 拓扑排序（Kahn算法）
    vector<int> topoOrder;
    queue<int> q;
    vector<int> tempIn = inDegree;  // 临时入度（避免修改原数组）
 
    q.push(source);
    tempIn[source] = -1;  // 标记已入队
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);
 
        for (auto [v, w] : adj[u]) {
            tempIn[v]--;
            if (tempIn[v] == 0) {
                q.push(v);
                tempIn[v] = -1;
            }
        }
    }
 
    // 检查拓扑排序是否覆盖所有顶点（确保无环且连通）
    if (topoOrder.size() != n) {
        return {{}, -1};  // 有环或不连通，返回错误
    }
 
    // 3. 计算事件最早发生时间ve
    vector<int> ve(n, 0);
    for (int u : topoOrder) {
        for (auto [v, w] : adj[u]) {
            if (ve[v] < ve[u] + w) {  // 取最长路径
                ve[v] = ve[u] + w;
            }
        }
    }
 
    // 4. 计算事件最迟发生时间vl（按逆拓扑序）
    vector<int> vl(n, INT_MAX);
    vl[sink] = ve[sink];  // 汇点的最迟发生时间等于最早发生时间
 
    // 逆拓扑序遍历（反转拓扑序列）
    reverse(topoOrder.begin(), topoOrder.end());
    for (int v : topoOrder) {
        for (auto [u, w] : reverseAdj[v]) {  // 遍历v的前驱u
            if (vl[u] > vl[v] - w) {  // 取最小值
                vl[u] = vl[v] - w;
            }
        }
    }
 
    // 5. 识别关键活动（e == l）
    vector<Edge> criticalEdges;
    for (const auto& e : edges) {
        int u = e.u, v = e.v, w = e.w;
        int e_k = ve[u];  // 活动最早开始时间
        int l_k = vl[v] - w;  // 活动最迟开始时间
        if (e_k == l_k) {
            criticalEdges.push_back(e);
        }
    }
 
    return {criticalEdges, ve[sink]};  // 返回关键活动和总工期
}
 
// 辅助函数：从关键活动中提取关键路径（可能有多条，这里取一条）
vector<int> getCriticalPath(int source, int sink, const vector<Edge>& criticalEdges) {
    // 构建关键活动的邻接表
    vector<vector<int>> adj(sink + 1);  // 假设顶点编号连续
    for (const auto& e : criticalEdges) {
        adj[e.u].push_back(e.v);
    }
 
    // DFS寻找从source到sink的路径（关键路径）
    vector<int> path;
    stack<pair<int, vector<int>>> st;
    st.push({source, {source}});
 
    while (!st.empty()) {
        auto [u, currPath] = st.top();
        st.pop();
 
        if (u == sink) {
            path = currPath;
            break;  // 找到一条即可
        }
 
        for (int v : adj[u]) {
            vector<int> newPath = currPath;
            newPath.push_back(v);
            st.push({v, newPath});
        }
    }
 
    return path;
}

五、测试用例与运行结果

int main() {
    // 测试AOE网：
    // 事件0（源点），1，2，3，4（汇点）
    // 活动：
    // 0→1（3），0→2（2），
    // 1→3（2），1→4（3），
    // 2→3（4），3→4（2）
    int n = 5;  // 顶点数（事件0-4）
    int source = 0;  // 源点
    int sink = 4;    // 汇点
 
    vector<Edge> edges = {
        Edge(0, 1, 3),
        Edge(0, 2, 2),
        Edge(1, 3, 2),
        Edge(1, 4, 3),
        Edge(2, 3, 4),
        Edge(3, 4, 2)
    };
 
    // 计算关键路径
    auto [criticalEdges, totalTime] = criticalPath(n, edges, source, sink);
    if (totalTime == -1) {
        cout << "AOE网有环或不连通，无法计算关键路径！" << endl;
        return 0;
    }
 
    // 输出结果
    cout << "项目最短完成时间：" << totalTime << endl;  // 预期：0→2→3→4：2+4+2=8
 
    cout << "关键活动：";
    for (const auto& e : criticalEdges) {
        cout << e.u << "→" << e.v << "（" << e.w << "） ";
        // 预期：0→2（2），2→3（4），3→4（2）
    }
    cout << endl;
 
    // 提取关键路径
    vector<int> criticalPath = getCriticalPath(source, sink, criticalEdges);
    cout << "关键路径：";
    for (int i = 0; i < criticalPath.size(); ++i) {
        if (i > 0) cout << "→";
        cout << criticalPath[i];
    }
    cout << endl;  // 预期：0→2→3→4
 
    return 0;
}