Hello 算法图论实战：邻接矩阵与邻接表的增删边、增删顶点实现与复杂度对比

Hello 算法图论实战邻接矩阵与邻接表的增删边、增删顶点实现与复杂度对比【免费下载链接】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 算法》hello-algo图章节中的“图的基础操作”展开系统讲解无向图在邻接矩阵与邻接表两种表示下如何完成“添加/删除边”和“添加/删除顶点”四类基础操作并结合仓库中 Python 实现、Java 实现 与 C 实现 的源码逐一印证每个操作的时间复杂度最终给出两种表示法的完整效率对比帮助读者建立“何时该用邻接矩阵、何时该用邻接表”的工程判断依据。一、图的两种表示操作的“舞台”图的基础操作可分为对“边”的操作和对“顶点”的操作。由于图有两种经典存储结构——邻接矩阵二维数组与邻接表哈希表 顶点邻接列表同样的操作在两种结构下的实现方式和时间开销差异明显。理解这些差异是后续学习图的遍历DFS/BFS以及更高层图算法的前提。本章配套概念可参考 图的定义 与 图的遍历。二、基于邻接矩阵的实现设一个顶点数量为 $n$ 的无向图邻接矩阵是一个 $n \times n$ 的二维数组adj_mat行列索引均对应“顶点索引”。文档给出的五类操作及其复杂度如下添加或删除边直接在邻接矩阵中修改指定的边即可使用 $O(1)$ 时间。由于是无向图因此需要同时更新两个方向的边(i, j)与(j, i)。添加顶点在邻接矩阵的尾部添加一行一列并全部填 $0$ 即可使用 $O(n)$ 时间。删除顶点在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况需要将 $(n-1)^2$ 个元素“向左上移动”从而使用 $O(n^2)$ 时间。初始化传入 $n$ 个顶点初始化长度为 $n$ 的顶点列表vertices使用 $O(n)$ 时间初始化 $n \times n$ 大小的邻接矩阵adj_mat使用 $O(n^2)$ 时间。2.1 源码印证Python 版 GraphAdjMat仓库中 graph_adjacency_matrix.py 完整实现了上述操作核心成员与方法如下class GraphAdjMat: 基于邻接矩阵实现的无向图类 def __init__(self, vertices: list[int], edges: list[list[int]]): # 顶点列表元素代表“顶点值”索引代表“顶点索引” self.vertices: list[int] [] # 邻接矩阵行列索引对应“顶点索引” self.adj_mat: list[list[int]] [] # 添加顶点 for val in vertices: self.add_vertex(val) # 添加边 # 请注意edges 元素代表顶点索引即对应 vertices 元素索引 for e in edges: self.add_edge(e[0], e[1]) def size(self) - int: 获取顶点数量 return len(self.vertices) def add_vertex(self, val: int): 添加顶点 n self.size() # 向顶点列表中添加新顶点的值 self.vertices.append(val) # 在邻接矩阵中添加一行 new_row [0] * n self.adj_mat.append(new_row) # 在邻接矩阵中添加一列 for row in self.adj_mat: row.append(0) def remove_vertex(self, index: int): 删除顶点 if index self.size(): raise IndexError() # 在顶点列表中移除索引 index 的顶点 self.vertices.pop(index) # 在邻接矩阵中删除索引 index 的行 self.adj_mat.pop(index) # 在邻接矩阵中删除索引 index 的列 for row in self.adj_mat: row.pop(index)对照文档的结论源码中可以看到$O(n)$ 的添加顶点见 add_vertex追加一行 $[0] \times n$再遍历所有已有行各补一个0恰好对应“尾部加一行一列”$O(n^2)$ 的删除顶点见 remove_vertexpop(index)删除一行后还需要逐行row.pop(index)删除同一列——当index 0时每行的删除都触发整行元素前移总移动量正是文档所述的 $(n-1)^2$这是矩阵表示删除顶点的性能瓶颈所在。边的操作实现更为直观见 add_edge / remove_edgedef add_edge(self, i: int, j: int): 添加边 # 参数 i, j 对应 vertices 元素索引 # 索引越界与相等处理 if i 0 or j 0 or i self.size() or j self.size() or i j: raise IndexError() # 在无向图中邻接矩阵关于主对角线对称即满足 (i, j) (j, i) self.adj_mat[i][j] 1 self.adj_mat[j][i] 1 def remove_edge(self, i: int, j: int): 删除边 if i 0 or j 0 or i self.size() or j self.size() or i j: raise IndexError() self.adj_mat[i][j] 0 self.adj_mat[j][i] 0从源码结构看这里有两个值得注意的工程细节对称性约定无向图的邻接矩阵关于主对角线对称因此每条边都要写两次adj_mat[i][j]与adj_mat[j][i]与文档中“无向图需同时更新两个方向的边”一一对应防御式校验add_edge/remove_edge在操作前统一检查索引越界与自环i j越界则抛出IndexError这一点在 Java 版本 中同样存在抛出IndexOutOfBoundsException说明这是各语言实现的共同约定。多语言实现均遵循同一套 API可交叉对照阅读C 版本、C 测试用例、Java 版本。2.2 运行示例Driver Code 的完整流程各语言文件的main部分提供了可直接运行的驱动代码以 Python 驱动代码 为例完整演示了“初始化 → 加边 → 删边 → 加顶点 → 删顶点”的全流程if __name__ __main__: # 初始化无向图 # 请注意edges 元素代表顶点索引即对应 vertices 元素索引 vertices [1, 3, 2, 5, 4] edges [[0, 1], [0, 3], [1, 2], [2, 3], [2, 4], [3, 4]] graph GraphAdjMat(vertices, edges) # 添加边顶点 1, 2 的索引分别为 0, 2 graph.add_edge(0, 2) # 删除边顶点 1, 3 的索引分别为 0, 1 graph.remove_edge(0, 1) # 添加顶点 graph.add_vertex(6) # 删除顶点顶点 3 的索引为 1 graph.remove_vertex(1)在本地直接执行python codes/python/chapter_graph/graph_adjacency_matrix.py即可逐步打印每次操作后的顶点列表与邻接矩阵打印通过 print_matrix 工具函数完成非常适合用于验证上述各操作的中间状态。三、基于邻接表的实现设无向图的顶点总数为 $n$、边总数为 $m$基于邻接表的各操作实现方式如下添加边在顶点对应链表的末尾添加边即可使用 $O(1)$ 时间。因为是无向图所以需要同时添加两个方向的边。删除边在顶点对应链表中查找并删除指定边使用 $O(m)$ 时间。在无向图中需要同时删除两个方向的边。添加顶点在邻接表中添加一个链表并将新增顶点作为链表头节点使用 $O(1)$ 时间。删除顶点需遍历整个邻接表删除包含指定顶点的所有边使用 $O(n m)$ 时间。初始化在邻接表中创建 $n$ 个顶点和 $2m$ 条边无向图每条边存两个方向使用 $O(n m)$ 时间。3.1 实现与示意图的两处差异文档特别指出对比示意图实际代码有两点不同这是理解仓库实现的关键用列表动态数组代替链表为了方便添加与删除顶点、简化代码仓库实现中“每个顶点的邻接列表”实际使用动态数组Pythonlist/ Cvector而非真正的链表用哈希表存储邻接表key为顶点实例value为该顶点的邻接顶点列表。此外邻接表中每个顶点是一个独立的Vertex实例见 vertex.py 中仅含一个val字段的类。文档给出了这样设计的原因如果与邻接矩阵一样用列表索引来区分顶点那么删除索引为 $i$ 的顶点后需要遍历整个邻接表把所有大于 $i$ 的索引全部减 $1$效率很低而每个顶点都是唯一的Vertex实例时删除某一顶点之后无须改动其他顶点。3.2 源码印证Python 版 GraphAdjListgraph_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]) def size(self) - int: 获取顶点数量 return len(self.adj_list) 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) 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) def add_vertex(self, vet: Vertex): 添加顶点 if vet in self.adj_list: return # 在邻接表中添加一个新链表 self.adj_list[vet] [] 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)逐条对应文档结论$O(1)$ 添加边add_edge 通过哈希表两次定位端点链表后各执行一次append无向图因此写两个方向$O(m)$ 删除边remove_edge 中list.remove(vet)需要在链表内线性查找目标最坏遍历整张图的所有邻接记录即 $O(m)$ 量级$O(1)$ 添加顶点add_vertex 仅向哈希表插入一个空列表并且对重复顶点做了幂等处理已存在则直接返回$O(n m)$ 删除顶点remove_vertex 先pop掉该顶点自己的链表再遍历其余所有顶点的链表逐一删除指向它的边——遍历总访问量正比于 $n m$与文档结论一致。C 实现 graph_adjacency_list.cpp 采用了相同的结构unordered_mapVertex*, vectorVertex*作为邻接表并额外封装了一个在vector中按指针定位删除的remove辅助方法逻辑与 Python 版完全对应。3.3 运行示例Python 驱动代码 使用辅助函数vals_to_vets见 vertex.py将值列表转换为顶点实例后构造图操作顺序与矩阵版一致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) # 添加边顶点 1, 2 即 v[0], v[2] graph.add_edge(v[0], v[2]) # 删除边顶点 1, 3 即 v[0], v[1] graph.remove_edge(v[0], v[1]) # 添加顶点 v5 Vertex(6) graph.add_vertex(v5) # 删除顶点顶点 3 即 v[1] graph.remove_vertex(v[1])对比两个驱动代码可以发现一个关键区别矩阵版用索引如add_edge(0, 2)定位顶点而邻接表版用顶点实例如add_edge(v[0], v[2])定位顶点——这正是前文所说“用Vertex实例代替索引”设计思想在 API 层面的直接体现。四、效率对比邻接矩阵 vs 邻接表设图中共有 $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)$结合源码可以进一步理解表中数字的来源矩阵的“判断是否邻接”只需一次数组访问adj_mat[i][j]$O(1)$ 成立邻接表则需线性扫描端点的邻接列表故为 $O(n)$ 量级矩阵删除顶点的 $O(n^2)$ 来自 remove_vertex 中逐行删除列元素时的整体移动邻接表删除顶点的 $O(n m)$ 则来自 remove_vertex 对全表邻接列表的一次遍历。观察上表似乎邻接表哈希表的时间效率与空间效率最优。但实际上在邻接矩阵中操作边的效率更高——只需一次数组访问或赋值操作即可完成常数因子极小。综合来看原文档给出的选型原则是邻接矩阵体现了“以空间换时间”的原则适合边较密、频繁进行“是否邻接”判断与增删边操作的图代价是 $O(n^2)$ 的内存占用与删除顶点时的高昂移动成本邻接表体现了“以时间换空间”的原则只存储实际存在的 $2m$ 条边稀疏图下空间优势明显代价是删除边、判断邻接等操作需要线性扫描。五、适用前提与延伸阅读本文所述复杂度均以无向简单图为前提每条边在两种结构中都会存两个方向矩阵对称、邻接表双向追加因此初始化邻接表需创建 $2m$ 条边记录若处理有向图边记录数减半但“同时更新两个方向”的步骤不再适用。邻接矩阵实现中edges传入的是顶点索引而非顶点值这一点在 构造方法注释 中反复强调调用时需注意区分邻接表实现则直接以Vertex实例为 key天然避免了索引重排问题。仓库同时提供 C、C、Java、JavaScript、TypeScript、Go、Rust 等十余种语言的同构实现如 C 版邻接矩阵、Java 版邻接表API 命名与设计细节一致便于跨语言对照学习掌握基础操作后可继续深入同章节的 图的遍历DFS/BFS那里会复用本文的邻接矩阵与邻接表结构。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考