图

概念

节点和边

一幅图结构由若干节点 (Vertex) 和边 (Edge) 构成，其中：

每个节点有一个唯一 ID。
边可以是有向的（有向图，Directional Graph），也可以是无向的（无向图，Undirected Graph）。
边上可以有权重（加权图，Weighted Graph），也可以没有权重（无权图，Unweighted Graph）。

可以把无向图理解成双向图, 有向图只能从某个节点到另一个节点，不能反向。

度

对于图中的每个节点，有一个度 (degree) 的概念。

在无向图中，度就是每个节点相连的边的条数。

在有向图中，度可以分为入度 (indegree) 和出度 (outdegree)。

入度：指向该节点的边的条数。

出度：从该节点出发的边的条数。

边和节点的数量关系

不考虑自环边（Self loop）和多重边（Multiple edges）等复杂的图。

在简单图中，假设包含 E 条边，V 个节点，我们想一下边的条数 E 的取值范围是多少？

E 的最小值可以是 0，相当于图结构中只有若干互不相连的节点，这是可以的。

考虑 E 的最大值，图中的每个节点最多可以有 V−1 条边与其他 V−1 个节点相连，所以最多能有的边数为 E=V(V−1)/2≈V^2。

如果几乎每两个节点之间都有一条边，即 E 接近 V^2，我们说这幅图是稠密图（Dense Graph）；如果只有很少的边，即 E 远小于 V^2，我们说这幅图是稀疏图（Sparse Graph）。

子图

子图 (Subgraph)：如果图 G’ 的所有节点和边都包含在图 G 中，则称 G’ 是 G 的一个子图。简单来说，子图是从原图中删除一些节点和边后得到的图。

生成子图 (Spanning Subgraph)：包含原图中所有节点，但只包含部分边的子图。

导出子图 (Induced Subgraph)：选择原图的一部分节点，以及这些节点之间在原图中的所有边所构成的子图。

子图的概念在很多图算法中都有应用，比如在寻找最小生成树时，我们实际上是在寻找一个包含所有节点的带权重最小的生成子图。

连通性

它描述了图中节点之间是否存在路径。

无向图的连通性

连通图 (Connected Graph): 如果无向图中任意两个节点之间都存在一条路径，我们称这个图是连通的。

连通分量 (Connected Component)：对于非连通的无向图，其中的多个连通子图被称为连通分量，一个图可以有多个连通分量。

有向图的强连通性

强连通图 (Strongly Connected Graph): 如果有向图中任意两个节点之间都存在一条路径，我们称这个图是强连通的。

弱连通图 (Weakly Connected Graph)：如果将有向图中的所有有向边都变成无向边后，该图变成连通的，那么原来的有向图就是弱连通的。

强连通分量 (Strongly Connected Component, SCC)：有向图中的若干个最大的强连通子图称为强连通分量。

弱连通分量 (Weakly Connected Component, WCC)：将有向图的所有有向边变为无向边后，形成的连通分量称为原有向图的弱连通分量。

图结构的通用代码实现

图的逻辑结构

图（Graph）由两部分组成：

顶点（Vertex / Node）：表示实体，如社交网络中的用户、地图中的城市。
边（Edge）：表示顶点之间的关系，如好友关系、道路连接。

一句话总结：图结构就是多叉树结构的延伸。
树中只允许父节点指向子节点，且子节点之间不能相连；而图中节点可以任意相互连接，形成复杂的网络。

邻接表 vs 邻接矩阵

特性	邻接表（Adjacency List）	邻接矩阵（Adjacency Matrix）
空间复杂度	O(V + E)（稀疏图更优）	O(V²)（稠密图可接受）
查询两点是否相连	O(degree(v))	O(1)
遍历邻居	高效（只遍历存在的边）	低效（需遍历整行）
适用场景	稀疏图（E ≪ V²）	稠密图（E ≈ V²）或需要频繁判断边存在性

不同种类的图结构

有向图（Directed Graph）：边有方向（A → B ≠ B → A）
无向图（Undirected Graph）：边无方向（A — B 等价于 B — A）
加权图（Weighted Graph）：每条边带有权重（如距离、成本）
无权图（Unweighted Graph）：边无权重（仅表示连接关系）

组合后共有四种基本类型：

有向无权图
有向加权图
无向无权图
无向加权图

图结构的通用代码实现（C++）

1. 有向加权图（邻接表实现）

 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
#include <vector>
#include <unordered_map>
#include <string>

struct Edge {
    std::string to;     // 目标顶点
    int weight;         // 边的权重
    
    Edge(const std::string& t, int w) : to(t), weight(w) {}
};

class WeightedDirectedGraphAdjList {
private:
    // 邻接表：顶点 -> 邻居列表
    std::unordered_map<std::string, std::vector<Edge>> adjList;
    
public:
    // 添加顶点
    void addVertex(const std::string& vertex) {
        adjList[vertex]; // 初始化空列表
    }
    
    // 添加有向加权边
    void addEdge(const std::string& from, const std::string& to, int weight) {
        adjList[from].emplace_back(to, weight);
    }
    
    // 获取邻居
    const std::vector<Edge>& getNeighbors(const std::string& vertex) const {
        static const std::vector<Edge> empty;
        auto it = adjList.find(vertex);
        return (it != adjList.end()) ? it->second : empty;
    }
    
    // 检查顶点是否存在
    bool hasVertex(const std::string& vertex) const {
        return adjList.count(vertex) > 0;
    }
};

2. 有向加权图（邻接矩阵实现）

 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
51
52
#include <vector>
#include <unordered_map>
#include <string>
#include <climits>

class WeightedDirectedGraphAdjMatrix {
private:
    std::vector<std::string> vertices;           // 顶点列表
    std::unordered_map<std::string, int> indexMap; // 顶点到索引的映射
    std::vector<std::vector<int>> adjMatrix;     // 邻接矩阵
    static const int INF = INT_MAX / 2;          // 表示无边
    
public:
    void addVertex(const std::string& vertex) {
        if (indexMap.count(vertex) == 0) {
            indexMap[vertex] = vertices.size();
            vertices.push_back(vertex);
            
            // 扩展矩阵
            for (auto& row : adjMatrix) {
                row.push_back(INF);
            }
            adjMatrix.push_back(std::vector<int>(vertices.size(), INF));
        }
    }
    
    void addEdge(const std::string& from, const std::string& to, int weight) {
        int i = indexMap[from];
        int j = indexMap[to];
        adjMatrix[i][j] = weight;
    }
    
    int getWeight(const std::string& from, const std::string& to) const {
        if (indexMap.count(from) == 0 || indexMap.count(to) == 0) {
            return INF;
        }
        return adjMatrix[indexMap.at(from)][indexMap.at(to)];
    }
    
    std::vector<std::string> getNeighbors(const std::string& vertex) const {
        std::vector<std::string> neighbors;
        if (indexMap.count(vertex) == 0) return neighbors;
        
        int idx = indexMap.at(vertex);
        for (int j = 0; j < vertices.size(); ++j) {
            if (adjMatrix[idx][j] != INF) {
                neighbors.push_back(vertices[j]);
            }
        }
        return neighbors;
    }
};

3. 有向无权图（邻接表实现）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class DirectedGraphAdjList {
private:
    std::unordered_map<std::string, std::vector<std::string>> adjList;
    
public:
    void addVertex(const std::string& vertex) {
        adjList[vertex];
    }
    
    void addEdge(const std::string& from, const std::string& to) {
        adjList[from].push_back(to);
    }
    
    const std::vector<std::string>& getNeighbors(const std::string& vertex) const {
        static const std::vector<std::string> empty;
        auto it = adjList.find(vertex);
        return (it != adjList.end()) ? it->second : empty;
    }
};

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
51
52
53
54
55
56
57
58
59
60
#include <vector>
#include <string>
#include <unordered_map>

class DirectedGraphAdjMatrix {
private:
    std::vector<std::string> vertices; // 存储顶点标签
    std::unordered_map<std::string, int> vertexIndices; // 顶点到索引的映射
    std::vector<std::vector<bool>> adjMatrix; // 邻接矩阵

    // 获取顶点的索引，如果顶点不存在，则返回 -1
    int getVertexIndex(const std::string& vertex) const {
        if (vertexIndices.find(vertex) == vertexIndices.end()) {
            return -1;
        }
        return vertexIndices.at(vertex);
    }

public:
    DirectedGraphAdjMatrix() {}

    // 添加顶点
    void addVertex(const std::string& vertex) {
        if (vertexIndices.find(vertex) == vertexIndices.end()) { // 如果顶点还未添加
            vertexIndices[vertex] = vertices.size();
            vertices.push_back(vertex);

            // 扩展邻接矩阵
            for (auto& row : adjMatrix) {
                row.push_back(false); // 新列全部初始化为 false
            }
            adjMatrix.emplace_back(vertices.size(), false); // 新行全部初始化为 false
        }
    }

    // 添加有向边
    void addEdge(const std::string& from, const std::string& to) {
        int fromIdx = getVertexIndex(from), toIdx = getVertexIndex(to);
        if (fromIdx != -1 && toIdx != -1) { // 确保两个顶点都存在
            adjMatrix[fromIdx][toIdx] = true;
        }
    }

    // 查询两点之间是否存在边
    bool hasEdge(const std::string& from, const std::string& to) const {
        int fromIdx = getVertexIndex(from), toIdx = getVertexIndex(to);
        if (fromIdx == -1 || toIdx == -1) return false; // 若任意顶点不存在，则返回 false
        return adjMatrix[fromIdx][toIdx];
    }

    // 打印邻接矩阵（调试用）
    void printAdjMatrix() const {
        for (const auto& row : adjMatrix) {
            for (bool isEdge : row) {
                std::cout << isEdge << " ";
            }
            std::cout << "\n";
        }
    }
};

5. 无向加权图（邻接表实现）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class WeightedUndirectedGraphAdjList {
private:
    std::unordered_map<std::string, std::vector<Edge>> adjList;
    
public:
    void addVertex(const std::string& vertex) {
        adjList[vertex];
    }
    
    void addEdge(const std::string& v1, const std::string& v2, int weight) {
        // 无向图：双向添加
        adjList[v1].emplace_back(v2, weight);
        adjList[v2].emplace_back(v1, weight);
    }
    
    const std::vector<Edge>& getNeighbors(const std::string& vertex) const {
        static const std::vector<Edge> empty;
        auto it = adjList.find(vertex);
        return (it != adjList.end()) ? it->second : empty;
    }
};

6. 无向加权图（邻接矩阵实现）

 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <vector>
#include <string>
#include <unordered_map>
#include <limits>
#include <iostream>

template<typename WeightType = int>
class UndirectedWeightedGraphAdjMatrix {
private:
    std::vector<std::string> vertices;                    // 顶点列表（按索引顺序）
    std::unordered_map<std::string, size_t> vertexIndex;  // 顶点名 → 索引映射
    std::vector<std::vector<WeightType>> adjMatrix;       // 邻接矩阵
    const WeightType INF;                                 // 表示“无边”的特殊值

public:
    // 构造函数：可自定义“无穷大”值（用于表示无连接）
    explicit UndirectedWeightedGraphAdjMatrix(
        const WeightType& inf = std::numeric_limits<WeightType>::max() / 2
    ) : INF(inf) {}

    // 添加顶点（若已存在则忽略）
    void addVertex(const std::string& v) {
        if (vertexIndex.find(v) != vertexIndex.end()) return;

        size_t idx = vertices.size();
        vertexIndex[v] = idx;
        vertices.push_back(v);

        // 扩展邻接矩阵：新增一行一列
        for (auto& row : adjMatrix) {
            row.push_back(INF);  // 新列初始化为 INF
        }
        adjMatrix.emplace_back(idx + 1, INF);  // 新行：idx+1 个 INF
    }

    // 添加无向加权边（自动双向设置）
    void addEdge(const std::string& u, const std::string& v, const WeightType& weight) {
        auto it_u = vertexIndex.find(u);
        auto it_v = vertexIndex.find(v);
        if (it_u == vertexIndex.end() || it_v == vertexIndex.end()) {
            // 可选：抛出异常或自动添加顶点
            // 这里选择自动添加缺失的顶点
            if (it_u == vertexIndex.end()) addVertex(u);
            if (it_v == vertexIndex.end()) addVertex(v);
            it_u = vertexIndex.find(u);
            it_v = vertexIndex.find(v);
        }

        size_t i = it_u->second;
        size_t j = it_v->second;
        adjMatrix[i][j] = weight;
        adjMatrix[j][i] = weight;  // 无向图：对称
    }

    // 获取边的权重（若无边则返回 INF）
    WeightType getWeight(const std::string& u, const std::string& v) const {
        auto it_u = vertexIndex.find(u);
        auto it_v = vertexIndex.find(v);
        if (it_u == vertexIndex.end() || it_v == vertexIndex.end()) {
            return INF;
        }
        return adjMatrix[it_u->second][it_v->second];
    }

    // 检查两个顶点之间是否有边
    bool hasEdge(const std::string& u, const std::string& v) const {
        return getWeight(u, v) != INF;
    }

    // 获取某个顶点的所有邻居及对应权重
    std::vector<std::pair<std::string, WeightType>> getNeighbors(const std::string& v) const {
        auto it = vertexIndex.find(v);
        if (it == vertexIndex.end()) return {};

        std::vector<std::pair<std::string, WeightType>> neighbors;
        size_t idx = it->second

7. 无向无权图（邻接表实现）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class UndirectedGraphAdjList {
private:
    std::unordered_map<std::string, std::vector<std::string>> adjList;
    
public:
    void addVertex(const std::string& vertex) {
        adjList[vertex];
    }
    
    void addEdge(const std::string& v1, const std::string& v2) {
        // 无向图：双向添加
        adjList[v1].push_back(v2);
        adjList[v2].push_back(v1);
    }
    
    const std::vector<std::string>& getNeighbors(const std::string& vertex) const {
        static const std::vector<std::string> empty;
        auto it = adjList.find(vertex);
        return (it != adjList.end()) ? it->second : empty;
    }
};

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <iostream>

class UndirectedUnweightedGraph {
private:
    // 邻接表：顶点 -> 邻居集合（使用 vector 或 unordered_set 均可）
    // 此处使用 vector，若需去重或快速查找邻居是否存在，可用 unordered_set
    std::unordered_map<std::string, std::vector<std::string>> adjList;

public:
    // 添加顶点（可选，addEdge 会自动添加缺失顶点）
    void addVertex(const std::string& v) {
        adjList[v]; // 确保顶点存在（即使无邻居）
    }

    // 添加无向边（自动双向添加，并自动创建缺失顶点）
    void addEdge(const std::string& u, const std::string& v) {
        // 自动添加顶点（如果尚未存在）
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    // 检查顶点是否存在
    bool hasVertex(const std::string& v) const {
        return adjList.find(v) != adjList.end();
    }

    // 检查两个顶点之间是否有边
    bool hasEdge(const std::string& u, const std::string& v) const {
        auto it = adjList.find(u);
        if (it == adjList.end()) return false;
        
        // 线性查找（对于稠密邻居可改用 unordered_set 提升至 O(1)）
        for (const auto& neighbor : it->second) {
            if (neighbor == v) return true;
        }
        return false;
    }

    // 获取某个顶点的所有邻居
    const std::vector<std::string>& getNeighbors(const std::string& v) const {
        static const std::vector<std::string> empty;
        auto it = adjList.find(v);
        return (it != adjList.end()) ? it->second : empty;
    }

    // 获取所有顶点
    std::vector<std::string> getVertices() const {
        std::vector<std::string> vertices;
        for (const auto& pair : adjList) {
            vertices.push_back(pair.first);
        }
        return vertices;
    }

    // 移除边（可选功能）
    void removeEdge(const std::string& u, const std::string& v) {
        // 从 u 的邻居中移除 v
        auto& uNeighbors = adjList[u];
        uNeighbors.erase(
            std::remove(uNeighbors.begin(), uNeighbors.end(), v),
            uNeighbors.end()
        );

        // 从 v 的邻居中移除 u
        auto& vNeighbors = adjList[v];
        vNeighbors.erase(
            std::remove(vNeighbors.begin(), vNeighbors.end(), u),
            vNeighbors.end()
        );
    }

    // 打印图结构（调试用）
    void print() const {
        if (adjList.empty()) {
            std::cout << "Graph is empty.\n";
            return;
        }

        for (const auto& pair : adjList) {
            std::cout << pair.first << ": ";
            for (const auto& neighbor : pair.second) {
                std::cout << neighbor << " ";
            }
            std::cout << "\n";
        }
    }
};

9. 无向图（邻接矩阵实现）— 通用模板

 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
template<typename WeightType = bool>
class UndirectedGraphAdjMatrix {
private:
    std::vector<std::string> vertices;
    std::unordered_map<std::string, int> indexMap;
    std::vector<std::vector<WeightType>> adjMatrix;
    WeightType defaultWeight;
    
public:
    explicit UndirectedGraphAdjMatrix(const WeightType& def = WeightType{}) 
        : defaultWeight(def) {}
    
    void addVertex(const std::string& vertex) {
        if (indexMap.count(vertex) == 0) {
            indexMap[vertex] = vertices.size();
            vertices.push_back(vertex);
            
            for (auto& row : adjMatrix) {
                row.push_back(defaultWeight);
            }
            adjMatrix.push_back(std::vector<WeightType>(vertices.size(), defaultWeight));
        }
    }
    
    void addEdge(const std::string& v1, const std::string& v2, const WeightType& weight = WeightType{true}) {
        int i = indexMap[v1], j = indexMap[v2];
        adjMatrix[i][j] = weight;
        adjMatrix[j][i] = weight; // 无向图对称
    }
    
    WeightType getWeight(const std::string& v1, const std::string& v2) const {
        if (indexMap.count(v1) == 0 || indexMap.count(v2) == 0) {
            return defaultWeight;
        }
        return adjMatrix[indexMap.at(v1)][indexMap.at(v2)];
    }
};

使用建议

默认选择邻接表：大多数实际图都是稀疏的（如社交网络、网页链接）
邻接矩阵适用场景：
- 图规模较小（V ≤ 1000）
- 需要频繁检查两点间是否有边
- 算法本身基于矩阵操作（如 Floyd-Warshall）
加权图：使用 Edge 结构体或矩阵存储权重
无权图：邻接表用 vector<string>，邻接矩阵用 bool 或 int

这些实现提供了图论算法（DFS/BFS、最短路径、最小生成树等）的基础数据结构支撑。

图结构的 DFS/BFS 遍历

图的遍历就是多叉树遍历的延伸，主要遍历方式还是深度优先搜索（DFS）和广度优先搜索（BFS）。

唯一的区别是，树结构中不存在环，而图结构中可能存在环，所以我们需要标记遍历过的节点，避免遍历函数在环中死循环。

由于图结构的复杂性，可以细分为遍历图的「节点」、「边」和「路径」三种场景，每种场景的代码实现略有不同。

遍历图的「节点」和「边」时，需要 visited 数组在前序位置做标记，避免重复遍历；遍历图的「路径」时，需要 onPath 数组在前序位置标记节点，在后序位置撤销标记。

深度优先遍历（DFS)

遍历所有节点

 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
// 多叉树节点
class Node {
public:
    int val;
    std::vector<Node*> children;
};

// 多叉树的遍历框架
void traverse(Node* root) {
    // base case
    if (root == nullptr) {
        return;
    }
    // 前序位置
    std::cout << "visit " << root->val << std::endl;
    for (auto child : root->children) {
        traverse(child);
    }
    // 后序位置
}

// 图节点
class Vertex {
public:
    int id;
    std::vector<Vertex*> neighbors;
};

// 图的遍历框架
// 需要一个 visited 数组记录被遍历过的节点
// 避免走回头路陷入死循环
void traverse(Vertex* s, std::vector<bool>& visited) {
    // base case
    if (s == nullptr) {
        return;
    }
    if (visited[s->id]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s->id] = true;
    std::cout << "visit " << s->id << std::endl;
    for (auto neighbor : s->neighbors) {
        traverse(neighbor, visited);
    }
    // 后序位置
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 遍历图的所有节点
void traverse(const Graph& graph, int s, std::vector<bool>& visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    if (visited[s]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s] = true;
    std::cout << "visit " << s << std::endl;
    for (const Graph::Edge& e : graph.neighbors(s)) {
        traverse(graph, e.to, visited);
    }
    // 后序位置
}

所以算法的时间复杂度是 O(E+V)，其中 E 是边的总数，V 是节点的总数。

遍历所有边

 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
// 多叉树节点
class Node {
public:
    int val;
    vector<Node*> children;
    
    Node(int v = 0) : val(v) {}
};

// 遍历多叉树的树枝
void traverseBranch(Node* root) {
    // base case
    if (root == nullptr) {
        return;
    }
    for (Node* child : root->children) {
        cout << "visit branch: " << root->val << " -> " << child->val << endl;
        traverseBranch(child);
    }
}

// 图节点
class Vertex {
public:
    int id;
    vector<Vertex*> neighbors;
    
    Vertex(int i = 0) : id(i) {}
};

// 遍历图的边
// 需要一个二维 visited 数组记录被遍历过的边，visited[u][v] 表示边 u->v 已经被遍历过
void traverseEdges(Vertex* s, vector<vector<bool>>& visited) {
    // base case
    if (s == nullptr) {
        return;
    }
    for (Vertex* neighbor : s->neighbors) {
        // 如果边已经被遍历过，则跳过
        if (visited[s->id][neighbor->id]) {
            continue;
        }
        // 标记并访问边
        visited[s->id][neighbor->id] = true;
        cout << "visit edge: " << s->id << " -> " << neighbor->id << endl;
        traverseEdges(neighbor, visited);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 从起点 s 开始遍历图的所有边
void traverseEdges(const Graph& graph, int s, std::vector<std::vector<bool>>& visited) {
    // base case
    if (s < 0 || s >= graph.size()) {
        return;
    }
    for (const Graph::Edge& e : graph.neighbors(s)) {
      // 如果边已经被遍历过，则跳过
      if (visited[s][e.to]) {
        continue;
      }
      // 标记并访问边
      visited[s][e.to] = true;
      std::cout << "visit edge: " << s << " -> " << e.to << std::endl;
      traverseEdges(graph, e.to, visited);
    }
}

因为需要创建二维 visited 数组，这个算法的时间复杂度是 O(E+V^2)，空间复杂度是 O(V^2)，其中 E 是边的数量，V 是节点的数量。

遍历所有路径（仅使用 onPath 数组）

这种方法适用于需要记录遍历路径的场景，如 797. 所有可能的路径。onPath 数组记录当前 DFS 路径上的节点，进入节点时添加，离开时移除。

 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
#include <vector>
#include <iostream>
using namespace std;

class Solution {
private:
    vector<vector<int>> allPaths;
    vector<int> path;
    
    void dfs(vector<vector<int>>& graph, int node) {
        // 添加当前节点到路径
        path.push_back(node);
        
        // 到达终点
        if (node == graph.size() - 1) {
            allPaths.push_back(path);
        } else {
            // 遍历相邻节点
            for (int neighbor : graph[node]) {
                dfs(graph, neighbor);
            }
        }
        
        // 从路径中移除当前节点（回溯）
        path.pop_back();
    }
    
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        dfs(graph, 0);
        return allPaths;
    }
};

同时使用 visited 和 onPath 数组

当图中存在环，且需要检测环或记录当前路径时，同时使用两个数组：

visited：记录所有已访问节点，防止重复遍历
onPath：记录当前 DFS 路径上的节点，用于检测环

 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
51
52
53
54
55
#include <vector>
#include <iostream>
using namespace std;

class Graph {
private:
    vector<vector<int>> adjList;
    int V;
    
public:
    Graph(int vertices) : V(vertices), adjList(vertices) {}
    
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }
    
    void traverseWithVisitedAndOnPath() {
        vector<bool> visited(V, false);
        vector<bool> onPath(V, false);
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, visited, onPath);
            }
        }
    }
    
    void dfs(int node, vector<bool>& visited, vector<bool>& onPath) {
        // 检测到环
        if (onPath[node]) {
            cout << "检测到环，包含节点: " << node << endl;
        }
        
        if (visited[node]) return;
        
        // 标记当前节点
        visited[node] = true;
        onPath[node] = true;
        cout << "访问节点: " << node << ", 路径: ";
        
        // 打印当前路径
        for (int i = 0; i < V; i++) {
            if (onPath[i]) cout << i << " ";
        }
        cout << endl;
        
        // 遍历邻居
        for (int neighbor : adjList[node]) {
            dfs(neighbor, visited, onPath);
        }
        
        // 回溯：从当前路径移除节点
        onPath[node] = false;
    }
};

完全不用 visited 和 onPath 数组

在某些特定场景，如 DAG（有向无环图）或保证无环的图中，我们可以省略辅助数组。但请注意，这仅适用于特定问题，一般图遍历需要这些辅助数组防止死循环。

 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
#include <vector>
#include <iostream>
using namespace std;

class DAGTraversal {
private:
    vector<vector<int>> adjList;
    int V;
    
public:
    DAGTraversal(int vertices) : V(vertices), adjList(vertices) {}
    
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
    }
    
    void dfs(int node) {
        cout << "访问节点: " << node << endl;
        
        // 由于是DAG，无需visited标记
        for (int neighbor : adjList[node]) {
            dfs(neighbor);
        }
    }
    
    void traverseFrom(int start) {
        dfs(start);
    }
    
    // BFS实现，同样无需visited（假设是DAG）
    void bfs(int start) {
        vector<int> queue;
        queue.push_back(start);
        int front = 0;
        
        while (front < queue.size()) {
            int node = queue[front++];
            cout << "BFS访问节点: " << node << endl;
            
            for (int neighbor : adjList[node]) {
                queue.push_back(neighbor);
            }
        }
    }
};

广度优先搜索（BFS）

写法一：标准 BFS

 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
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

class GraphBFS1 {
private:
    vector<vector<int>> adjList;
    int V;
    
public:
    GraphBFS1(int vertices) : V(vertices), adjList(vertices) {}
    
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // 无向图
    }
    
    void bfs(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            cout << "访问节点: " << node << endl;
            
            for (int neighbor : adjList[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
    }
};

写法二：带层级遍历的 BFS

 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
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

class GraphBFS2 {
private:
    vector<vector<int>> adjList;
    int V;
    
public:
    GraphBFS2(int vertices) : V(vertices), adjList(vertices) {}
    
    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u); // 无向图
    }
    
    void bfsWithLevel(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        int level = 0;
        while (!q.empty()) {
            int levelSize = q.size();
            cout << "层级 " << level << ": ";
            
            for (int i = 0; i < levelSize; i++) {
                int node = q.front();
                q.pop();
                cout << node << " ";
                
                for (int neighbor : adjList[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
            cout << endl;
            level++;
        }
    }
};

写法三：BFS 通用模板

  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
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <vector>
#include <queue>
#include <unordered_set>
#include <iostream>
using namespace std;

// 通用BFS模板，适用于各种场景
template <typename T>
class BFSTemplate {
public:
    // 标准BFS遍历
    static void bfs(
        const vector<vector<T>>& graph, 
        T start,
        function<void(T)> visitNode = [](T node) { cout << "访问节点: " << node << endl; },
        function<vector<T>(T)> getNeighbors = [](T node) { return vector<T>(); }
    ) {
        unordered_set<T> visited;
        queue<T> q;
        
        visited.insert(start);
        q.push(start);
        
        while (!q.empty()) {
            T node = q.front();
            q.pop();
            
            // 访问节点
            visitNode(node);
            
            // 获取邻居
            vector<T> neighbors = getNeighbors(node);
            if (neighbors.empty() && node < graph.size()) {
                neighbors = graph[node];
            }
            
            // 遍历邻居
            for (T neighbor : neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }
    
    // 带层级信息的BFS
    static void bfsWithLevel(
        const vector<vector<T>>& graph, 
        T start,
        function<void(T, int)> visitNode = [](T node, int level) { 
            cout << "层级 " << level << " - 节点: " << node << endl; 
        },
        function<vector<T>(T)> getNeighbors = [](T node) { return vector<T>(); }
    ) {
        unordered_set<T> visited;
        queue<pair<T, int>> q; // 节点和层级
        
        visited.insert(start);
        q.push({start, 0});
        
        while (!q.empty()) {
            auto [node, level] = q.front();
            q.pop();
            
            // 访问节点
            visitNode(node, level);
            
            // 获取邻居
            vector<T> neighbors = getNeighbors(node);
            if (neighbors.empty() && node < graph.size()) {
                neighbors = graph[node];
            }
            
            // 遍历邻居
            for (T neighbor : neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push({neighbor, level + 1});
                }
            }
        }
    }
};

// 使用示例
void exampleUsage() {
    // 创建图
    vector<vector<int>> graph = {
        {1, 2},    // 0的邻居
        {0, 3, 4}, // 1的邻居
        {0, 5},    // 2的邻居
        {1},       // 3的邻居
        {1},       // 4的邻居
        {2}        // 5的邻居
    };
    
    // 标准BFS
    cout << "标准BFS:" << endl;
    BFSTemplate<int>::bfs(graph, 0);
    
    // 带层级的BFS
    cout << "\n带层级的BFS:" << endl;
    BFSTemplate<int>::bfsWithLevel(graph, 0);
}

欧拉图与一笔画问题

一笔画游戏

一笔画游戏是一种经典益智游戏，规则要求玩家一笔连接所有的点和边，其中：

点可以重复经过
每条边必须恰好经过一次，不能重复
完成游戏的窍门：
- 如果所有节点的度数都是偶数：可以从任何节点开始，最终会回到起点
- 如果恰好有两个节点的度数为奇数：必须从这两个奇数度节点中的任意一个开始
- 其他情况：无法完成一笔画

七桥问题

欧拉图的概念源于18世纪著名的哥尼斯堡七桥问题：

当时的哥尼斯堡（现俄罗斯加里宁格勒）有一条河流将城市分为南北两岸
河中有东西两个小岛
七座桥连接着北岸、南岸、东岛和西岛
问题：能否设计一条路线，从任意区域出发，经过每座桥恰好一次，最后回到起点？

欧拉将这个问题抽象为图论问题：

每个区域对应一个节点
每座桥对应一条边
问题转化为：是否存在一条路径，经过图中每条边恰好一次，且最终回到起点

欧拉通过数学证明七桥问题无解，由此开创了图论这一数学分支。

术语定义

欧拉路径（Euler Path）：经过图中每条边恰好一次的路径
欧拉回路（Euler Circuit）：经过图中每条边恰好一次，并且起点和终点相同的回路
欧拉图（Eulerian Graph）：包含欧拉回路的图
半欧拉图（Semi-Eulerian Graph）：包含欧拉路径但不包含欧拉回路的图
节点的度（Degree）：无向图中，与节点相连的边的数量；有向图中，分为入度和出度

欧拉图的判定

无向图

欧拉图（存在欧拉回路）的判定条件：
1. 图是连通的
2. 所有顶点的度数均为偶数
半欧拉图（存在欧拉路径）的判定条件：
1. 图是连通的
2. 恰好有两个顶点的度数为奇数（作为路径的起点和终点）
3. 其余顶点的度数均为偶数

有向图

欧拉图（存在欧拉回路）的判定条件：
1. 图是强连通的
2. 每个顶点的入度等于出度
半欧拉图（存在欧拉路径）的判定条件：
1. 图是单连通的
2. 恰好有一个顶点的出度比入度大1（作为起点）
3. 恰好有一个顶点的入度比出度大1（作为终点）
4. 其余顶点的入度等于出度

寻找欧拉路径的算法

Hierholzer算法是寻找欧拉路径/回路的经典算法，它是DFS算法的拓展，时间复杂度为O(E)，其中E为边的数量。

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
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;

// 无向图的欧拉路径/回路
class UndirectedEulerian {
private:
    // 邻接表表示图，pair.second表示边是否被访问过
    unordered_map<int, vector<pair<int, bool>>> graph;
    vector<pair<int, int>> path; // 存储欧拉路径的边
    
    // 递归DFS实现
    void dfs(int u) {
        for (auto& [v, visited] : graph[u]) {
            if (!visited) {
                // 标记边为已访问
                visited = true;
                // 由于是无向图，需要同时标记反向边
                for (auto& [x, vis] : graph[v]) {
                    if (x == u && !vis) {
                        vis = true;
                        break;
                    }
                }
                dfs(v);
                path.push_back({u, v});
            }
        }
    }
    
    // Hierholzer算法的栈实现
    void hierholzer(int start) {
        stack<int> nodeStack;
        nodeStack.push(start);
        
        while (!nodeStack.empty()) {
            int u = nodeStack.top();
            bool hasUnvisitedEdge = false;
            
            for (auto& [v, visited] : graph[u]) {
                if (!visited) {
                    visited = true;
                    // 标记反向边
                    for (auto& [x, vis] : graph[v]) {
                        if (x == u && !vis) {
                            vis = true;
                            break;
                        }
                    }
                    nodeStack.push(v);
                    hasUnvisitedEdge = true;
                    break;
                }
            }
            
            if (!hasUnvisitedEdge) {
                nodeStack.pop();
                if (!nodeStack.empty()) {
                    path.push_back({nodeStack.top(), u});
                }
            }
        }
    }
    
public:
    void addEdge(int u, int v) {
        graph[u].push_back({v, false});
        graph[v].push_back({u, false}); // 无向图
    }
    
    // 寻找欧拉回路
    bool findEulerCircuit(int start) {
        path.clear();
        
        // 检查度数条件
        for (auto& [node, edges] : graph) {
            if (edges.size() % 2 != 0) {
                return false; // 存在奇度数节点，不是欧拉图
            }
        }
        
        // 使用Hierholzer算法
        hierholzer(start);
        
        // 检查是否遍历了所有边
        size_t edgeCount = 0;
        for (auto& [node, edges] : graph) {
            edgeCount += edges.size();
        }
        edgeCount /= 2; // 每条边在邻接表中出现两次
        
        return path.size() == edgeCount;
    }
    
    // 寻找欧拉路径
    bool findEulerPath() {
        path.clear();
        
        // 检查度数条件
        vector<int> oddDegreeNodes;
        for (auto& [node, edges] : graph) {
            if (edges.size() % 2 != 0) {
                oddDegreeNodes.push_back(node);
            }
        }
        
        // 要么没有奇度节点，要么恰好有两个
        if (oddDegreeNodes.size() != 0 && oddDegreeNodes.size() != 2) {
            return false;
        }
        
        int startNode = (oddDegreeNodes.size() == 2) ? oddDegreeNodes[0] : graph.begin()->first;
        
        // 使用Hierholzer算法
        hierholzer(startNode);
        
        // 检查是否遍历了所有边
        size_t edgeCount = 0;
        for (auto& [node, edges] : graph) {
            edgeCount += edges.size();
        }
        edgeCount /= 2; // 每条边在邻接表中出现两次
        
        return path.size() == edgeCount;
    }
    
    void printPath() {
        cout << "欧拉路径/回路: ";
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << "(" << path[i].first << "->" << path[i].second << ") ";
        }
        cout << endl;
    }
};

// 有向图的欧拉路径/回路
class DirectedEulerian {
private:
    // 邻接表表示图，pair.second表示边是否被访问过
    unordered_map<int, vector<pair<int, bool>>> graph;
    vector<pair<int, int>> path; // 存储欧拉路径的边
    
    // Hierholzer算法的栈实现
    void hierholzer(int start) {
        stack<int> nodeStack;
        nodeStack.push(start);
        
        while (!nodeStack.empty()) {
            int u = nodeStack.top();
            bool hasUnvisitedEdge = false;
            
            for (auto& [v, visited] : graph[u]) {
                if (!visited) {
                    visited = true;
                    nodeStack.push(v);
                    hasUnvisitedEdge = true;
                    break;
                }
            }
            
            if (!hasUnvisitedEdge) {
                nodeStack.pop();
                if (!nodeStack.empty()) {
                    path.push_back({nodeStack.top(), u});
                }
            }
        }
    }
    
public:
    void addEdge(int u, int v) {
        graph[u].push_back({v, false});
    }
    
    // 计算入度和出度
    void getInOutDegrees(unordered_map<int, int>& inDegrees, unordered_map<int, int>& outDegrees) {
        for (auto& [u, edges] : graph) {
            outDegrees[u] = edges.size();
            for (auto& [v, visited] : edges) {
                inDegrees[v]++;
            }
        }
    }
    
    // 寻找欧拉回路
    bool findEulerCircuit(int start) {
        path.clear();
        
        // 检查度数条件
        unordered_map<int, int> inDegrees, outDegrees;
        getInOutDegrees(inDegrees, outDegrees);
        
        for (auto& [node, edges] : graph) {
            if (inDegrees[node] != outDegrees[node]) {
                return false; // 入度不等于出度，不是欧拉图
            }
        }
        
        // 使用Hierholzer算法
        hierholzer(start);
        
        // 检查是否遍历了所有边
        size_t edgeCount = 0;
        for (auto& [node, edges] : graph) {
            edgeCount += edges.size();
        }
        
        return path.size() == edgeCount;
    }
    
    // 寻找欧拉路径
    bool findEulerPath() {
        path.clear();
        
        // 检查度数条件
        unordered_map<int, int> inDegrees, outDegrees;
        getInOutDegrees(inDegrees, outDegrees);
        
        int startCount = 0, endCount = 0;
        int startNode = -1;
        
        for (auto& [node, edges] : graph) {
            int diff = outDegrees[node] - inDegrees[node];
            if (diff == 1) {
                startCount++;
                startNode = node; // 起点
            } else if (diff == -1) {
                endCount++;
            } else if (diff != 0) {
                return false; // 度数差不为-1,0,1
            }
        }
        
        // 要么没有起点终点，要么恰好各一个
        if (!((startCount == 0 && endCount == 0) || (startCount == 1 && endCount == 1))) {
            return false;
        }
        
        // 如果没有指定起点，选择任意节点
        if (startNode == -1) {
            startNode = graph.begin()->first;
        }
        
        // 使用Hierholzer算法
        hierholzer(startNode);
        
        // 检查是否遍历了所有边
        size_t edgeCount = 0;
        for (auto& [node, edges] : graph) {
            edgeCount += edges.size();
        }
        
        return path.size() == edgeCount;
    }
    
    void printPath() {
        cout << "欧拉路径/回路: ";
        for (int i = path.size() - 1; i >= 0; i--) {
            cout << "(" << path[i].first << "->" << path[i].second << ") ";
        }
        cout << endl;
    }
};

// 测试示例
int main() {
    // 无向图欧拉回路示例
    cout << "===== 无向图欧拉回路示例 =====" << endl;
    UndirectedEulerian undirGraph;
    undirGraph.addEdge(0, 1);
    undirGraph.addEdge(1, 2);
    undirGraph.addEdge(2, 3);
    undirGraph.addEdge(3, 0);
    undirGraph.addEdge(0, 2);
    
    if (undirGraph.findEulerCircuit(0)) {
        cout << "找到欧拉回路!" << endl;
        undirGraph.printPath();
    } else {
        cout << "未找到欧拉回路，尝试寻找欧拉路径..." << endl;
        if (undirGraph.findEulerPath()) {
            cout << "找到欧拉路径!" << endl;
            undirGraph.printPath();
        } else {
            cout << "未找到欧拉路径" << endl;
        }
    }
    
    // 有向图欧拉路径示例
    cout << "\n===== 有向图欧拉路径示例 =====" << endl;
    DirectedEulerian dirGraph;
    dirGraph.addEdge(0, 1);
    dirGraph.addEdge(1, 2);
    dirGraph.addEdge(1, 3);
    dirGraph.addEdge(2, 1);
    dirGraph.addEdge(3, 0);
    dirGraph.addEdge(3, 4);
    dirGraph.addEdge(4, 3);
    
    if (dirGraph.findEulerPath()) {
        cout << "找到欧拉路径!" << endl;
        dirGraph.printPath();
    } else {
        cout << "未找到欧拉路径" << endl;
    }
    
    return 0;
}

代码说明

Hierholzer算法核心思想：
- 从起点开始，深度遍历图
- 当无法继续前进时，将当前节点加入路径
- 最终得到的路径是逆序的，需要反转
两种实现方式：
- 递归DFS实现：简洁，但可能栈溢出
- 非递归栈实现：更稳定，适合大型图
无向图与有向图的区别：
- 无向图：需要同时标记正反向边
- 有向图：只需标记单向边
算法步骤：
- 验证图是否满足欧拉路径/回路的条件
- 使用Hierholzer算法寻找路径
- 验证是否遍历了所有边

复杂度分析

时间复杂度：O(E)，其中E为边的数量
空间复杂度：O(V+E)，其中V为顶点数量，E为边的数量

Hierholzer算法是解决欧拉路径问题的最优算法，在电路设计、路径规划等领域有广泛应用。

图结构最短路径算法详解

最短路径问题概览

最短路径问题在现实生活中应用广泛，如计算最小成本、最短路径长度、最少时间等。在算法中，我们通常将这类问题抽象为计算加权图中的最小路径权重。本文中，“最短路径"和"最小路径权重和"是等价的。

最短路径问题主要分为两类：

单源最短路径：计算从一个起点到其他所有顶点的最短路径
多源最短路径：计算任意两节点之间的最短路径

单源最短路径

单源最短路径问题要求计算从某个起点出发，到图中其他所有顶点的最短路径。例如，有n个节点(0到n-1)，计算从节点2到其他所有节点的最短路径。

单源最短路径算法的输出通常是一个一维数组distTo，其中distTo[i]表示从起点到节点i的最短路径长度。

代表性算法：

Dijkstra算法：基于BFS+贪心思想，效率高，但不能处理带负权重的图
基于队列的Bellman-Ford算法(SPFA)：可以处理带负权重的图，但效率比Dijkstra低

点对点最短路径

点对点最短路径问题只需计算从起点src到特定目标节点dst的最短路径，是单源最短路径的特例。通常可以通过在找到目标节点后提前结束单源最短路径算法来解决。

**A算法(A Star Algorithm)**是专门处理点对点问题的算法，它利用启发式函数(Heuristic Function)有方向性地进行搜索，提高效率。A算法的关键在于：

充分利用已知信息(起点和终点)
通过启发函数引导搜索方向
在经验法则和实际情况中找到平衡

多源最短路径

多源最短路径问题要求计算图中任意两节点之间的最短路径。例如，有n个节点(0到n-1)，计算所有节点对之间的最短路径。

多源最短路径算法的输出是一个二维数组dist，其中dist[i][j]表示从节点i到节点j的最短路径长度。

代表性算法：

Floyd算法：基于动态规划，适合稠密图
多次调用Dijkstra：对每个节点作为起点运行Dijkstra，适合稀疏图

负权重边的影响

负权重边会使最短路径问题变得复杂。在不含负权重边的图中，Dijkstra等贪心算法可以正确工作，因为随着经过的边数增加，路径权重和也会增加。但负权重边打破了这一假设。

负权重环的影响尤为严重：如果存在从起点可达的负权重环，最短路径问题就没有意义，因为可以在环上无限循环使路径权重趋于负无穷。

算法对负权重边的处理能力：

不能处理负权重边：Dijkstra算法、A*算法
可以处理负权重边：Bellman-Ford算法、SPFA算法、Floyd算法
常用于检测负权重环：Bellman-Ford算法

Dijkstra 算法简介

Dijkstra算法是解决单源最短路径问题的经典算法，本质是BFS+贪心思想的结合。算法使用优先队列(Priority Queue)每次选择当前已知距离最短的节点进行扩展。

算法步骤：

初始化：起点距离为0，其他节点距离为无穷大
将所有节点加入优先队列
当队列非空：
- 取出当前距离最小的节点u
- 遍历u的所有邻居v
- 如果通过u到达v的路径更短，则更新v的距离
最终得到从起点到所有节点的最短距离

特点：

不能处理带负权重的图
时间复杂度：使用优先队列时为O(ElogV)，其中E为边数，V为顶点数
空间复杂度：O(V+E)

A* 算法简介

A*算法是Dijkstra算法的改进版，专为解决点对点最短路径问题设计。它引入了启发式函数h(n)，估计从节点n到目标节点的代价，使搜索更有方向性。

A*算法使用评估函数：f(n) = g(n) + h(n)

g(n)：从起点到节点n的实际代价
h(n)：从节点n到目标节点的估计代价（启发式函数）

关键性质：

当h(n) = 0时，A*退化为Dijkstra算法
当h(n)小于等于实际代价时，A*保证找到最短路径
当h(n)越接近实际代价，搜索效率越高

A*算法的效率高度依赖于启发式函数的设计。在地图导航等应用中，常用欧几里得距离或曼哈顿距离作为启发式函数。

Bellman-Ford/SPFA 算法简介

Bellman-Ford算法可以处理带负权重的单源最短路径问题，并能检测负权重环。原始Bellman-Ford算法时间复杂度较高(O(VE))，而SPFA(Shortest Path Faster Algorithm)是其队列优化版本。

SPFA算法核心思想：

使用队列存储需要松弛的节点
每次从队列中取出一个节点u
尝试通过u松弛其所有邻居v
如果v的距离被更新且不在队列中，将v加入队列
重复直到队列为空

特点：

可以处理带负权重的图
能检测负权重环(如果某节点入队次数超过V次)
平均时间复杂度优于Bellman-Ford，但最坏情况下仍是O(VE)
空间复杂度：O(V+E)

Floyd 算法简介

Floyd算法(又称Floyd-Warshall算法)是解决多源最短路径问题的经典算法，本质是动态规划的应用。

算法核心：

定义状态：dp[k][i][j]表示从i到j，中间只经过编号不超过k的节点的最短路径
状态转移：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
优化：可以压缩为二维DP，直接在原数组上更新

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
48
#include <vector>
#include <climits>
#include <algorithm>
#include <iostream>
using namespace std;

// Floyd算法C++实现
void floyd(vector<vector<int>>& dist) {
    int n = dist.size();
    
    // dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])
    // 优化为二维DP，k作为最外层循环
    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] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

// 使用示例
int main() {
    // 示例：4个节点的图
    const int INF = INT_MAX;
    vector<vector<int>> dist = {
        {0, 3, INF, 5},
        {2, 0, INF, 4},
        {INF, 1, 0, INF},
        {INF, INF, 2, 0}
    };
    
    floyd(dist);
    
    // 输出结果
    for (const auto& row : dist) {
        for (int d : row) {
            if (d == INF) cout << "INF ";
            else cout << d << " ";
        }
        cout << endl;
    }
    
    return 0;
}

特点：

能处理带负权重的图(但不能有负权重环)
时间复杂度：O(V³)，适合节点数较少的稠密图
空间复杂度：O(V²)
算法简单，易于实现，且可以检测负权重环

总结

最短路径算法是图论中的核心问题，不同算法适用于不同场景：

无负权重边的单源最短路径：Dijkstra算法
有点对点需求且有启发式信息：A*算法
有负权重边的单源最短路径：Bellman-Ford/SPFA算法
多源最短路径：Floyd算法或多次调用Dijkstra

最小生成树算法

什么是生成树

给定一个无向连通图 G，其生成树是 G 的一个子图，具有以下关键特性：

包含原图中的所有顶点
边的数量恰好为顶点数减一（V-1条边）
连通且无环（满足树的定义）

一个图通常可以有多个不同的生成树。同一张图可以有不同的生成树结构，其中红色标记的边构成了生成树。生成树的核心在于保持图的连通性，同时消除所有环路。

什么是最小生成树

当图是加权图（每条边都有权重）时，最小生成树(Minimum Spanning Tree, MST) 就是所有生成树中边权重总和最小的那一棵。

现实应用场景：

设计最低成本的通信网络
电路布线优化
城市间公路/管道铺设
聚类分析

例如，在城市间修建公路时，节点代表城市，边代表可能的公路连接，权重代表修建成本。最小生成树算法能找出连接所有城市的最低总成本方案。

最小生成树算法

有两类经典算法用于求解最小生成树问题，它们都基于贪心思想，但实现方式不同：

1. Kruskal 算法

核心思想：按边权重从小到大排序，依次选择不会形成环的边
实现要点：
- 首先对图中所有边按权重升序排序
- 使用Union-Find 并查集数据结构高效检测是否形成环
- 逐个添加边，直到形成包含所有顶点的树
时间复杂度：O(E log E)，其中 E 为边的数量
优势：实现相对简单，适合稀疏图

2. Prim 算法

核心思想：从单个顶点开始，逐步扩展生成树
实现要点：
- 从任意顶点开始，维护一个"已加入MST"的顶点集合
- 每次选择连接已加入顶点和未加入顶点的最小权重边
- 使用优先级队列(最小堆) 高效选择下一条边
- 重复直到所有顶点都被包含
时间复杂度：使用优先队列时为 O(E log V)
优势：与 Dijkstra 算法相似，适合稠密图

两种算法在正确性上都能找到全局最优解，但在不同图结构和实现方式下效率可能不同。

随机地图构造问题

最小生成树算法经过巧妙改造后，可广泛应用于游戏地图生成，特别是随机迷宫和洞穴场景的构造：

核心思想：

利用最小生成树"连接所有顶点且无环"的特性
确保生成地图的连通性（从起点总能到达终点）
通过引入随机性，创造每次不同的自然地图结构

两种算法生成地图的特点：

Kruskal 算法生成地图：
- 地图初始化为完整网格图结构
- 从多个随机位置同时开始生成路径
- 最终连接成一个完整迷宫
- 生成的地图通常具有更多分支和死胡同
- 路径分布较为均匀
Prim 算法生成地图：
- 地图初始状态全部为障碍物
- 从单一起点向周围逐步扩展路径
- 生成的地图通常具有长通道和较少分支
- 路径分布从起点向外辐射

并查集(Union Find)算法

动态连通性及术语

连通分量：图中相互连通的一组节点。初始时，每个节点自成一个连通分量。

连接操作(Union)：将两个节点连接，如果它们原本属于不同的连通分量，则合并这两个分量。

连通性(Connectivity)：两个节点之间存在路径，满足以下性质：

自反性：节点p和p自身是连通的
对称性：如果节点p和q连通，那么q和p也连通
传递性：如果p和q连通，q和r连通，那么p和r也连通

动态连通性问题：在图中动态地进行连接操作，并随时查询任意两个节点是否连通，或查询当前连通分量的数量。这种"等价关系"在编译器优化、社交网络分析等领域有广泛应用。

为什么需要并查集算法

传统图结构(邻接表/邻接矩阵)难以高效处理动态连通性问题：

连接操作：添加一条边可以在O(1)时间内完成
连通性查询：需要DFS/BFS遍历，最坏时间复杂度O(V+E)
连通分量计数：需要完整遍历图，时间复杂度O(V+E)

而并查集API设计简洁高效：

1
2
3
4
5
6
7
class UF {
public:
    UF(int n);                 // 初始化，O(n)
    void union(int p, int q);  // 连接节点，O(1)
    bool connected(int p, int q); // 查询连通性，O(1)
    int count();               // 查询连通分量数量，O(1)
};

并查集不仅时间复杂度优越(O(1)操作)，而且不需要构造完整的图结构，仅用一个数组就能高效解决问题。

并查集的核心原理

并查集本质上是一种森林结构，每个连通分量表示为一棵树：

每个节点指向其父节点
每棵树的根节点代表该连通分量
判断连通性：检查两个节点是否拥有相同的根节点
连接操作：将一棵树的根节点指向另一棵树的根节点

并查集的实现及优化

未优化的并查集效果

未优化的并查集在最坏情况下会退化成链表，导致查找操作的时间复杂度达到O(n)。例如，依次连接0-1, 1-2, 2-3…，最终形成一条长链，每次查找根节点都需要遍历整条链。

 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
// 未优化的并查集 C++实现
class UnoptimizedUF {
private:
    vector<int> parent;
    int count;
    
public:
    UnoptimizedUF(int n) {
        count = n;
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 每个节点初始时指向自己
        }
    }
    
    int find(int x) {
        // 未优化的查找，可能遍历整条链
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }
    
    void unionNodes(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        
        // 简单地将rootQ连接到rootP
        parent[rootQ] = rootP;
        count--;
    }
    
    bool connected(int p, int q) {
        return find(p) == find(q);
    }
    
    int getCount() {
        return count;
    }
};

权重数组的优化效果

按秩合并(Weighted Quick Union) 优化通过维护每棵树的大小，总是将小树连接到大树上，避免树过高：

 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
// 带权重优化的并查集 C++实现
class WeightedUF {
private:
    vector<int> parent;
    vector<int> size; // 记录每棵树的大小
    int count;
    
public:
    WeightedUF(int n) {
        count = n;
        parent.resize(n);
        size.resize(n, 1); // 初始时每棵树大小为1
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        while (parent[x] != x) {
            x = parent[x];
        }
        return x;
    }
    
    void unionNodes(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        
        // 将小树连接到大树
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count--;
    }
    
    bool connected(int p, int q) {
        return find(p) == find(q);
    }
    
    int getCount() {
        return count;
    }
};

优化效果：

树的高度被控制在O(log n)级别
查找和合并操作的时间复杂度降至O(log n)
避免了树的极度不平衡

路径压缩的优化效果

路径压缩(Path Compression) 优化在查找操作时，将路径上的所有节点直接指向根节点，进一步降低树的高度：

 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 带权重优化和路径压缩的并查集 C++实现
class OptimizedUF {
private:
    vector<int> parent;
    vector<int> size;
    int count;
    
public:
    OptimizedUF(int n) {
        count = n;
        parent.resize(n);
        size.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];
    }
    
    // 非递归实现的路径压缩
    int findIterative(int x) {
        int root = x;
        // 先找到根节点
        while (root != parent[root]) {
            root = parent[root];
        }
        
        // 将路径上的所有节点直接指向根
        while (x != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        
        return root;
    }
    
    void unionNodes(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count--;
    }
    
    bool connected(int p, int q) {
        return find(p) == find(q);
    }
    
    int getCount() {
        return count;
    }
};

优化效果：

近乎常数时间复杂度：结合按秩合并和路径压缩，单次操作的均摊时间复杂度为O(α(n))，其中α是反阿克曼函数，对于任何实际输入大小，α(n) < 5
树的高度极低：经过多次操作后，树的高度几乎保持在常数级别
自调整结构：频繁访问的节点会被优化到更靠近根的位置

总结

并查集通过精巧的数据结构设计，将动态连通性问题的效率从O(V+E)提升到了接近O(1)。两种优化技术(按秩合并+路径压缩)共同作用，使并查集成为图论算法中效率最高的数据结构之一。在实际应用中，优化后的并查集几乎可以视为常数时间操作，适用于处理大规模动态连通性问题，如社交网络分析、图像分割、电路设计等场景。

Reference

https://labuladong.online/algo/data-structure-basic/graph-traverse-basic/