CC++ & Algorithm

邻接表

较难5
语言版本：C++Python
概述：邻接表像每个人的朋友名单，只记录真正的朋友，节省空间，适合边少的图。

邻接表：用“朋友名单”来存储图

假如班里100个同学，但每个人只跟很少几个人是朋友。如果用一个100行×100列的表格（邻接矩阵）来记录谁跟谁是朋友，那表格里大多数格子都是“0”——表示“不是朋友”，白白浪费了纸。这时候，我们换一种方式：每个人手里拿一张“好友名单”，只写真正朋友的名字。没有朋友的人，名单就是空的。这个思想就是邻接表。

在计算机里，图（Graph）就是由一堆“顶点”（比如同学）和一些“边”（比如朋友关系）组成的。邻接表是存储图的一种常用方法，特别适合边数远远少于顶点数平方的图——这种图叫稀疏图。咱们的生活中，同学关系、地铁线路、网页链接大多都是稀疏图。

为什么用邻接表？——从邻接矩阵的“浪费”说起

想想邻接矩阵是什么：它是一个二维数组，假设有 n 个顶点，矩阵有 n 行 n 列，格子 [i][j] 存 1 表示顶点 i 和 j 有边，存 0 表示没边。如果 n=100，矩阵有 10000 个格子，但你可能总共只有 200 条朋友关系，那么 9800 个格子都是 0，太浪费了！

而邻接表只存存在的边：每个顶点有一个容器，里面只放它的邻居编号。比如顶点0的朋友是1和3，那么容器里就只放1和3，没有多余的0。边越多，容器越长；边少，容器就短。内存占用精确等于边的数量（无向图每条边会存两次，所以总容器元素个数 = 2×边数）。

那用邻接表有什么优缺点呢？

  • ✅ 优点：空间小（适合稀疏图），遍历某个顶点的所有邻居非常快（直接遍历容器）。
  • ❌ 缺点：判断两个顶点之间有没有边，需要在一个容器里挨个查找，比邻接矩阵（直接看格子）慢。

邻接表的结构

每个顶点对应一个 列表（list） 或 动态数组（vector），里面按顺序存放与它直接相连的顶点编号。

例如下图（无向图，5个顶点，4条边）：

0 — 1 — 2
    |
    3 — 4
  • 顶点0的朋友：1
  • 顶点1的朋友：0, 2, 3
  • 顶点2的朋友：1
  • 顶点3的朋友：1, 4
  • 顶点4的朋友：3

用邻接表表示：

顶点0 -> [1]
顶点1 -> [0, 2, 3]
顶点2 -> [1]
顶点3 -> [1, 4]
顶点4 -> [3]

在C++里，通常用 vector<vector<int>> 来实现：一个大的vector，里面每个元素又是一个vector<int>，用于存储邻居编号。

C++中实现邻接表——手把手写代码

我们来搭建一个邻接表。首先定义一个 vector<vector<int>> adj(n)，其中 n 是顶点数。adj[0] 就是一个vector，用来装顶点0的邻居；adj[1] 装顶点1的邻居……以此类推。

添加边

如果是无向图（朋友是双向的），那么添加一条边 u–v 需要：

  • 在 adj[u] 里加入 v
  • 在 adj[v] 里加入 u

如果是有向图（比如粉丝关系，你关注我但我不一定关注你），则只加 adj[u] 里加入 v 即可。

遍历邻居

想知道顶点 v 的所有朋友，直接遍历 adj[v] 这个vector，里面的每个元素都是邻居编号。

下面是一个完整的例子，我们用 5 个顶点（编号0~4），加上前面那张图的边。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5;                      // 顶点数（比如5个同学编号0~4）
    vector<vector<int>> adj(n);     // 邻接表：包含n个空vector

    // 添加4条无向边：
    adj[0].push_back(1);            // 0的好友：1
    adj[1].push_back(0);            // 1的好友：0（无向图要双向加）

    adj[1].push_back(2);            // 1的好友：2
    adj[2].push_back(1);            // 2的好友：1

    adj[1].push_back(3);            // 1的好友：3
    adj[3].push_back(1);            // 3的好友：1

    adj[3].push_back(4);            // 3的好友：4
    adj[4].push_back(3);            // 4的好友：3

    // 打印每个顶点的邻接表
    cout << "邻接表（每个顶点的朋友名单）:" << endl;
    for (int v = 0; v < n; v++) {
        cout << "顶点" << v << " -> ";
        for (int u : adj[v]) {      // 遍历v的朋友列表
            cout << u << " ";
        }
        cout << endl;
    }

    // 特别查看顶点1的朋友
    cout << "\n顶点1的朋友有：";
    for (int friend_id : adj[1]) {
        cout << friend_id << " ";
    }
    cout << endl;

    return 0;
}

输出：

邻接表（每个顶点的朋友名单）:
顶点0 -> 1 
顶点1 -> 0 2 3 
顶点2 -> 1 
顶点3 -> 1 4 
顶点4 -> 3 

顶点1的朋友有：0 2 3

可以看到，邻接表只存了实际存在的边，没有多余的空位置，所以非常节省内存。

生活中的例子：班级好友名单

假设我们班有6个同学（编号0~5），好朋友关系如下：

  • 0和1是好朋友
  • 0和2是好朋友
  • 1和3是好朋友
  • 3和4是好朋友
  • 5没有朋友（孤零零）

用邻接表，顶点5对应的vector是空的。这完美体现了“稀疏”——一个班里总有几个同学可能跟谁都不熟。

常见错误（新手容易踩的坑）

错误1：无向图只添加单向

许多新手写无向图时只加了一边，比如只写了 adj[u].push_back(v)，忘记写 adj[v].push_back(u)。结果遍历时发现 u 认识 v，但 v 不认识 u，数据就不对称了。

✅ 记住：无向图的边是双向的，两端都要加。

错误2：有向图混淆方向

有向图的边是单向的，比如“a 关注 b”只应加在 a 的列表里，不能加反向。如果写成双向，那就变成“互关”了。

错误3：索引越界

邻接表的大小是 n，顶点编号从0到 n-1。如果输入了大于等于 n 的顶点编号去访问 adj[big]，程序会崩溃（vector越界）。所以一定要确保顶点编号在合法范围内。

错误4：忘记初始化vector的大小

如果用 vector<vector<int>> adj; 而不指定大小，直接 adj[0].push_back(...) 会出错，因为 adj 还是空vector。必须先 adj.resize(n) 或者定义时就给大小 vector<vector<int>> adj(n);。

完整示例：读入顶点和边，构建邻接表并打印

下面是一个更通用的程序，可以让用户输入顶点数和边数，然后输入每条边的两个端点，程序自动构建邻接表。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;                        // n: 顶点数, m: 边数
    cout << "请输入顶点数 n 和边数 m（空格隔开）: ";
    cin >> n >> m;

    vector<vector<int>> adj(n);      // 邻接表，包含n个空列表

    cout << "请依次输入每条边的两个顶点编号（从0开始，空格隔开）:" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;                    // 边的两个端点
        cin >> u >> v;
        // 假设是无向图
        adj[u].push_back(v);         // u 认识 v
        adj[v].push_back(u);         // v 认识 u
    }

    cout << "\n邻接表如下：" << endl;
    for (int v = 0; v < n; v++) {
        cout << "顶点" << v << " -> ";
        if (adj[v].empty()) {
            cout << "(没有朋友)";
        } else {
            for (int neighbor : adj[v]) {
                cout << neighbor << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

运行示例：

请输入顶点数 n 和边数 m（空格隔开）: 5 4
请依次输入每条边的两个顶点编号（从0开始，空格隔开）:
0 1
1 2
1 3
3 4

邻接表如下：
顶点0 -> 1 
顶点1 -> 0 2 3 
顶点2 -> 1 
顶点3 -> 1 4 
顶点4 -> 3

如果某个顶点（比如顶点5不存在，因为我们只设了5个顶点编号0~4），输入5就会越界，程序可能崩溃。所以输入时要小心。

相关知识点指引

邻接表是很多图算法的基础，学会了它，你就可以继续学习：

  • 图的深度优先遍历（DFS）：从某个顶点出发，沿着邻接表一路往下走，像探险一样。
  • 图的广度优先遍历（BFS）：像把石子丢进水里，一圈一圈向外扩散，求最短路径常用。
  • 最短路径算法（Dijkstra、Floyd）等，都需要用到图的存储结构。

在GESP 7级考试中，邻接表常常作为处理图的标准工具出现。记住它的定义和使用，再结合遍历，你就能解决很多实际问题，比如查找好朋友的“朋友圈”、计算两个地铁站之间的换乘次数等。

邻接表就像每个人手里的朋友名单——简单、直观、不浪费，非常适合描述我们身边那些“稀疏”的关系。尝试自己写几个图来练习吧！

例题精讲

1单选题

对于一个有n个顶点和m条边的无向图，使用邻接表（vector实现）存储时，其空间复杂度为（ ）。

AO(n)
BO(m)
CO(n+m)
DO(n^2)
2判断题

使用邻接表存储图时，判断顶点u和顶点v之间是否有边可以直接相连的平均时间复杂度为O(1)。

3填空题
下面是用 vector<vector<int>> 实现的无向图邻接表结构。请补全 addEdge 函数，添加一条从 u 到 v 的无向边。

#include <vector>
using namespace std;
const int MAXN = 100;
vector<int> adj[MAXN];

void addEdge(int u, int v) {
    adj[u].push_back(v);
    ___;
}
4单选题

关于邻接表与邻接矩阵，下列说法正确的是（ ）。

A邻接表判断两个顶点是否相邻比邻接矩阵更快
B对于稠密图（边数接近n^2），邻接表比邻接矩阵更省空间
C对于稀疏图，邻接表的空间效率明显优于邻接矩阵
D邻接表遍历所有边的时间复杂度高于邻接矩阵
5填空题
以下是用邻接表实现的广度优先搜索（BFS）代码片段，起始顶点为 s。请补全遍历邻接表时，标记邻居已访问并入队的部分。

#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100;
vector<int> adj[MAXN];
bool visited[MAXN];

void bfs(int s) {
    queue<int> q;
    visited[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (___ ) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}