用邻接表给图“建朋友圈”——节省空间又好用的图存储方法

想象一下，你的班级里有 30 个同学，如果让你记录每个同学的好朋友名单，最直接的办法是给每个同学发一张纸，纸上写着他所有好朋友的名字。这就是邻接表的核心思路：每个顶点（同学）都有一张“朋友名单”，里面存的是和他直接相连的顶点（朋友）。在编程里，我们常用列表的列表或者字典来实现邻接表，专门用来存储那些“边很少”的图（比如社交网络里，一个人可能只有几十个好友，而不是和全班每个同学都相连）。它比邻接矩阵（一个大表格）要节省很多空间，也是后续学习深度优先搜索、最短路径等图算法的基础。

生活中的例子：通讯录 vs 邻接表

你手机里的通讯录，每个联系人的名字后面都会存着他的电话号码。邻接表就像这样：每个顶点是“联系人”，它后面跟着一个列表，里面是该联系人的“邻居”（有直接边相连的顶点）。如果用邻接矩阵，就需要一个巨大的表格，哪怕两个人之间没有联系，也要占一个格子存“0”。所以当图中的边数远小于顶点数的平方（即“稀疏图”）时，邻接表就特别节省空间。

用列表的列表实现邻接表（最常用的方法）

假设我们有一个无向图，有 5 个顶点（编号 0 到 4），边是：0–1，0–2，1–3，3–4。下面用 Python 的“列表的列表”来建邻接表。

n = 5                     # 顶点个数
adj = [[] for _ in range(n)]   # 每个顶点初始一个空列表，存放它的邻居

# 添加边：每条边 (u, v) 表示 u 和 v 相连
edges = [(0, 1), (0, 2), (1, 3), (3, 4)]
for u, v in edges:
    adj[u].append(v)      # 把 v 加到 u 的邻居列表里
    adj[v].append(u)      # 无向图要双向添加，把 u 也加到 v 的邻居里

# 打印每个顶点的邻居
for i in range(n):
    print(f"顶点{i}的邻居：{adj[i]}")

输出：

顶点0的邻居：[1, 2]
顶点1的邻居：[0, 3]
顶点2的邻居：[0]
顶点3的邻居：[1, 4]
顶点4的邻居：[3]

你看，每个顶点后面跟的列表就是它的“朋友名单”。比如顶点 0 的好朋友是 1 和 2。

用字典实现邻接表（顶点不是连续整数时更方便）

如果图的顶点不是 0,1,2,... 这样的连续整数，而是像城市名、同学名字这样的字符串，用列表就不太方便了。这时候可以用字典：字典的键是顶点，值是对应的邻居列表。

举个例子：你和你的几个好朋友之间互相认识，用名字表示顶点。

# 用字典实现邻接表
adj_dict = {}                         # 空字典

# 定义添加边的函数
def add_edge(dict_graph, u, v):
    if u not in dict_graph:
        dict_graph[u] = []            # 如果 u 还没出现过，先建一个空列表
    if v not in dict_graph:
        dict_graph[v] = []            # 同样处理 v
    dict_graph[u].append(v)           # 添加邻居 v 到 u 的列表
    dict_graph[v].append(u)           # 无向图双向加

# 添加一些朋友关系
add_edge(adj_dict, "小明", "小红")
add_edge(adj_dict, "小明", "小刚")
add_edge(adj_dict, "小红", "小丽")
add_edge(adj_dict, "小刚", "小丽")

# 打印每个顶点的邻居
for person, friends in adj_dict.items():
    print(f"{person}的朋友：{friends}")

输出：

小明的朋友：['小红', '小刚']
小红的朋友：['小明', '小丽']
小刚的朋友：['小明', '小丽']
小丽的朋友：['小红', '小刚']

这种字典写法在竞赛中也经常用，特别是当顶点范围很大但实际出现的顶点很少时（比如网络爬虫里的网址）。

有向图的邻接表：单向朋友（关注关系）

如果你在玩一个游戏，玩家之间可以“关注”别人（比如 A 关注了 B，但 B 不一定关注 A），这就是有向图。有向图的邻接表只按箭头方向添加边，不反向添加。

n = 5                     # 顶点个数
adj_d = [[] for _ in range(n)]   # 空列表

# 有向关系：0->1, 0->2, 1->3
edges_d = [(0, 1), (0, 2), (1, 3)]
for u, v in edges_d:
    adj_d[u].append(v)    # 只添加 u 到 v 的方向，不反向加

print("有向图的邻接表：", adj_d)
# 输出：有向图的邻接表：[[1, 2], [3], [], [], []]

注意：顶点 2、3、4 的邻居列表都是空的，因为没有人关注它们（或者它们没有发出关注）。如果我们想查谁关注了某个顶点（即入边），通常需要另外建一个“反向邻接表”。

邻接表的优点总结

节省空间：只存储实际存在的边。一个稀疏图（边数远小于 $n^2$ ）用邻接表只需要 $O(n+m)$ 的内存（ $n$ 个顶点， $m$ 条边），而邻接矩阵需要 $O(n^2)$ 。
方便遍历邻居：想找某个顶点的所有邻居，直接拿 adj[i] 就行，操作非常快，是 $O(\text{该顶点的度数})$ 。
容易添加新顶点：用字典实现时，随时可以添加一个新顶点。用列表实现时，如果预先知道顶点总数，一次性建好列表也很方便。

新手最容易犯的 3 个错误

错误 1：无向图只加单向

# 错误：只加了一次
for u, v in edges:
    adj[u].append(v)   # 忘记加 adj[v].append(u)

这样会造成顶点 v 的邻居列表里没有 u，导致图中关系不对称，后续遍历时会漏掉顶点。

错误 2：顶点编号越界

n = 5          # 顶点编号 0~4
adj = [[] for _ in range(n)]
edges = [(0, 5)]   # 5 超出了范围，会报 IndexError

所以添加边前要确保顶点编号在 0 到 n-1 之间，或者用字典避免这个限制。

错误 3：重复添加同一条边

如果数据中有重复的边（比如（0,1）出现了两次），邻接表里就会有两个 1，实际图里不应该有重边。解决方法：可以在添加前检查是否已经在列表中，或者用 set 代替 list（但注意 set 是无序的），或者直接用 if v not in adj[u] 判断。

完整可运行的示例：用邻接表存储一个班级的朋友关系

假设一个班级有 6 个同学（编号 0~5），他们的朋友关系如下（无向图）：
0 和 1、0 和 2、1 和 3、2 和 4、3 和 4、4 和 5。
我们建邻接表，然后打印每个同学的朋友名单，并统计有几个朋友。

# 完整示例：用邻接表存储班级朋友关系
n = 6                        # 6个同学
adj = [[] for _ in range(n)] # 每个同学的朋友列表

# 朋友关系列表
friends = [(0, 1), (0, 2), (1, 3), (2, 4), (3, 4), (4, 5)]

# 双向添加
for u, v in friends:
    adj[u].append(v)
    adj[v].append(u)

# 打印每个人的朋友数量和名字
for i in range(n):
    num_friends = len(adj[i])
    friend_list = adj[i]
    print(f"同学{i}有{num_friends}个朋友，他们是：{friend_list}")

输出：

同学0有2个朋友，他们是：[1, 2]
同学1有2个朋友，他们是：[0, 3]
同学2有2个朋友，他们是：[0, 4]
同学3有2个朋友，他们是：[1, 4]
同学4有3个朋友，他们是：[2, 3, 5]
同学5有1个朋友，他们是：[4]

邻接表