企业官网建设流程全解析

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_vertex，pop(index)删除一行后，还需要逐行row.pop(index)删除同一列——当index = 0时，每行的删除都触发整行元素前移，总移动量正是文档所述的 $(n-1)^2$，这是矩阵表示删除顶点的性能瓶颈所在。

边的操作实现更为直观，见 add_edge / remove_edge：

def 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

从源码结构看，这里有两个值得注意的工程细节：

1. 对称性约定：无向图的邻接矩阵关于主对角线对称，因此每条边都要写两次（adj_mat[i][j]与adj_mat[j][i]），与文档中“无向图需同时更新两个方向的边”一一对应；
2. 防御式校验：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 实现与示意图的两处差异

文档特别指出，对比示意图，实际代码有两点不同，这是理解仓库实现的关键：

1. 用列表（动态数组）代替链表：为了方便添加与删除顶点、简化代码，仓库实现中“每个顶点的邻接列表”实际使用动态数组（Pythonlist/ C++vector）而非真正的链表；
2. 用哈希表存储邻接表：key为顶点实例，value为该顶点的邻接顶点列表。

此外，邻接表中每个顶点是一个独立的Vertex实例（见 vertex.py 中仅含一个val字段的类）。文档给出了这样设计的原因：如果与邻接矩阵一样用列表索引来区分顶点，那么删除索引为 $i$ 的顶点后，需要遍历整个邻接表把所有大于 $i$ 的索引全部减 $1$，效率很低；而每个顶点都是唯一的Vertex实例时，删除某一顶点之后无须改动其他顶点。

3.2 源码印证：Python 版 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]) 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_map<Vertex*, vector<Vertex*>>作为邻接表，并额外封装了一个在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$ 条边，原文档给出了如下效率对比表。请注意，“邻接表（链表）”对应本文实现，而“邻接表（哈希表）”专指将每条邻接链表进一步替换为哈希表后的实现：

结合源码可以进一步理解表中数字的来源：

• 矩阵的“判断是否邻接”只需一次数组访问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