邻接矩阵 - CSP-J | C++ & Algorithm 编程研习社

用邻接矩阵表示图：就像班级座位表

在编程中，我们经常需要表示“谁和谁有关系”——比如社交网络中的好友、地图上的道路、比赛中的对阵。邻接矩阵就是一种最简单、最直观的表示方法：它像一张班级座位表，行和列都代表同一个班级的每一位同学，如果某两位同学是好朋友，就在他们对应的格子里打勾（或者写1），否则写0。

在 Python 中，我们用二维列表（列表的列表）来存放这张表格。矩阵大小是 n × n（n 是顶点数），第 i 行第 j 列的元素表示顶点 i 到顶点 j 之间是否有边。如果有边，存 1（或权重）；没有边，存 0。

一、邻接矩阵长什么样？

假设有 4 个同学：0 号、1 号、2 号、3 号。他们之间的朋友关系如下：

0 和 1 是好朋友
0 和 2 是好朋友
1 和 2 是好朋友
2 和 3 是好朋友（没有自环，自己不算自己的朋友）

那么座位表（邻接矩阵）就是 4 行 4 列，第 i 行第 j 列是 1 表示 i 和 j 是朋友：

    0  1  2  3
0  [0, 1, 1, 0]
1  [1, 0, 1, 0]
2  [1, 1, 0, 1]
3  [0, 0, 1, 0]

你发现了吗？横着看第一行：[0, 1, 1, 0] 表示 0 号同学的朋友是 1 号和 2 号。竖着看第一列也一样，因为“朋友”关系是双向的（无向图），所以矩阵永远关于主对角线对称。

二、如何用 Python 创建邻接矩阵

2.1 基础：手动添加边（无向图）

先创建一个全是 0 的 n×n 矩阵，再把有边的地方改成 1。注意无向图要同时改 matrix[u][v] 和 matrix[v][u]。

# 顶点数
n = 4

# 创建全0的矩阵（注意不要写成 [[0]*n]*n，那是浅复制，会导致所有行共享）
matrix = [[0] * n for _ in range(n)]

# 添加边（无向图，对称添加）
edges = [(0,1), (0,2), (1,2), (2,3)]  # 每条边是 (u, v) 元组
for u, v in edges:
    matrix[u][v] = 1  # u 到 v 有边
    matrix[v][u] = 1  # v 到 u 也有边（无向）

# 打印矩阵
print("邻接矩阵：")
for row in matrix:
    print(row)

输出：

邻接矩阵：
[0, 1, 1, 0]
[1, 0, 1, 0]
[1, 1, 0, 1]
[0, 0, 1, 0]

2.2 有向图：单向箭头

如果关系是单向的（比如“关注”或“单行道”），就不需要对称赋值。例如：0→1，0→2，2→3。

n = 4
matrix = [[0] * n for _ in range(n)]

# 有向边，只给一个方向赋值
directed_edges = [(0,1), (0,2), (2,3)]
for u, v in directed_edges:
    matrix[u][v] = 1  # 只写这一行

for row in matrix:
    print(row)

输出：

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

此时 matrix[1][0] 还是 0，表示 1 不能到 0。

2.3 带权重的图：存数字而不是 1

有时候边上有“距离”或“花费”，比如城市之间的公路长度。我们就把 1 换成具体的数值。例如：0→1 距离 5，0→2 距离 3，2→3 距离 8。

n = 4
# 初始化用很大的数表示“没有直接连接”（常用 float('inf') 或 -1）
INF = float('inf')
matrix = [[INF] * n for _ in range(n)]

# 自己到自己的距离设为 0
for i in range(n):
    matrix[i][i] = 0

# 带权边
weighted_edges = [(0,1,5), (0,2,3), (2,3,8)]
for u, v, w in weighted_edges:
    matrix[u][v] = w
    matrix[v][u] = w  # 无向图

for row in matrix:
    print(row)

输出：

[0, 5, 3, inf]
[5, 0, inf, inf]
[3, inf, 0, 8]
[inf, inf, 8, 0]

三、新手最容易犯的三个错误

❌ 错误 1：用 `[[0]n]n` 创建矩阵

# 错误写法
matrix = [[0] * n] * n   # 这不会创建 n 个独立列表，而是同一个列表的 n 个引用
matrix[0][1] = 1
print(matrix)  # 输出 [[0,1,0], [0,1,0], [0,1,0]] 所有行都被改了！

正确写法：用列表推导式 [[0] * n for _ in range(n)]，每次都生成新列表。

❌ 错误 2：无向图忘记对称赋值

# 只写了 matrix[u][v] = 1，忘了 matrix[v][u] = 1
# 这样会导致 1 号同学觉得 0 号不是朋友，但 0 号觉得 1 号是朋友，矛盾

解决方法：无向图一定记得同时写两行，或者封装成函数。

❌ 错误 3：顶点编号从 1 开始，导致数组越界

很多题目中顶点编号是 1 到 n，而列表索引从 0 开始。如果直接写 matrix[1][2] 没问题，但注意要分配 n+1 大小的矩阵。

# 正确做法：多开一行一列，用索引 1..n
n = 4
matrix = [[0] * (n+1) for _ in range(n+1)]
# 这样顶点 1 存在 matrix[1]，顶点 4 存在 matrix[4]

四、完整可运行示例（带输入）

下面是一个完整的程序，从标准输入读取顶点数、边数以及每条边，然后构建邻接矩阵并输出。

# 读取第一行：顶点数n 和 边数m
n, m = map(int, input("请输入顶点数和边数（用空格分隔）：").split())

# 创建 n x n 的零矩阵（顶点编号 0 ~ n-1）
matrix = [[0] * n for _ in range(n)]

# 逐条读取边
print("请依次输入每一条边的两个端点（空格分隔）：")
for _ in range(m):
    u, v = map(int, input().split())
    # 无向图，双向赋值
    matrix[u][v] = 1
    matrix[v][u] = 1

# 输出邻接矩阵
print("\n邻接矩阵：")
for i in range(n):
    # 用 join 让输出更整齐
    print(' '.join(str(x) for x in matrix[i]))

运行示例：

请输入顶点数和边数（用空格分隔）：4 4
请依次输入每一条边的两个端点（空格分隔）：
0 1
0 2
1 2
2 3

邻接矩阵：
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

五、邻接矩阵的优点和缺点

优点：

查询极快：判断顶点 i 和 j 是否相连，只需 matrix[i][j]，O(1) 时间。
代码简单：创建和遍历非常直观。
适合小图（顶点 ≤ 1000），尤其边很多（稠密图）时效率高。

缺点：

空间大：n 个顶点需要 n² 个格子。1000 个顶点就是 1 百万个格子，10000 个顶点就是 1 亿个，内存爆炸。
对于稀疏图（边数远小于 n²），大量格子是 0，浪费空间。
遍历所有边需要 O(n²) 时间，而邻接表只需要 O(边数)。

一句话总结：邻接矩阵适合顶点少、边多的图；稀疏图请用邻接表。

六、相关知识点指引

学完邻接矩阵后，你可以继续学习：

邻接表：用列表+链表或动态数组存储每条边，节省空间，适合稀疏图。
图的基本遍历：深度优先搜索（DFS）和广度优先搜索（BFS），邻接矩阵配合一个 visited 数组即可实现。
最短路径：Floyd-Warshall 算法（动态规划）直接基于邻接矩阵，适合求所有点对之间的最短距离。
最小生成树：Prim 算法也可以用邻接矩阵实现（适合稠密图）。

如果你对矩阵操作更感兴趣，还可以看看二维数组的更多用法，比如矩阵旋转、矩阵乘法等，它们和图论中的邻接矩阵有异曲同工之妙。

例题精讲