Python邻接矩阵详解（图的表示方法入门教程）

用Python创建邻接矩阵

下面我们用一个简单的例子来演示如何用Python邻接矩阵表示一个图。

假设我们有一个包含4个顶点（A、B、C、D）的无向图，边如下：

• A — B
• A — C
• B — D
• C — D

步骤1：初始化邻接矩阵

首先，创建一个 4×4 的全零矩阵：

# 初始化一个4x4的邻接矩阵（全0）n = 4adj_matrix = [[0 for _ in range(n)] for _ in range(n)]print("初始邻接矩阵：")for row in adj_matrix:    print(row)

步骤2：添加边

根据图的边关系，在矩阵对应位置填入1。注意：无向图是对称的，所以 [i][j] 和 [j][i] 都要设为1。

# 添加边# A(0) - B(1)adj_matrix[0][1] = 1adj_matrix[1][0] = 1# A(0) - C(2)adj_matrix[0][2] = 1adj_matrix[2][0] = 1# B(1) - D(3)adj_matrix[1][3] = 1adj_matrix[3][1] = 1# C(2) - D(3)adj_matrix[2][3] = 1adj_matrix[3][2] = 1print("添加边后的邻接矩阵：")for row in adj_matrix:    print(row)

运行结果如下：

[0, 1, 1, 0][1, 0, 0, 1][1, 0, 0, 1][0, 1, 1, 0]

封装成类（进阶）

为了更方便地使用，我们可以将邻接矩阵封装成一个图类：

class Graph:    def __init__(self, vertices):        self.vertices = vertices        self.adj_matrix = [[0] * vertices for _ in range(vertices)]        def add_edge(self, u, v):        # 无向图：双向添加        self.adj_matrix[u][v] = 1        self.adj_matrix[v][u] = 1        def print_matrix(self):        for row in self.adj_matrix:            print(row)# 使用示例g = Graph(4)g.add_edge(0, 1)  # A-Bg.add_edge(0, 2)  # A-Cg.add_edge(1, 3)  # B-Dg.add_edge(2, 3)  # C-Dg.print_matrix()

邻接矩阵的优缺点

优点：

• 查询两个顶点是否相邻的时间复杂度为 O(1)。
• 实现简单，直观易懂。

缺点：

• 空间复杂度高，为 O(V²)，其中 V 是顶点数。对于稀疏图（边很少）来说浪费空间。
• 添加或删除顶点需要重建整个矩阵。

总结

通过本教程，你已经掌握了如何用Python邻接矩阵表示图的基本方法。这是学习图的表示方法的重要一步，也是理解更复杂图算法（如DFS、BFS、最短路径等）的基础。希望这篇邻接矩阵教程对你有所帮助！

提示：在实际项目中，如果图很稀疏，可以考虑使用邻接表（Adjacency List）来节省内存。