C++邻接表详解（图的邻接表表示法完整入门教程）

为什么选择C++实现邻接表？

C++提供了强大的标准模板库（STL），如 vector、list 等容器，可以非常方便地构建邻接表。同时，C++性能高、控制力强，是学习数据结构和算法的理想语言。掌握C++图数据结构的实现，对面试和项目开发都大有裨益。

邻接表的基本结构

假设图中有 V 个顶点（编号通常从 0 到 V-1），我们可以用一个大小为 V 的数组（或 vector）来表示整个图，其中每个元素是一个列表，存储该顶点的所有邻居。

例如，对于一个无向图：

• 顶点 0 连接到 1 和 2
• 顶点 1 连接到 0 和 3
• 顶点 2 连接到 0
• 顶点 3 连接到 1

其邻接表表示如下：
0: [1, 2]
1: [0, 3]
2: [0]
3: [1]

C++代码实现邻接表

下面我们用 C++ 的 vector<vector<int>> 来实现一个简单的邻接表。这种方式简洁高效，适合大多数场景。

#include <iostream>#include <vector>using namespace std;// 图类（使用邻接表表示）class Graph {private:    int V; // 顶点数量    vector<vector<int>> adjList; // 邻接表public:    // 构造函数    Graph(int vertices) {        V = vertices;        adjList.resize(V);    }    // 添加边（无向图）    void addEdge(int u, int v) {        adjList[u].push_back(v);        adjList[v].push_back(u); // 无向图需双向添加    }    // 打印邻接表    void printGraph() {        for (int i = 0; i < V; ++i) {            cout << "顶点 " << i << ": ";            for (int neighbor : adjList[i]) {                cout << neighbor << " ";            }            cout << endl;        }    }};// 主函数示例int main() {    Graph g(4); // 创建含4个顶点的图    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 3);    cout << "邻接表表示如下：\n";    g.printGraph();    return 0;}  

上述代码定义了一个 Graph 类，使用 vector<vector<int>> 作为邻接表。通过 addEdge 方法添加边，并通过 printGraph 打印整个图的结构。

扩展：有向图与带权图

如果你要表示有向图，只需在 addEdge 中只添加单向边：

void addEdge(int u, int v) {    adjList[u].push_back(v); // 仅从 u 指向 v}  

对于带权图（每条边有权重），可以将邻接表改为存储 pair（顶点, 权重）：

vector<vector<pair<int, int>>> adjList; // pair<neighbor, weight>// 添加带权边void addEdge(int u, int v, int weight) {    adjList[u].push_back(make_pair(v, weight));}  

总结

通过本教程，你已经掌握了如何用 C++ 实现图的邻接表表示法。无论是无向图、有向图还是带权图，邻接表都是一种灵活高效的存储方式。希望这篇邻接表实现教程能帮助你打下扎实的数据结构基础！

关键词回顾：C++邻接表、图的邻接表表示、C++图数据结构、邻接表实现教程。