8.1 图的表示：先把顶点和边放进内存

第 8 章 · 图基础｜前置：数组、列表与类｜下一篇：DFS 与 BFS。本页先固定顶点、边、自环、重复边和非法编号的合同，再比较邻接矩阵与邻接表。

从“路”而不是“上下级”开始

前面研究的树有父子层级。一般图允许 A 同时连到 B、C，也允许沿其他边绕回 A。这里 A、B、C 是顶点，连接它们的是边。图可以有方向：A → B 不自动意味着可以反向行走。

表示这些关系，常见的做法有两种：

• 邻接矩阵：第 u 行、第 v 列表示 u → v 是否存在。
• 邻接表：每个顶点保存自己的出邻居。

本篇采用一个明确的教学合同：顶点必须是 0..n-1 的整数；允许自环；重复加同一条边不会产生平行边；非法编号抛出 IndexError。真实项目也可以允许平行边，但需要保存多个边记录或边的重数，不能仍用一个布尔值表达。n 必须是非负整数，directed 必须为布尔值；构造后不直接修改这两个字段。

一份可以复制运行的实现

class AdjacencyMatrixGraph:
    """布尔邻接矩阵；固定顶点数，重复边会被自然去重。"""

    def __init__(self, n, directed=False):
        if not isinstance(n, int):
            raise TypeError("n must be an integer")
        if not isinstance(directed, bool):
            raise TypeError("directed must be a boolean")
        if n < 0:
            raise ValueError("n must be non-negative")
        self.n = n
        self.directed = directed
        self._matrix = [[False] * n for _ in range(n)]

    def _check(self, vertex):
        if not isinstance(vertex, int) or not 0 <= vertex < self.n:
            raise IndexError(f"vertex out of range: {vertex!r}")

    def add_edge(self, source, target):
        self._check(source)
        self._check(target)
        self._matrix[source][target] = True
        if not self.directed:
            self._matrix[target][source] = True

    def remove_edge(self, source, target):
        self._check(source)
        self._check(target)
        self._matrix[source][target] = False
        if not self.directed:
            self._matrix[target][source] = False

    def has_edge(self, source, target):
        self._check(source)
        self._check(target)
        return self._matrix[source][target]

    def neighbors(self, vertex):
        self._check(vertex)
        return [other for other, linked in enumerate(self._matrix[vertex]) if linked]

class AdjacencyListGraph:
    """有序邻接表；用列表保留插入顺序，显式抑制重复边。"""

    def __init__(self, n, directed=False):
        if not isinstance(n, int):
            raise TypeError("n must be an integer")
        if not isinstance(directed, bool):
            raise TypeError("directed must be a boolean")
        if n < 0:
            raise ValueError("n must be non-negative")
        self.n = n
        self.directed = directed
        self._adjacency = [[] for _ in range(n)]

    def _check(self, vertex):
        if not isinstance(vertex, int) or not 0 <= vertex < self.n:
            raise IndexError(f"vertex out of range: {vertex!r}")

    def add_edge(self, source, target):
        self._check(source)
        self._check(target)
        if target not in self._adjacency[source]:
            self._adjacency[source].append(target)
        if not self.directed and source != target:
            if source not in self._adjacency[target]:
                self._adjacency[target].append(source)

    def remove_edge(self, source, target):
        self._check(source)
        self._check(target)
        if target in self._adjacency[source]:
            self._adjacency[source].remove(target)
        if not self.directed and source != target:
            if source in self._adjacency[target]:
                self._adjacency[target].remove(source)

    def has_edge(self, source, target):
        self._check(source)
        self._check(target)
        return target in self._adjacency[source]

    def neighbors(self, vertex):
        self._check(vertex)
        return list(self._adjacency[vertex])

if __name__ == "__main__":
    names = ["A", "B", "C", "D", "E"]
    graph = AdjacencyListGraph(len(names))
    for source, target in [(0, 1), (0, 2), (1, 3), (2, 4)]:
        graph.add_edge(source, target)
    for vertex, name in enumerate(names):
        print(name, "->", [names[n] for n in graph.neighbors(vertex)])

运行方式：

1. 保存为 graph_representation.py。
2. 执行 python3 graph_representation.py。
3. 预期看到 A 连 B、C，B 连 A、D；无向边在两端都能查到。

手算一遍矩阵

若无向边为 {A,B}、{A,C}、{B,D}、{C,E}，矩阵是：

    A B C D E
A   0 1 1 0 0
B   1 0 0 1 0
C   1 0 0 0 1
D   0 1 0 0 0
E   0 0 1 0 0

它沿主对角线对称，因为每条路都能双向通行。若 A→B 是单向边，只写 matrix[A][B]，矩阵便不必对称。

怎么选

设顶点数为 V、边数为 E，d(u) 为本实现中 u 的邻居列表长度。无向非自环边会出现两次，自环只出现一次；总存储仍是 O(V + E)。矩阵按顶点编号枚举邻居，列表按插入顺序枚举；两者表示同一张图，也可能产生不同的遍历顺序。

操作或场景	邻接矩阵	本文的有序邻接表
空间	O(V²)	O(V + E)
查询 u → v	O(1)	O(d(u)+1)
枚举 u 的邻居	O(V)	O(d(u)+1)
有向边加/删	O(1)	O(d(u)+1)
无向边加/删	O(1)	O(d(u)+d(v)+1)

这些类固定顶点集，不提供新增顶点方法。扩展设计时，邻接表可追加一个空列表；矩阵要为新行、新列安排存储。固定尺寸矩阵删边只需把格子改成 False，无需重排。初始化空矩阵要 Θ(V²)，空邻接表要 Θ(V)；逐边建邻接表还要支付列表判重成本，不能直接宣称这个构造过程总是 O(V+E)。也不要用一段机器上的跑分替代复杂度分析；数据规模、密度、语言实现和缓存行为都会改变结果。

工程中若既要邻居遍历又要快速判重，可以把每个邻接容器换成 set。代价是默认遍历顺序不再适合作为算法输出合同。本文使用列表，是为了让 DFS、BFS 的教学结果可重复。

边界检查清单

• 孤立点：即使没有边，也必须保留一个空邻接表。
• 自环：无向图的 u：u 只保存一次；它会使二分图检测失败。按图论惯例，无向自环对度数贡献 2，因此 len(neighbors(u)) 在有自环时不等于标准度数。
• 重复边：本实现去重；若业务需要航班、班次之类的平行边，应保留多个边记录或重数。
• 有向性：u → v 不自动推出 v → u。
• 返回副本：neighbors() 不暴露内部列表，调用者清空返回值不会破坏图。

小练习

另建一个有向图，顶点为 A 到 E，只加入 A→B、A→C、C→A，再回答：

1. 为什么 has_edge(B, A) 是假？
2. C→A 与 A→C 是否构成一个长度为 2 的环？
3. 若删除 A→C，C 还能否直接到 A？

先在纸上画五六个点，再对照程序输出。图这一章最费时间的地方不是敲代码，而是把“一个节点可以沿多条路回到旧节点”装进脑子里。

地图画好以后

表示法会改变操作成本，却不改变图本身。矩阵用 O(V²) 空间换取常数时间判边；邻接表的空间与全图邻居枚举为 O(V+E)，判边成本则取决于出度和邻接容器。无向边、自环、重复边与返回副本都必须先写进合同。

示例已经把顶点和边放进内存。下一篇在同一结构上运行DFS、BFS 与图上的结构算法。