CC++ & Algorithm

图的表示——邻接表

较难5
语言版本：C++
概述：为每个顶点拉一个“朋友名单”，只记录存在的边，像通讯录一样节省空间。

图的邻居名单：邻接表

想象一下，你要记录全班同学的朋友关系。如果用一张大表格，每个格子都要填“认识”或“不认识”，即使两个人根本不说话也得写个“0”，多浪费纸啊！更聪明的做法是：每个同学只写自己的朋友名单。这就是邻接表——像通讯录一样，只记录存在的关系，节省空间又好用。

什么是邻接表？

邻接表的核心思想是：为图的每个顶点准备一个“朋友名单”，名单里只存放它能直接到达的邻居顶点编号。

比如有三个顶点 0、1、2，有向边是 0→1 和 1→2，那么邻接表长这样：

  • 顶点0的朋友：[1]
  • 顶点1的朋友：[2]
  • 顶点2的朋友：[ ]（空名单）

每个订单就像一张便签条，上面写着“我能走到哪些人”。如果有向边变成无向边（双向朋友），那每一条边要同时写到两个人的名单里，比如0和1是朋友，那么0的名单里加1，1的名单里也加0。

用C++实现邻接表

在C++中，我们最常用 vector<int> adj[n] 来表示邻接表。这里的 adj 是一个数组，数组的每个元素 adj[i] 就是一个 vector<int>（动态数组），可以不断往里添加邻居顶点编号。

代码模板（有向图）

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

int main() {
    int n = 3; // 顶点数（比如3个同学）
    vector<int> adj[n]; // 邻接表，每个顶点一个动态数组

    // 添加有向边 0->1, 1->2
    adj[0].push_back(1); // 顶点0的朋友名单里加入1
    adj[1].push_back(2); // 顶点1的朋友名单里加入2

    // 输出每个顶点的邻居（朋友名单）
    for (int i = 0; i < n; i++) {
        cout << i << " 的邻居: ";
        for (int j : adj[i]) { // 遍历顶点i的名单
            cout << j << " ";
        }
        cout << endl;
    }
    return 0;
}

运行结果：

0 的邻居: 1 
1 的邻居: 2 
2 的邻居:

无向图的邻接表

如果边是无向的（比如朋友关系是双向的），添加边时要双向操作。假设0和1是朋友，1和2是朋友，代码变成：

int n = 3; // 顶点数
vector<int> adj[n]; // 邻接表

// 添加无向边 0-1 和 1-2
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

// 输出结果：0的邻居有1，1的邻居有0和2，2的邻居有1

带权边的邻接表（比如距离、费用）

有时边上有权重，比如从家到学校的距离，或者买东西花的钱。这时可以用 vector<pair<int,int>>，每个元素是一个 pair，第一个数是邻居编号，第二个数是权重。

int n = 3; // 顶点数
vector<pair<int,int>> adj[n]; // 邻接表，每个元素是（邻居，权重）

// 添加带权有向边：0->1 权重5，1->2 权重3
adj[0].push_back({1, 5}); // 从0到1距离5
adj[1].push_back({2, 3}); // 从1到2距离3

// 输出带权邻居
for (int i = 0; i < n; i++) {
    cout << i << " 的邻居及距离: ";
    for (auto p : adj[i]) {
        cout << "(" << p.first << "," << p.second << ") ";
    }
    cout << endl;
}

邻接表 vs 邻接矩阵：什么时候用哪个？

我们可以把图想象成班级的同学关系网络。

  • 邻接矩阵：像一张大表格，行和列都是所有人的编号，交叉处填1（认识）或0（不认识）。全班50人，就要写2500个格子，即使大多数人彼此不认识，也要填一堆0。浪费纸，但查两个人是否认识很快（直接看交叉点）。
  • 邻接表：只给每个人一张朋友名单。全班50人，平均每人朋友10个，总共只需写500个名字。节省大量空间，但查两个人是否认识，得翻一个人的名单看看有没有对方，稍微慢一点。

CSP-J竞赛中的选择原则：

  • 如果边数很少（稀疏图），比如顶点数1000，边数只有2000，用邻接表更省空间（O(顶点数+边数)），而且遍历所有边很方便。
  • 如果边数接近顶点数的平方（稠密图），比如完全图，每条边都存在，邻接表反而更复杂（每条边要存两遍），此时邻接矩阵更直观。

实际比赛中，大多数图都是稀疏的，所以邻接表是更常用的选择。

新手容易犯的错误

  1. 忘记区分有向和无向：无向图要双向添加，只加单向会导致从A能找到B，但从B找不到A，程序出错。
  2. 数组越界：如果用 vector<int> adj[n]，顶点编号从0到n-1，千万不要访问 adj[n] 或 adj[-1]。添加边前最好检查编号是否合法。
  3. 忘记初始化：用 vector<int> adj[n] 没问题，但如果用 vector<vector<int>> adj(n) 要小心空指针。推荐直接用数组形式的 vector<int> adj[n]。
  4. 遍历时混淆索引：比如 for (int j : adj[i]) 中 j 是邻居顶点编号，不是顶点索引，可以直接用。
  5. 带权图忘了pair：如果边有权重，却用 vector<int>，导致权重信息丢失。

完整示例：用邻接表建立无向图

下面是一个完整的程序，读取顶点数和边数，然后添加无向边，最后输出每个顶点的度（朋友数量）。

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

int main() {
    int n = 5; // 顶点数（比如5个小朋友）
    int m = 4; // 边数（比如4对朋友关系）
    vector<int> adj[n]; // 邻接表

    // 假设输入的朋友关系：0-1, 0-2, 1-3, 3-4
    // 这里手动添加，实际可以改成从键盘读入
    adj[0].push_back(1);
    adj[1].push_back(0);
    adj[0].push_back(2);
    adj[2].push_back(0);
    adj[1].push_back(3);
    adj[3].push_back(1);
    adj[3].push_back(4);
    adj[4].push_back(3);

    // 输出每个顶点的度（朋友个数）
    cout << "每个顶点的朋友数量:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "顶点" << i << " 有 " << adj[i].size() << " 个朋友";
        cout << "（名单: ");
        for (int j : adj[i]) {
            cout << j << " ";
        }
        cout << ")" << endl;
    }
    return 0;
}

输出：

每个顶点的朋友数量:
顶点0 有 2 个朋友（名单: 1 2 )
顶点1 有 2 个朋友（名单: 0 3 )
顶点2 有 1 个朋友（名单: 0 )
顶点3 有 2 个朋友（名单: 1 4 )
顶点4 有 1 个朋友（名单: 3 )

相关知识点指引

  • 图的遍历：学完邻接表，下一步可以学习用DFS（深度优先搜索）或BFS（广度优先搜索）来走遍整个图，比如找一条路径或判断连通性。
  • 最短路径：如果边有权重，可以用Dijkstra算法或Floyd算法，而邻接表是Dijkstra的常用数据结构。
  • 邻接矩阵：作为对比，了解另一种表示方法，知道什么时候用矩阵更方便。
  • 链式前向星：更高级的静态邻接表实现，适合大规模图，但初学者先用 vector 最合适。

邻接表就像每个人手中的小本子，记录自己认识的朋友——简单、直接、省地方。写代码的时候，多加几条边、多试几个例子，很快就能掌握它啦！

例题精讲

1单选题

对于一个包含n个顶点和m条边的无向图（n和m都是正整数），使用邻接表存储时，其空间复杂度最接近以下哪个？

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

对于有向图，使用邻接表存储时，每个有向边只会出现在起始顶点的邻接表中，而不会出现在终止顶点的邻接表中。

3填空题
以下C++代码使用邻接表存储一个无向图，请补全添加边的函数addEdge。假设图有n个顶点（编号0到n-1），邻接表用vector<int> adj[n]表示。

#include <vector>
using namespace std;

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

以下关于邻接表存储图的描述，错误的是哪一项？

A邻接表适合存储稀疏图，可以节省存储空间
B判断两个顶点之间是否有边，邻接表的时间复杂度为O(度)或O(1)（通过哈希优化），但最坏情况下不如邻接矩阵快
C邻接表的边删除操作比邻接矩阵更简单
D在无向图中，邻接表存储的边数是边数的两倍
5填空题
以下代码遍历邻接表以输出图中所有的边。假设有n个顶点，邻接表为vector<int> adj[n]。要求每条无向边只输出一次（例如输出"(0,1)"而不是"(1,0)"）。请补全内层循环的if条件。

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

void printEdges(vector<int> adj[], int n) {
    for (int u = 0; u < n; ++u) {
        for (int v : adj[u]) {
            if (___) {
                cout << "(" << u << "," << v << ")" << endl;
            }
        }
    }
}