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

你有没有在班级里记过“朋友名单”？比如你列出所有和你直接玩得好的同学的名字。如果每个同学都有一个这样的名单，那全班就能组成一张“朋友网”。在计算机里，这张网就是图（Graph），而每个顶点的“朋友名单”正是邻接表。

邻接表是一种存储图的方式：它为每个顶点准备一个列表，里面存放所有与该顶点直接相连的顶点。这样做既节省空间（只存实际存在的边），又方便快速找到某个点的所有邻居。Python 里实现起来特别简单——用一个列表，列表的每个位置又是一个小列表，这个小列表就对应那个顶点的邻居名单。

邻接表到底长什么样？

假设有 3 个小朋友：0 号、1 号、2 号。他们之间的友谊是：0 和 1 是朋友，1 和 2 是朋友。那么邻接表就是：

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

用 Python 代码表示，就是先创建一个长度为 3 的列表，每个位置放一个空列表，然后根据边的关系往里面添加邻居。

无向图（双向友谊）

友谊关系是双向的：如果 0 和 1 是朋友，那么 0 的名单里有 1，1 的名单里也要有 0。这就是无向图。

n = 3  # 顶点数量：0,1,2
adj_list = [[] for _ in range(n)]  # 创建空列表: [[], [], []]

edges = [(0, 1), (1, 2)]  # 所有边
for u, v in edges:
    adj_list[u].append(v)  # u 把 v 加进自己的名单
    adj_list[v].append(u)  # v 也把 u 加进自己的名单（无向图必须双向添加）

# 打印结果
print("无向图邻接表:")
for i in range(n):
    print(f"顶点{i}的邻居: {adj_list[i]}")

运行结果：

无向图邻接表:
顶点0的邻居: [1]
顶点1的邻居: [0, 2]
顶点2的邻居: [1]

有向图（单向关注）

如果关系是单向的，比如 0 给 1 发了私信（从 0 到 1），但 1 不回关，那就只需要加一次。这种叫有向图，边的方向很重要。

dig_adj = [[] for _ in range(n)]  # 同样先建空列表
dig_edges = [(0, 1), (1, 2)]       # 0->1, 1->2
for u, v in dig_edges:
    dig_adj[u].append(v)           # 只加一次，表示 u 指向 v

print("有向图邻接表:")
for i in range(n):
    print(f"顶点{i}的出边: {dig_adj[i]}")

运行结果：

有向图邻接表:
顶点0的出边: [1]
顶点1的出边: [2]
顶点2的出边: []

注意：这里只记录了“发出箭头”的边，所以叫做“出边”列表；如果要记录“入边”，就需要再建一个列表专门存指向自己的邻居。

邻接表比邻接矩阵好在哪？

邻接矩阵是另一种存储图的方式，像一个表格（二维数组），有边的地方填 1，没边的地方填 0。对于 3 个顶点，矩阵是 3×3 的样子。但假如有 1000 个顶点，却只有几对边，矩阵里会装满 0，浪费大量空间。而邻接表只存真实存在的边，特别省内存——就像你只记好朋友的名字，不会记全班所有人的名字（没朋友也列出来）。

邻接表找邻居快：直接看对应顶点的列表即可，时间复杂度 O(度数)，而矩阵需要遍历一行所有顶点，O(n)。

邻接表缺点：要判断两个顶点是否直接相连，需要遍历其中一个顶点的邻居列表，速度可能比矩阵慢（矩阵直接看 matrix[u][v] 是 1 还是 0 就行）。但对于大多数图算法（如遍历、最短路径），邻接表已经足够好用。

新手容易犯的错误

❌ 错误1：无向图只加了一边

# 错误的无向图构建
adj_list = [[] for _ in range(3)]
adj_list[0].append(1)  # 只加了0->1
# 忘记加 adj_list[1].append(0)

后果：从顶点 1 找朋友时找不到 0，关系变成单向。记住：无向图必须双向添加。

❌ 错误2：索引越界

如果顶点编号从 1 开始，但你创建的列表长度是 n，访问 adj_list[ n ] 就会报错。例如顶点有 1,2,3，你想用索引 1,2,3，但 Python 列表从 0 开始，所以你创建长度 n+1（让索引 0 闲置），或者全部偏移。最常见做法：顶点从 0 编号，省事。

❌ 错误3：忘记初始化列表

直接用 adj_list = [] 然后想 adj_list[0].append(1) 会报错，因为列表是空的，没有索引 0。必须先创建好每个顶点的空列表。

完整可运行示例：创建图并检查邻居

下面的代码创建了一个 4 个顶点的无向图，然后询问用户输入两个顶点，判断它们是否直接相连。

# 完整示例：邻接表建图 + 判断两点是否相邻
n = 4  # 顶点：0,1,2,3
adj = [[] for _ in range(n)]  # 邻接表

# 定义图的边
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)  # 无向图双向添加

# 打印所有顶点的邻居
print("邻接表内容：")
for i in range(n):
    print(f"顶点{i}的邻居: {adj[i]}")

# 询问用户想查哪两个顶点是否相连
u = int(input("请输入第一个顶点编号 (0~3): "))
v = int(input("请输入第二个顶点编号 (0~3): "))

# 判断 v 是否在 u 的邻居列表里
if v in adj[u]:
    print(f"是的！顶点{u}和顶点{v}直接相连。")
else:
    print(f"不，顶点{u}和顶点{v}没有直接边。")

运行示例（假设用户输入 0 和 3）：

邻接表内容：
顶点0的邻居: [1, 2]
顶点1的邻居: [0, 3]
顶点2的邻居: [0, 3]
顶点3的邻居: [1, 2]
请输入第一个顶点编号 (0~3): 0
请输入第二个顶点编号 (0~3): 3
不，顶点0和顶点3没有直接边。

相关知识点指引

• 图的遍历：学会用邻接表后，就可以写 深度优先搜索 (DFS) 和 广度优先搜索 (BFS)，像迷宫里找路一样。
• 最短路径：比如用 BFS 找两个顶点的最短距离（无权图），用 Dijkstra 算法 找带权图的最短路径。
• 邻接矩阵：当图很稠密（几乎每个顶点之间都有边）时，邻接矩阵反而更方便，判断连通性 O(1)。
• 有向图 vs 无向图：注意构建图时是否双向添加，以及后续算法的区别。

邻接表是图论学习的基石，像你的通讯录一样简单直观。快用它来存储你身边的各种关系图吧！