图的邻接表实现详解

你写过同学通讯录小程序吗？或者做过校园地图导航的小功能？这类需求里，人与人之间的“好友关系”，或路口与路口之间的“连通道路”，本质上都不是一条条线性排列的数据——它们更适合用“图”来建模。而邻接表，就是程序员最常用、也最贴近直觉的一种图存储方式。

为什么不用二维数组？

有人一上来就想用二维数组 graph[i][j] 表示顶点 i 和 j 是否相连。这叫邻接矩阵，简单直接，但有个硬伤：如果全校 5000 个学生，只有一小部分互为好友，那这个 5000×5000 的数组，99% 的空间都在存 0。内存哗哗浪费，遍历还慢。

邻接表不这么干。它给每个顶点配一个“小本本”，只记它真正连着谁。像班长整理小组名单：1 号同学的好友是 [3, 7, 12]，2 号同学的好友是 [5, 8]……没连上的，压根不写。

怎么动手写一个？

以 C++ 为例，核心思路就三步：

定义节点结构：存邻居编号 + 指向下个节点的指针；
准备一个数组（或 vector），每个元素是一个链表头指针；
添加边时，把对方编号插到自己的链表头部（或尾部）。

下面是个极简可运行的版本：

struct Node {
    int to;
    Node* next;
    Node(int t) : to(t), next(nullptr) {}
};

vector<Node*> adj(100); // 假设最多 100 个顶点

// 添加无向边 u-v
void addEdge(int u, int v) {
    Node* newNode = new Node(v);
    newNode->next = adj[u];
    adj[u] = newNode;

    newNode = new Node(u); // 无向图要双向加
    newNode->next = adj[v];
    adj[v] = newNode;
}

Python 玩得更轻巧，直接用 list 存列表：

# 初始化 100 个空列表
adj = [[] for _ in range(100)]

# 添加无向边 u-v
def add_edge(u, v):
    adj[u].append(v)
    adj[v].append(u)

实际用起来啥感觉？

比如你要查“张三”都跟谁有微信好友关系，直接看 adj[张三] 这个列表就行，不用扫完整张表。想给张三新拉个好友李四？往他列表末尾 append 一下，O(1) 就搞定。要是用邻接矩阵，你还得先定位到第张三行、第李四列，再改一个数——看似一样快，但内存占用和缓存友好度差远了。

当然，邻接表也有软肋：判断“张三和王五是不是好友”，得遍历张三的好友列表找一遍，最坏 O(n)；而邻接矩阵查个 graph[张三][王五] 是稳稳的 O(1)。所以选哪种，真得看你的场景里，“查连通性”多，还是“遍历邻居”多。

小提醒：手写链表容易忘释放内存，工程中更推荐用 vector<vector<int>> 或者 vector<list<int>>，既清晰又安全。算法题里手动 new/delete 练练手感可以，上线代码别这么干。

图的邻接表实现：用链表存关系，内存省、增删快

为什么不用二维数组？

怎么动手写一个？

实际用起来啥感觉？