Python中怎么用01矩阵表示图的邻接关系

Dylan
Dylan
发布时间:2026-11-18 | 3人浏览过
原创

本文详细讲解在Python中如何使用01矩阵表示图的邻接关系,包含顶点映射、原生列表与NumPy构建步骤、有向图与无向图处理、常用图属性查询及典型避坑指南。

在图论和计算机算法中,邻接矩阵是记录顶点连接关系最基础且严谨的数据结构。本文以实用讲解的方式,剖析如何使用纯0与1的二维矩阵表示图的邻接状态,提供原生列表与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。
Python中怎么用01矩阵表示图的邻接关系
图 1:有向图结构到 01 邻接矩阵的坐标映射原理示意

二、从边列表到01矩阵的4步处理流程

在实际编程中,图的数据通常以“顶点列表”加“边列表”的形式给出(例如日志记录、网络流或数据库关联记录)。构建01矩阵是一个确定性的转换过程,主要包含4个核心操作阶段:

Python中怎么用01矩阵表示图的邻接关系
图 2:从图的定义到 01 邻接矩阵的完整处理与验证流程

三、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矩阵表示图的最大好处之一是,许多复杂的图论拓扑属性可以转化为简练的矩阵运算。

Python中怎么用01矩阵表示图的邻接关系
图 3: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矩阵表示图的邻接关系
图 4:Python 图邻接表示方案多维决策对比与架构选型总览

六、实践总结与开发建议

在Python中用01矩阵表示图的邻接关系,核心逻辑可以归纳为两句话:“节点建立从 0 到 N-1 的整型索引映射”,以及“通过二维数组的 (行, 列) 坐标以 1 标记连接,以 0 标记隔离”。

在日常开发落地时,建议遵循以下实践标准:

  1. 小图与算法竞赛直接使用列表推导式:轻量、无任何第三方包依赖,记得必须使用 [[0] * n for _ in range(n)]。
  2. 矩阵运算与代数图论首选 NumPy:当需要计算出度入度、矩阵乘方、谱聚类或图拉普拉斯矩阵时,NumPy 能够提供百倍以上的执行效率。
  3. 无向图务必保证对称赋值:每次添加一条边 (u, v),必须同时执行 matrix[u][v] = 1 与 matrix[v][u] = 1。
  4. 警惕空间爆炸:当节点数 V 达到 100,000 时,N × N 的整型矩阵需要消耗近 40 GB 内存。遇到此类大规模稀疏网络,应果断切换为邻接表或 scipy.sparse 压缩稀疏矩阵。
相关专题:

本站声明

本文内容仅供参考,不代表本站观点。转载或引用请注明出处。如发现内容问题,请通过联系我们页面反馈。

Python 相关产品和应用

全部下载

专题列表