C++ 实现图邻接表的完全指南：从原理到最佳实践

在 C++ 开发中，处理图相关的算法问题时，选择一种高效且易于维护的数据结构至关重要。你可能已经听说过邻接矩阵，但在处理大规模数据或稀疏图时，它往往会浪费大量的内存空间。在今天的这篇文章中，我们将深入探讨一种更通用、更灵活的图的表示方法——邻接表。

我们将从基本概念出发，一起探索如何在 C++ 中从零开始构建邻接表，分析它的存储机制，并通过多个完整的代码示例来掌握它的实现技巧。无论你是正在准备算法面试，还是正在开发涉及网络拓扑或地图路径的软件，这篇文章都将为你提供实用的参考。

什么是邻接表？

简单来说，邻接表 是一种结合了数组和链表（或动态数组）优点的数据结构。它的核心思想非常直观：我们使用一个数组，其中数组的每一个索引对应图中的一个顶点。而数组中的每个元素，本身又是一个容器（比如 C++ 中的 vector），用来存储所有与该顶点相连的其他顶点。

为了让你更好地理解，我们可以这样想象：

• 数组：就像是通讯录的分类索引，每个人的名字占一个位置。
• 链表/Vector：就像是每个人名下的详细好友列表。

当我们需要找某个顶点的所有邻居时，只需访问数组的对应索引，就能立刻拿到关联的数据。相比于邻接矩阵（需要一个 $V \times V$ 的二维数组），邻接表在空间复杂度上通常具有显著优势，特别是对于边数远小于顶点数的平方的稀疏图。

图解：数据如何在内存中布局

为了加深印象，让我们通过具体的图例来看看数据是如何组织的。

#### 1. 无向图的情形

想象一个包含 3 个顶点（0, 1, 2）的无向图。在这种图中，连接是双向的：如果 0 连接到 1，那么 1 也连接到 0。

• 顶点 0：连接到 1 和 2。

内存视图*：INLINECODE1daad22f 包含 INLINECODEa71e88b3。

• 顶点 1：连接到 0 和 2。

内存视图*：INLINECODE607418fc 包含 INLINECODE6659f7fa。

• 顶点 2：连接到 1 和 0。

内存视图*：INLINECODEe60cc664 包含 INLINECODEe724e6c2。
关键点：在实现无向图时，我们每次添加边都需要做“双向绑定”。当你添加边 $(u, v)$ 时，必须在 INLINECODE33e1d39c 中添加 $v$，同时在 INLINECODE6c0a3583 中添加 $u$。

#### 2. 有向图的情形

现在，让我们把图变成有向图。箭头有了方向，关系的建立就变成了单向的。

• 顶点 0：没有出边（指向别人的边）。

内存视图*：INLINECODE4e71a0f6 为空 INLINECODEea13fcf7。

• 顶点 1：指向 0 和 2。

内存视图*：INLINECODE3fa57d05 包含 INLINECODEd3edc3ab。

• 顶点 2：指向 0。

内存视图*：INLINECODEa2f7cdb9 包含 INLINECODE8f05153c。

核心算法与实现逻辑

在编写代码之前，我们需要理清基本的逻辑步骤。这不仅是编程的基础，也是我们在面试中向面试官解释思路的关键。

我们可以通过以下步骤构建邻接表：

• 初始化：定义图中的顶点总数 $V$。创建一个大小为 $V$ 的容器数组（C++ 中通常用 vector<vector>）。
• 添加边 (addEdge)：

* 接收两个参数 $u$（源点）和 $v$（目标点）。

* 将 $v$ 添加到 $u$ 的链表中。

* 判断：如果图是无向的，必须回过头来将 $u$ 添加到 $v$ 的链表中。如果是有向图，则跳过这一步。

• 遍历与打印 (printGraph)：循环遍历数组中的每一个顶点，并输出其对应容器中的所有元素。

C++ 实战：标准实现 (使用 Vector)

在 C++ 中，std::vector 是实现邻接表的理想选择，因为它能够动态管理内存，无需我们手动处理链表的指针操作。下面是一个包含详细注释的完整实现方案。为了保证代码的健壮性，我们将图封装为一个类，并支持有向图和无向图的切换。

#include 
#include 
using namespace std;

// 定义图类，封装邻接表的操作
class Graph {
private:
    // 使用 vector 的 vector 来模拟邻接表
    // adjList[i] 存储的是顶点 i 的所有邻居
    vector<vector> adjList;
    // 标记图是否为有向图，默认为 false (无向)
    bool isDirected;

public:
    // 构造函数：初始化图
    // vertices: 顶点的数量
    // directed: 是否为有向图，默认为 false
    Graph(int vertices, bool directed = false) {
        // 调整 vector 的大小以适应顶点数量
        adjList.resize(vertices);
        isDirected = directed;
    }

    // 添加边的函数
    // src: 源顶点
    // dest: 目标顶点
    void addEdge(int src, int dest) {
        // 简单的边界检查（实际项目中可能需要抛出异常）
        if (src = adjList.size() || dest = adjList.size()) {
            cout << "无效的顶点索引！" < 1 时，也要连接 1 -> 0
        if (!isDirected) {
            adjList[dest].push_back(src);
        }
    }

    // 打印邻接表的函数
    void printGraph() {
        cout << "
--- 邻接表表示 ---" << endl;
        for (int i = 0; i < adjList.size(); ++i) {
            cout << "顶点 " << i << ": ";
            // 如果该顶点没有邻居，打印 "无"
            if (adjList[i].empty()) {
                cout << "无连接";
            } else {
                // 遍历并打印所有邻居
                for (int neighbor : adjList[i]) {
                    cout < " << neighbor << " ";
                }
            }
            cout << endl;
        }
    }
};

int main() {
    // 示例 1: 创建一个包含 5 个顶点的无向图
    Graph g(5);

    // 添加边构建网络拓扑
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    // 打印结构
    g.printGraph();

    cout << "
--- 切换到有向图测试 ---" << endl;
    // 示例 2: 创建一个包含 4 个顶点的有向图
    Graph directedG(4, true); // true 表示有向

    directedG.addEdge(0, 1);
    directedG.addEdge(0, 2);
    directedG.addEdge(2, 1); // 2指向1
    directedG.addEdge(3, 0); // 3指向0，但0不指向3

    directedG.printGraph();

    return 0;
}

进阶实现：处理带权图

在实际应用中，图往往不仅仅代表“是否连接”，还可能代表“距离”或“成本”。例如，在地图导航中，城市 A 到城市 B 可能是 10 公里。这时候，简单的整数列表就不够用了，我们需要存储 pair 对（目标顶点，权重）。

让我们看看如何修改代码来支持带权图。

#include 
#include 
#include  // for pair
using namespace std;

// 定义一个别名，使代码更易读
// 每一个邻居都是一个 pair
using AdjListType = vector<vector<pair>>;

class WeightedGraph {
private:
    AdjListType adjList;
    bool isDirected;

public:
    WeightedGraph(int vertices, bool directed = false) {
        adjList.resize(vertices);
        isDirected = directed;
    }

    // 修改后的 addEdge，增加了 weight 参数
    void addEdge(int src, int dest, int weight) {
        // 使用 make_pair 或大括号初始化
        adjList[src].push_back(make_pair(dest, weight));
        
        if (!isDirected) {
            adjList[dest].push_back(make_pair(src, weight));
        }
    }

    void printGraph() {
        cout << "
--- 带权邻接表 ---" << endl;
        for (int i = 0; i < adjList.size(); ++i) {
            cout << "顶点 " << i << ": ";
            for (auto &edge : adjList[i]) {
                // first 是目标顶点，second 是权重
                cout < (" << edge.first << ", 权:" << edge.second << ") ";
            }
            cout < 1号机场，票价 500
    airline.addEdge(0, 1, 500);
    airline.addEdge(0, 2, 300);
    airline.addEdge(1, 2, 100);
    airline.addEdge(2, 3, 200);

    airline.printGraph();
    
    return 0;
}

实战经验：链表实现 vs Vector实现

虽然我们在上面使用了 std::vector，但在传统的 C 语言教学或极度关注内存碎片化的场景中，你可能会看到真正的链表（指针实现）。

在 C++ 中，我们通常优先推荐使用 vector 而不是手写链表来实现邻接表。原因如下：

• 缓存局部性：vector 的数据在内存中是连续存储的，CPU 遍历时效率极高，而链表节点在内存中是分散的，容易导致缓存未命中。
• 内存管理：手写链表需要处理复杂的指针操作和内存释放，容易出错；vector 自动管理内存，安全性更高。

什么时候应该使用真正的指针链表？

• 当图的规模极其庞大，且边频繁地被添加和删除（导致 vector 频繁重新分配内存）时，链表 O(1) 的插入性能可能更有优势。但在绝大多数算法竞赛或工程实践中，vector 的表现已经足够优秀。

常见陷阱与最佳实践

作为一名开发者，在使用邻接表时，有几个“坑”是你需要警惕的。

• 索引越界：这是最常见的错误。在添加边之前，务必检查 $u$ 和 $v$ 是否在 $[0, V-1]$ 的范围内。虽然上面的示例代码中做了简单的检查，但在复杂的算法中（如 DFS 或 BFS），很容易疏忽这一点。

• 无向图的双向添加遗忘：如果你在实现无向图的 Dijkstra 算法时忘记添加反向边，你会发现只有部分节点可达，导致算法结果错误。一个好的习惯是将双向操作封装在 addEdge 内部，避免每次手动写两遍。

• 自环和平行边：

* 自环：即 $u = v$ 的边。大多数代码能处理这种情况，但要注意它会对遍历逻辑产生影响（如访问标记的设置）。

* 平行边：即两个顶点之间有多条相同的边。如果不希望存在平行边，可以在添加前使用 INLINECODEa6b39589 检查邻居是否已存在，或者使用 INLINECODEb9d92755 代替 vector（这会稍微降低插入性能到 $O(\log E)$）。

• 字符串顶点的处理：现实世界的数据往往不是整数（如城市名“Beijing”）。不要尝试直接用 INLINECODE0f63ade1 作为邻接表，这会极大地降低性能。最佳实践是使用 INLINECODE73cae1f7 建立从字符串到整数的映射，然后继续使用整数作为邻接表的索引。

性能分析与复杂度

为了让你在系统设计面试中更有底气，我们需要量化邻接表的性能。

• 空间复杂度：$O(V + E)$。我们需要 $V$ 个数组头，以及总共 $2E$ 个条目（对于无向图，每条边存两次；对于有向图，存 $E$ 次）。这比邻接矩阵的 $O(V^2)$ 要节省得多。
• 添加边：$O(1)$。直接 push_back 即可（假设 vector 不需要扩容）。
• 检查是否存在边：$O(k)$，其中 $k$ 是顶点的度数。你需要遍历该顶点的列表来查找。如果你需要频繁检查边是否存在，且顶点度数很高，可能需要考虑邻接矩阵或使用哈希表优化邻接表。
• 遍历所有邻居：$O(k)$。这是邻接表最擅长的操作。

总结

在今天的文章中，我们全面地探讨了如何在 C++ 中实现邻接表。从最基础的无向图、有向图，到更复杂的带权图，我们看到了邻接表作为一种灵活的数据结构，是如何优雅地解决图存储问题的。

掌握邻接表是解决更高级图算法（如 DFS、BFS、最短路径算法）的基石。希望你现在能够自信地写出清晰、高效且无内存泄漏的图结构代码。下次当你遇到一个看似复杂的网络连接问题时，记得先画出一个邻接表，思路往往会豁然开朗。

你可以尝试扩展示例代码，实现一个基于 std::map 的字符串顶点图，或者尝试在邻接表上实现一个简单的深度优先搜索（DFS）遍历，这将进一步巩固你的理解。