hello-algo 图论实战：基于邻接表（GraphAdjList）实现无向图的增删改查-育师

教程
文档
示例工程
教育

【免费下载链接】hello-algo

《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现

项目地址：https://gitcode.com/GitHub_Trending/he/hello-algo

点击查看免费下载

导读

本文围绕《Hello 算法》仓库中 graph_adjacency_list.md 这一可视化教学文档，深入讲解如何用「邻接表（adjacency list）」这一数据结构表示无向图，并完整实现顶点与边的增删操作。你将掌握GraphAdjList类的设计思路、核心 API 的时间复杂度，以及邻接表与邻接矩阵的取舍，并能基于 Python 源码 graph_adjacency_list.py 亲手运行一个完整的无向图示例。

为什么用邻接表表示图

图（graph）由顶点（vertex）和边（edge）组成，是自由度最高的一种非线性数据结构。在存储图时，业界主要有两种方案：邻接矩阵和邻接表。正如 graph.md 所述：

邻接矩阵用一个 $n \times n$ 矩阵表示图，$M[i,j]=1$ 表示顶点 $i$ 与顶点 $j$ 之间有边，空间复杂度为 $O(n^2)$；
邻接表用 $n$ 个链表表示图，第 $i$ 条链表存储顶点 $i$ 的所有邻接顶点，只存储实际存在的边，空间复杂度为 $O(n+m)$。

现实中图的边数通常远小于 $n^2$，因此邻接表在稀疏图上显著节省内存。下图展示了使用邻接表存储一个 5 顶点无向图的示例：

观察邻接表结构不难发现，它和哈希表中的「链式地址」非常相似。因此 graph.md 指出：当链表较长时，可将其转化为 AVL 树或红黑树，把查找效率从 $O(n)$ 优化到 $O(\log n)$；甚至可以转换为哈希表，将时间复杂度降至 $O(1)$。这正是本仓库实现方案的核心灵感——用「哈希表 + 列表」来模拟传统链表邻接表。

GraphAdjList 类的数据结构设计

本文主角是 graph_adjacency_list.md 中完整呈现的GraphAdjList类。其核心设计在源码 graph_adjacency_list.py 中清晰可见：

class GraphAdjList: """基于邻接表实现的无向图类""" def __init__(self, edges: list[list[Vertex]]): """构造方法""" # 邻接表，key：顶点，value：该顶点的所有邻接顶点 self.adj_list = dict[Vertex, list[Vertex]]() # 添加所有顶点和边 for edge in edges: self.add_vertex(edge[0]) self.add_vertex(edge[1]) self.add_edge(edge[0], edge[1])

与教科书式「链表数组」的邻接表不同，这里的实现做了两处工程化改造（graph_operations.md 中有专门说明）：

用动态数组（列表）代替链表，方便添加与删除顶点，并简化代码；
用哈希表存储邻接表，key为顶点实例，value为该顶点的邻接顶点列表。

为什么要用Vertex类实例作为 key 而不是列表索引？graph_operations.md 给出了关键理由：若与邻接矩阵一样用索引区分顶点，删除索引为 $i$ 的顶点后，需要遍历整个邻接表把所有大于 $i$ 的索引减 1，效率很低；而每个顶点是唯一的Vertex实例时，删除某个顶点后无需改动其他顶点。Vertex类的定义位于 vertex.py：

class Vertex: """顶点类""" def __init__(self, val: int): self.val = val def vals_to_vets(vals: list[int]) -> list["Vertex"]: """输入值列表 vals ，返回顶点列表 vets""" return [Vertex(val) for val in vals]

配套的vals_to_vets工具函数负责把[1, 3, 2, 5, 4]这样的值列表批量转换为Vertex对象列表，方便测试代码构造顶点。

核心操作逐一拆解

GraphAdjList提供了 5 个核心 API，下面结合源码逐项讲解其实现与复杂度。

size()：获取顶点数量

def size(self) -> int: """获取顶点数量""" return len(self.adj_list)

由于邻接表本身就是哈希表，顶点数量即哈希表的键数量，$O(1)$ 时间返回。

add_edge()：添加边

def add_edge(self, vet1: Vertex, vet2: Vertex): """添加边""" if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2: raise ValueError() # 添加边 vet1 - vet2 self.adj_list[vet1].append(vet2) self.adj_list[vet2].append(vet1)

前置校验：要求两个顶点都已存在于邻接表中，且不能是同一个顶点（无向简单图中不允许自环），否则抛出ValueError；
双向追加：因为是无向图，边vet1 - vet2等价于vet2 - vet1，必须同时向两个顶点的邻接列表追加对方；
在列表末尾追加元素的时间复杂度为 $O(1)$。

remove_edge()：删除边

def remove_edge(self, vet1: Vertex, vet2: Vertex): """删除边""" if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2: raise ValueError() # 删除边 vet1 - vet2 self.adj_list[vet1].remove(vet2) self.adj_list[vet2].remove(vet1)

与添加边对称，删除边同样需要双向操作。list.remove()需要先线性查找目标元素，因此在基于列表的实现中删除边的时间复杂度为 $O(n)$。

add_vertex()：添加顶点

def add_vertex(self, vet: Vertex): """添加顶点""" if vet in self.adj_list: return # 在邻接表中添加一个新链表 self.adj_list[vet] = []

如果顶点已存在则直接返回（幂等操作）；
否则在哈希表中新增一个键值对，值为空列表，表示「暂无任何邻接顶点」，时间复杂度 $O(1)$。

remove_vertex()：删除顶点

def remove_vertex(self, vet: Vertex): """删除顶点""" if vet not in self.adj_list: raise ValueError() # 在邻接表中删除顶点 vet 对应的链表 self.adj_list.pop(vet) # 遍历其他顶点的链表，删除所有包含 vet 的边 for vertex in self.adj_list: if vet in self.adj_list[vertex]: self.adj_list[vertex].remove(vet)

删除顶点是操作中最复杂的一个，分两步：

从哈希表中弹出该顶点对应的列表，删除顶点本身；
遍历其余所有顶点的邻接列表，把包含vet的条目逐一移除，即删除所有与vet相连的边。

因为需要遍历全图，时间复杂度为 $O(n+m)$。这正是使用Vertex实例做 key 的价值所在：删除顶点后，其余顶点的 key 完全不受影响，无需像索引方案那样做大规模下标重排。

Driver Code：完整运行一个无向图示例

为了让读者快速验证，文档末尾（与 graph_adjacency_list.py 一致）附带了完整的 Driver Code，可一键运行：

"""Driver Code""" if __name__ == "__main__": # 初始化无向图 v = vals_to_vets([1, 3, 2, 5, 4]) edges = [ [v[0], v[1]], [v[0], v[3]], [v[1], v[2]], [v[2], v[3]], [v[2], v[4]], [v[3], v[4]], ] graph = GraphAdjList(edges) print("\n初始化后，图为") graph.print() # 添加边 # 顶点 1, 2 即 v[0], v[2] graph.add_edge(v[0], v[2]) print("\n添加边 1-2 后，图为") graph.print() # 删除边 # 顶点 1, 3 即 v[0], v[1] graph.remove_edge(v[0], v[1]) print("\n删除边 1-3 后，图为") graph.print() # 添加顶点 v5 = Vertex(6) graph.add_vertex(v5) print("\n添加顶点 6 后，图为") graph.print() # 删除顶点 # 顶点 3 即 v[1] graph.remove_vertex(v[1]) print("\n删除顶点 3 后，图为") graph.print()

运行流程依次演示了 5 个关键场景：

步骤	操作	说明
1	`GraphAdjList(edges)`	传入 6 条边初始化 5 顶点无向图
2	`graph.add_edge(v[0], v[2])`	添加边 1-2
3	`graph.remove_edge(v[0], v[1])`	删除边 1-3
4	`graph.add_vertex(v5)`	新增值为 6 的顶点（暂时孤立）
5	`graph.remove_vertex(v[1])`	删除顶点 3 及其全部关联边

类中的print()方法（graph_adjacency_list.py）会以顶点值: [邻接顶点值列表]的格式打印邻接表，方便直观核对每次操作前后图的结构变化。下图展示了初始化邻接表的完整步骤动画截图：

运行本示例前需先按仓库说明配置 Python 环境，然后执行：

python codes/python/chapter_graph/graph_adjacency_list.py

时间复杂度全景：邻接表 vs 邻接矩阵

graph_operations.md 给出了设图共有 $n$ 个顶点、$m$ 条边时两种表示法的完整效率对比表：

操作	邻接矩阵	邻接表（链表）	邻接表（哈希表）
判断是否邻接	$O(1)$	$O(n)$	$O(1)$
添加边	$O(1)$	$O(1)$	$O(1)$
删除边	$O(1)$	$O(n)$	$O(1)$
添加顶点	$O(n)$	$O(1)$	$O(1)$
删除顶点	$O(n^2)$	$O(n + m)$	$O(n)$
内存空间占用	$O(n^2)$	$O(n + m)$	$O(n + m)$

其中「邻接表（链表）」对应传统教科书实现，「邻接表（哈希表）」对应本文GraphAdjList的工程化版本。从表中可以看到：

邻接矩阵擅长边操作：判断、添加、删除边都只需一次数组访问，体现「以空间换时间」；
邻接表擅长顶点操作：添加顶点只需 $O(1)$，且内存只随实际边数增长，体现「以时间换空间」；
本仓库实现的哈希表版邻接表把「判断是否邻接」也提升到了 $O(1)$，综合效率更均衡。

跨语言实现：从 Python 到 C 与 Go

邻接表思想在不同语言中有不同落地方式，仓库提供了多语言对照实现，可以作为学习参考：

C 语言：在 graph_adjacency_list.c 中保留了最贴近教科书的结构——用AdjListNode单向链表节点 + 固定大小heads[MAX_SIZE]数组实现「链表数组」，addEdgeHelper采用头插法添加边（L65-L71），删除边则需在链表中遍历定位（removeEdgeHelper），还涉及手动的内存释放，是理解邻接表底层内存模型的最佳入口；
Go 语言：在 graph_adjacency_list.go 中与 Python 一致采用map[Vertex][]Vertex的「哈希表 + 切片」结构，删除边通过DeleteSliceElms工具函数完成；
Java / C++ / TypeScript 等：codes/目录下各语言均有同名graph_adjacency_list文件，实现思路一致，方便横向对比不同语言的集合类型写法。

从源码结构可以看出：无论哪种语言，「双向维护无向边 + 删除顶点时遍历清理关联边」都是邻接表实现必须遵守的两条核心准则。

邻接表是图遍历算法的基础设施

GraphAdjList不只是孤立的数据结构，它直接支撑着仓库中两个图的遍历算法：

广度优先遍历（BFS）：graph_bfs.py 借助队列实现「由近及远」的遍历，核心语句for adj_vet in graph.adj_list[vet]正是通过邻接表快速取得当前顶点的全部邻居，配合visited哈希集合防止重复访问；
深度优先遍历（DFS）：graph_dfs.py 采用递归方式沿邻接表逐层深入，同样依赖graph.adj_list[vet]获取邻接顶点。

正是因为邻接表能够以 $O(\text{度数})$ 的代价枚举某个顶点的所有邻居，BFS/DFS 才能达到 $O(n+m)$ 的总体遍历复杂度；若改用邻接矩阵，遍历单个顶点的邻居需要扫描一整行，效率会明显下降。这再次印证了邻接表在稀疏图场景下的综合优势。