教程文档示例工程教育【免费下载链接】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(nm)$。现实中图的边数通常远小于 $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.pyclass 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(nm)$。这正是使用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 个关键场景步骤操作说明1GraphAdjList(edges)传入 6 条边初始化 5 顶点无向图2graph.add_edge(v[0], v[2])添加边 1-23graph.remove_edge(v[0], v[1])删除边 1-34graph.add_vertex(v5)新增值为 6 的顶点暂时孤立5graph.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不只是孤立的数据结构它直接支撑着仓库中两个图的遍历算法广度优先遍历BFSgraph_bfs.py 借助队列实现「由近及远」的遍历核心语句for adj_vet in graph.adj_list[vet]正是通过邻接表快速取得当前顶点的全部邻居配合visited哈希集合防止重复访问深度优先遍历DFSgraph_dfs.py 采用递归方式沿邻接表逐层深入同样依赖graph.adj_list[vet]获取邻接顶点。正是因为邻接表能够以 $O(\text{度数})$ 的代价枚举某个顶点的所有邻居BFS/DFS 才能达到 $O(nm)$ 的总体遍历复杂度若改用邻接矩阵遍历单个顶点的邻居需要扫描一整行效率会明显下降。这再次印证了邻接表在稀疏图场景下的综合优势。小结邻接表用「每个顶点 其邻接顶点集合」的方式存储图只保存实际存在的边空间效率优于邻接矩阵hello-algo 的GraphAdjList采用「哈希表 动态数组」实现并用Vertex实例作为唯一标识兼顾了增删顶点与增删边的效率添加/删除边需双向同步维护删除顶点需遍历全表清理关联边这是无向图邻接表实现的两个关键细节完整可运行的示例代码见 graph_adjacency_list.py配套的可视化步骤图与复杂度对比表见 graph_operations.md。如果你正在学习图的存储结构或准备面试中的图论题目建议在读懂本文代码后动手将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-algo 图基础基于邻接矩阵的无向图 GraphAdjMat Python 实现与操作复杂度全解析hello algo 图基础基于邻接矩阵的无向图 GraphAdjMat Python 实现与操作复杂度全解析 导读 邻接矩阵是图graph最直观的存储表教程文档示例工程教育hello-algo 邻接矩阵图实现详解Python GraphAdjMat 类的增删顶点/边全解析hello algo 邻接矩阵图实现详解Python GraphAdjMat 类的增删顶点/边全解析 本文围绕《Hello 算法》hello algo仓库教程文档示例工程教育Hello Algo 图数据结构全解邻接矩阵、邻接表与 BFS/DFS 遍历的源码级梳理Hello Algo 图数据结构全解邻接矩阵、邻接表与 BFS/DFS 遍历的源码级梳理 本文围绕《Hello 算法》图库章节的小结展开系统梳理图的数据结构教程文档示例工程教育上一篇PrivateGPT私有化部署终极指南企业级AI解决方案完整教程下一篇腾讯混元Hy3-FP8部署实战vLLM vs SGLang性能对比创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考