用表格表示图：Python邻接矩阵

同学们，生活中我们经常要表示“谁和谁有关系”。比如，班级里哪些同学互相认识，你所在的小组里谁和谁是一对搭档，电子游戏里哪些角色能互相传送。在编程里，这种“关系”可以用图来表示。前面我们学过用字典（邻接表）来存图，今天来学另一种方法——邻接矩阵。它就像一张成绩表，行和列都写着同学的名字，如果两个人有关系，就在对应的格子里打钩（填1），否则留空（填0）。

什么是邻接矩阵？

邻接矩阵就是一个二维表格（在Python里是二维列表）。行代表“从哪个顶点出发”，列代表“到哪个顶点去”。表格的每个格子存一个数字：

如果有边（关系），就填 1
如果没有边，就填 0

举个例子：假设有三个城市 A（编号1）、B（编号2）、C（编号3），有两条公路：A↔B（双向）和 B↔C（双向）。用邻接矩阵表示就是：

	1	2	3
1	0	1	0
2	1	0	1
3	0	1	0

因为 A 到 B 有路，所以第1行第2列是1；B 到 A 也有路，所以第2行第1列也是1。这种对称的样子就是无向图（边没有方向）。

如果是有向图，比如 A 只能到 B，B 只能到 C，C 不能到别人，矩阵就变成：

	2	3
1	1	0
2	0	1
3	0	0

注意：第2行第1列是0，说明不能从 B 回到 A。矩阵不再对称。

如何用Python创建邻接矩阵？

第一步：初始化全0矩阵

假如有 N 个顶点（编号从1开始），我们需要一个 N+1 行、N+1 列的二维列表（把索引0空出来，看着更习惯）。代码这样写：

n = 3                          # 顶点数
# 创建一个 (n+1) x (n+1) 的全0矩阵
matrix = [[0] * (n + 1) for _ in range(n + 1)]

这行代码虽然短，但我们要理解：[0] * (n+1) 生成了一个全是0的一维列表，再用列表推导式重复了 (n+1) 次，最终得到一个二维列表。

第二步：根据边填1

假设无向图的边是 (1,2) 和 (2,3)，我们需要把两个方向的格子都改成1：

edges = [(1,2), (2,3)]        # 无向图的边列表
for u, v in edges:            # u, v 是边的两个端点
    matrix[u][v] = 1           # u->v 填1
    matrix[v][u] = 1           # v->u 也填1（因为是无向图）

有向图则只填一个方向：

dig_edges = [(1,2), (2,3)]    # 有向图的边列表
for u, v in dig_edges:
    matrix[u][v] = 1           # 只填 u->v 的格子

第三步：打印矩阵

为了看清楚，可以逐行打印，跳过第一行第一列（因为索引0我们用不上）。

print("邻接矩阵：")
for row in matrix[1:]:        # 从第1行开始（跳过索引0）
    print(row[1:])            # 从第1列开始（跳过索引0）

这样打印出来就是整齐的3x3表格了。

生活中的例子：朋友圈

小明、小红、小刚三个人的朋友圈。小明和小红是朋友，小红和小刚是朋友，小明和小刚不是朋友。用无向图表示，顶点编号：小明=1，小红=2，小刚=3。边：1-2，2-3。

# 无向图邻接矩阵（朋友圈）
n = 3                           # 3个人
# 初始化 (n+1) x (n+1) 矩阵，多一行一列留着不用
friends = [[0] * (n + 1) for _ in range(n + 1)]
edges = [(1,2), (2,3)]          # 朋友关系（双向）

for u, v in edges:
    friends[u][v] = 1
    friends[v][u] = 1           # 无向，对称

# 打印结果，只展示1~3行，1~3列
print("朋友圈邻接矩阵（无向图）：")
for row in friends[1:]:
    print(row[1:])

输出：

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

解释：第一行是“小明”：他和小红是朋友（1），和小刚不是（0）。第二行“小红”：和小明是朋友（1），和小刚也是（1）。第三行“小刚”：和小红是朋友，和小明不是。矩阵关于主对角线对称。

邻接矩阵的优缺点

优点：快速判断两点是否直接相连

比如要问“小刚和小明是不是朋友？”程序只需看 friends[3][1] 是不是1，一秒钟就知道。时间复杂度 O(1)。

缺点：占内存大

假如班级有50个同学，每个同学的关系用一个格子表示，矩阵就是 50×50 = 2500 个格子。如果用字典（邻接表），只存有关系的边，可能只需几十个数据。所以当顶点很多（比如1000个）而边很少时，用矩阵就是浪费——全存0。只有边比较多（比如接近完全图）时，矩阵才划算。

常见错误与注意事项

错误1：忘记无向图要填两个方向

# 错误写法
edges = [(1,2), (2,3)]
for u, v in edges:
    matrix[u][v] = 1    # 只填了一个方向
# 这样 matrix[2][1] 还是0，变成了有向图

解决方法：如果无向图，记得加 matrix[v][u] = 1。

# 完整示例：用邻接矩阵表示图
def create_adj_matrix(n, edges, directed=False):
    """
    创建 n 个顶点的邻接矩阵（顶点编号从1开始）
    :param n: 顶点数
    :param edges: 边列表，每个元素是 (u, v)
    :param directed: True 表示有向图，False 表示无向图
    :return: 二维列表，大小为 (n+1) x (n+1)
    """
    # 初始化全0矩阵，索引0不用
    matrix = [[0] * (n + 1) for _ in range(n + 1)]
    for u, v in edges:
        matrix[u][v] = 1          # 从u到v
        if not directed:          # 如果是无向图
            matrix[v][u] = 1      # 从v到u也要填1
    return matrix

def print_matrix(matrix):
    """打印矩阵，去掉第一行第一列（索引0）"""
    for row in matrix[1:]:
        print(row[1:])

# ---- 测试无向图：三个朋友 ----
n = 3
edges_undirected = [(1,2), (2,3)]
print("无向图邻接矩阵（朋友网络）：")
mat_undirected = create_adj_matrix(n, edges_undirected, directed=False)
print_matrix(mat_undirected)

print()  # 空行

# ---- 测试有向图：单向关注 ----
# 假设小明关注小红，小红关注小刚，但没人关注回去
edges_directed = [(1,2), (2,3)]
print("有向图邻接矩阵（关注关系）：")
mat_directed = create_adj_matrix(n, edges_directed, directed=True)
print_matrix(mat_directed)

# ---- 快速查询：小明是否和小刚直接相连？ ----
if mat_undirected[1][3] == 1:
    print("小明和小刚是朋友")
else:
    print("小明和小刚不是朋友")

运行结果：

无向图邻接矩阵（朋友网络）：
[0, 1, 0]
[1, 0, 1]
[0, 1, 0]

有向图邻接矩阵（关注关系）：
[0, 1, 0]
[0, 0, 1]
[0, 0, 0]

小明和小刚不是朋友

Python邻接矩阵