我们先想想，生活中有没有这样的场景：城市之间有公路连接，我们需要知道哪些城市之间可以通行；或者社交网络里，你和哪些人是朋友，朋友之间互相认识。这些都可以抽象成“图”的概念。
一、图的基本概念¶
在数据结构中，图（Graph） 是由一组顶点（Vertex）和一组边（Edge）组成的结构。顶点就是图中的“点”，边就是连接两个顶点的“线”。
- 顶点（Vertex）：也叫“节点”，是图的基本单元。比如社交网络中的每个人就是一个顶点。
- 边（Edge）：连接两个顶点的关系，可能是单向或双向的，可能有权重（比如公路的长度、航班的价格）。
图的分类¶
图有很多种类型，初学者需要了解最基础的两种：
1. 有向图（Directed Graph）：边是有方向的。例如，微博的关注关系（你关注某人，不代表对方关注你）。
2. 无向图（Undirected Graph）：边是无方向的。例如，微信好友关系（双向）。
另外，还有有权图和无权图：
- 有权图：边带有权重（数值），比如“城市A到城市B的距离是100公里”。
- 无权图：边没有权重，只有连接关系（比如社交网络的好友关系，只关心是否认识）。
二、邻接表表示法：为什么需要它？¶
表示图的方法有很多，最常见的是邻接矩阵和邻接表。邻接矩阵是一个二维数组，用adj[i][j]表示顶点i和j之间是否有边（1表示有，0表示无）。但邻接矩阵有个缺点：当图比较稀疏（边数远小于顶点数的平方）时，会浪费大量空间。例如，1000个顶点的图，邻接矩阵需要1000×1000=100万个位置，而如果只有100条边，大部分位置都是0。
邻接表（Adjacency List） 是更高效的表示方法：它只存储实际存在的边，空间效率更高。核心思想是：每个顶点对应一个列表，存储与它直接相连的所有顶点。
三、邻接表的具体结构¶
以无向图为例，假设顶点0、1、2、3，边的连接关系如下：
- 顶点0连接顶点1、2、3
- 顶点1连接顶点0、2
- 顶点2连接顶点0、1、3
- 顶点3连接顶点0、2
那么邻接表的结构可以表示为：
顶点0的邻接表：[1, 2, 3] # 0连接1、2、3
顶点1的邻接表：[0, 2] # 1连接0、2
顶点2的邻接表：[0, 1, 3] # 2连接0、1、3
顶点3的邻接表：[0, 2] # 3连接0、2
用数组表示的话，邻接表可以写成：
adj = [
[1, 2, 3], # 顶点0的邻接点
[0, 2], # 顶点1的邻接点
[0, 1, 3], # 顶点2的邻接点
[0, 2] # 顶点3的邻接点
]
有向图的邻接表¶
如果是有向图（比如顶点0→1，顶点1→2，顶点2→0），邻接表只需要存储每个顶点的“出边”：
顶点0的邻接表：[1, 2] # 0指向1和2
顶点1的邻接表：[2] # 1指向2
顶点2的邻接表：[0] # 2指向0
顶点3的邻接表：[] # 3没有出边
四、邻接表的实现（以无向图为例）¶
用代码实现邻接表时，最常用的方式是：
- 用一个数组（或列表）存储所有顶点的邻接信息，数组的每个元素对应一个顶点。
- 每个顶点的邻接信息用一个列表（或链表）存储。
Python实现示例¶
# 假设顶点数为4（0,1,2,3）
num_vertices = 4
adj = [[] for _ in range(num_vertices)] # 初始化邻接表，每个顶点对应一个空列表
# 添加边（无向图，每条边(u,v)要同时添加u到v和v到u）
edges = [(0,1), (0,2), (0,3), (1,2), (2,3)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # 无向图，双向添加
print(adj) # 输出：[[1,2,3], [0,2], [0,1,3], [0,2]]
有权图的邻接表¶
如果是有权图，邻接表的每个元素可以存储“邻接点+权重”的元组：
# 有权图例子：顶点0到1的边权重是5，0到2的权重是3，0到3的权重是8
edges = [(0,1,5), (0,2,3), (0,3,8), (1,2,2), (2,3,1)]
adj_weighted = [[] for _ in range(num_vertices)]
for u, v, w in edges:
adj_weighted[u].append((v, w))
adj_weighted[v].append((u, w)) # 无向图双向
print(adj_weighted)
# 输出：[[(1,5), (2,3), (3,8)], [(0,5), (2,2)], [(0,3), (1,2), (3,1)], [(0,8), (2,1)]]
五、邻接表的优缺点¶
- 优点：
- 空间效率高：只存储实际存在的边，空间复杂度为O(V+E)（V是顶点数，E是边数），适合稀疏图。
- 遍历方便：可以快速访问某个顶点的所有邻接点。
-
插入和删除边也很方便。
-
缺点：
- 查找两个顶点之间是否有边需要遍历邻接表，时间复杂度为O(d)（d是该顶点的度数）。
- 对于完全图（边数接近V²），邻接表可能不如邻接矩阵高效（但这种情况较少见）。
总结¶
图是数据结构中非常重要的概念，而邻接表是表示图的高效方法，尤其适合稀疏图。掌握邻接表的表示方法，不仅能帮助我们理解图的存储逻辑，还能为后续学习图的遍历算法（如BFS、DFS）和最短路径算法打下基础。
希望这篇指南能帮助你快速入门图的基本概念和邻接表表示法。实践中，可以尝试用邻接表实现简单的图操作，比如遍历所有邻接点，或者判断两个顶点是否相连。