Python中怎么用01矩阵表示图的邻接关系
本文详细讲解在Python中如何使用01矩阵表示图的邻接关系,包含顶点映射、原生列表与NumPy构建步骤、有向图与无向图处理、常用图属性查询及典型避坑指南。
在图论中,图(Graph)由顶点集合与连接顶点的边集合构成。要用计算机程序处理图结构,必须将其数字化存储。01矩阵(在未加权图中被称为01邻接矩阵,Adjacency Matrix)是一种标准的表示方式:若图中包含 N 个顶点,则构建一个 N × N 的二维矩阵,其中第 i 行第 j 列的数值用 1 表示顶点 i 与顶点 j 之间存在边相连,用 0 表示二者无直连边。
一、01邻接矩阵的基本定义与映射机制
为了把图转换为二维矩阵,首先需要为图中的每个顶点分配一个唯一的整数索引(通常为 0 到 N - 1)。假设顶点集合为 {A, B, C, D},我们可以建立如下对应关系:A → 0、B → 1、C → 2、D → 3。
建立索引后,矩阵中的每个单元格 M[i][j] 对应于从顶点 i 到顶点 j 的连接状态。有向图与无向图在01矩阵中的表现形式具有鲜明差异:
- 无向图(Undirected Graph):由于边是双向连通的,顶点
i到j连通必然意味着j到i连通。因此,无向图的01邻接矩阵必然关于主对角线严格对称,即满足M[i][j] == M[j][i]。 - 有向图(Directed Graph):边具有方向性。
M[i][j] = 1仅代表存在一条由i指向j的出边,并不蕴含反向连通。因此有向图的矩阵通常是非对称矩阵。 - 自环(Self-loop):若某个顶点自身与自身相连,则主对角线对应位置
M[i][i] = 1;对于简单图(无自环图),主对角线元素全为0。
二、从边列表到01矩阵的4步处理流程
在实际编程中,图的数据通常以“顶点列表”加“边列表”的形式给出(例如日志记录、网络流或数据库关联记录)。构建01矩阵是一个确定性的转换过程,主要包含4个核心操作阶段:
三、Python实现方案:原生列表与NumPy数组
在Python生态中,表达二维矩阵最常用的两种载体是原生嵌套列表与NumPy多维数组。前者无需安装外部依赖,适用于通用算法答题和轻量级工程;后者底层采用连续C内存存储,支持向量化与矩阵运算,是科学计算和网络分析的首选。
1. 原生Python实现代码
使用原生列表时,关键在于正确初始化二维数组。必须使用列表推导式 [[0] * n for _ in range(n)],使矩阵的每一行都是一个独立的内存对象。
class GraphMatrix:
def __init__(self, vertices, is_directed=False):
"""
初始化图邻接矩阵
:param vertices: 顶点标识列表,例如 ['A', 'B', 'C', 'D']
:param is_directed: 是否为有向图
"""
self.vertices = list(vertices)
self.is_directed = is_directed
self.n = len(self.vertices)
# 建立顶点名称到矩阵行列索引的双向映射
self.vertex_to_idx = {v: i for i, v in enumerate(self.vertices)}
self.idx_to_vertex = {i: v for i, v in enumerate(self.vertices)}
# 核心:使用推导式初始化 N x N 全零二维列表
self.matrix = [[0] * self.n for _ in range(self.n)]
def add_edge(self, u, v):
"""添加一条从 u 到 v 的边"""
if u not in self.vertex_to_idx or v not in self.vertex_to_idx:
raise ValueError(f"顶点 {u} 或 {v} 不存在于图中")
i, j = self.vertex_to_idx[u], self.vertex_to_idx[v]
self.matrix[i][j] = 1
# 若为无向图,对称填充反向连接
if not self.is_directed:
self.matrix[j][i] = 1
def has_edge(self, u, v):
"""判断 u 到 v 是否有直连边,时间复杂度 O(1)"""
i, j = self.vertex_to_idx[u], self.vertex_to_idx[v]
return self.matrix[i][j] == 1
def get_out_neighbors(self, u):
"""获取顶点 u 的所有出边邻居"""
i = self.vertex_to_idx[u]
return [self.idx_to_vertex[j] for j, connected in enumerate(self.matrix[i]) if connected == 1]
def display(self):
"""打印 01 邻接矩阵"""
header = " " + " ".join(f"{v:>2}" for v in self.vertices)
print(header)
for i, row in enumerate(self.matrix):
v_name = self.idx_to_vertex[i]
row_str = " ".join(f"{val:>2}" for val in row)
print(f"{v_name:>2} [{row_str}]")
# 示例:构建包含 4 个顶点的有向图
if __name__ == "__main__":
nodes = ['A', 'B', 'C', 'D']
g = GraphMatrix(nodes, is_directed=True)
# 填入边集合
edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D'), ('D', 'A')]
for u, v in edges:
g.add_edge(u, v)
print("--- 4x4 有向图 01 邻接矩阵 ---")
g.display()
print("\n查询 A 是否能直达 C:", g.has_edge('A', 'C')) # 输出: True
print("查询 C 是否能直达 A:", g.has_edge('C', 'A')) # 输出: False
print("顶点 A 的所有出边邻居:", g.get_out_neighbors('A')) # 输出: ['B', 'C']
避坑提示: 切忌使用 [[0] * n] * n 进行初始化!乘法浅拷贝会导致外层列表引用同一个内层行对象。一旦执行 matrix[0][1] = 1,整个矩阵每一行的第 1 列都会被同步修改为 1。
2. NumPy实现代码
NumPy 提供了 np.zeros((n, n), dtype=int),能够直接分配一块连续内存来存放 01 矩阵。NumPy 的优势在于可以直接利用向量化与线性代数库计算图的特征。
import numpy as np
# 1. 定义顶点与边
vertices = ['A', 'B', 'C', 'D']
v_map = {name: i for i, name in enumerate(vertices)}
n = len(vertices)
# 2. 初始化 NumPy 二维矩阵(整数类型)
adj_matrix = np.zeros((n, n), dtype=int)
# 3. 批量添加边
edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D'), ('D', 'A')]
for u, v in edges:
i, j = v_map[u], v_map[v]
adj_matrix[i, j] = 1
print("NumPy 01 矩阵数组:")
print(adj_matrix)
# 4. 利用 NumPy 计算度数
out_degrees = adj_matrix.sum(axis=1) # 行求和 -> 各节点出度
in_degrees = adj_matrix.sum(axis=0) # 列求和 -> 各节点入度
for i, v in enumerate(vertices):
print(f"顶点 {v}: 出度 = {out_degrees[i]}, 入度 = {in_degrees[i]}")
四、01邻接矩阵的核心图属性查询与计算
使用01矩阵表示图的最大好处之一是,许多复杂的图论拓扑属性可以转化为简练的矩阵运算。
1. 边存在性判断:O(1) 极速查询
如果需要高频判断“顶点 u 是否与 v 相连”,01矩阵具备不可替代的优势。直接通过坐标寻址 matrix[u][v] == 1,耗时严格为 O(1),无需像邻接表那样遍历链表。
2. 路径计数与矩阵乘方
这是01矩阵在数学上最精妙的特性:设 M 为 01 邻接矩阵,若计算其矩阵乘积 M² = M × M,则结果矩阵中的每一个元素 (M²)[i][j] 正好等于从顶点 i 到 j 长度为 2 的路径数量。例如在上述图模型中:
# 计算走 2 步能到达的路径数
M2 = np.linalg.matrix_power(adj_matrix, 2)
print("走 2 步的路径数矩阵:\n", M2)
# 输出中若 M2[0, 2] == 1,说明存在路径 A -> B -> C(长度为 2)
五、01矩阵与其他图表示方案的选型对比
虽然01矩阵结构直观、查边效率极高,但它并非适用所有场景。因为其空间开销恒为 O(V²)(与边数 E 无关),当图规模较大且连接较稀疏时,会产生大量冗余的 0。
| 对比维度 | 01 邻接矩阵 (Adjacency Matrix) | 邻接表 (Adjacency List) | 稀疏矩阵 (scipy.sparse) |
|---|---|---|---|
| 存储空间 | O(V²),与边数无关 |
O(V + E),动态按需分配 |
O(E),仅存非零元素 |
| 查边 (u, v) 耗时 | O(1) 极速 |
O(deg(u)),需遍历邻居 |
O(log(deg(u))) |
| 找某节点全部邻居 | O(V),需扫整行所有列 |
O(deg(u)),直接遍历 |
O(deg(u)) |
| 添加 / 删除边 | O(1),直接改写 0 或 1 |
O(deg(u)) 或 O(1) |
修改开销稍大(视格式而定) |
| 适用图类型 | 稠密图 (Dense, E 接近 V²) | 稀疏图 (Sparse, E ≪ V²) | 超大规模稀疏图 (V > 10⁵) |
六、实践总结与开发建议
在Python中用01矩阵表示图的邻接关系,核心逻辑可以归纳为两句话:“节点建立从 0 到 N-1 的整型索引映射”,以及“通过二维数组的 (行, 列) 坐标以 1 标记连接,以 0 标记隔离”。
在日常开发落地时,建议遵循以下实践标准:
- 小图与算法竞赛直接使用列表推导式:轻量、无任何第三方包依赖,记得必须使用
[[0] * n for _ in range(n)]。 - 矩阵运算与代数图论首选 NumPy:当需要计算出度入度、矩阵乘方、谱聚类或图拉普拉斯矩阵时,NumPy 能够提供百倍以上的执行效率。
- 无向图务必保证对称赋值:每次添加一条边
(u, v),必须同时执行matrix[u][v] = 1与matrix[v][u] = 1。 - 警惕空间爆炸:当节点数
V达到100,000时,N × N的整型矩阵需要消耗近40 GB内存。遇到此类大规模稀疏网络,应果断切换为邻接表或scipy.sparse压缩稀疏矩阵。
本站声明
本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。













