邻接表：轻装远征的档案袋

邻接表：轻装远征的档案袋

别以为方阵情报表放之四海皆准。设想远征队的地图上有十万个据点，而道路只有三十来万条——方阵要开出上百亿个格子，其中绝大多数永远空着，等于背着满袋空白纸行军。情报官很快想出更省的办法：只为每个据点立一份"邻居档案"，记录它直接连着谁。全部档案合起来就是邻接表。本节讲它的实现、账单与工业界的偏爱理由，顺带把两种表示放到同一张实验台上实测对比。

档案袋的结构

邻接表的核心是一个"顶点到邻居序列"的映射。无向图里，一条边要在两端的档案里各登记一条（甲的档案记乙，乙的档案记甲）；有向图里只在发出方的档案登记。加权图把邻居记录成"对方加权重"的二元组；多重图允许同一邻居出现多次——邻接表天然容得下平行边与自环，这是它比矩阵更"宽容"的地方。

账单与矩阵正好互补：

• 空间：与"顶点数加边数"同阶。对稀疏图（现实网络的常态），这是从平方级到线性级的瘦身。
• 枚举邻居：顺着档案直接读，耗时与该顶点的度数同阶——矩阵则要扫一整行，即使邻居寥寥。深度优先、广度优先、Prim、Dijkstra 等算法的时间账单全部以"枚举邻居"为计价单位，所以教科书上这些算法的复杂度都写成"顶点数加边数"的形式，其前提正是邻接表存储。
• 查邻：没有格子可看，必须在档案里找。若档案是无序列表，耗时与度数同阶；换成集合或有序结构可提速，代价是插入变慢。频繁查邻的场合，要么矩阵，要么邻接表加集合双轨。

手写实现

下面用字典加列表实现邻接表，这是竞赛代码与面试白板的标准形态：

class AdjListGraph:
    """支持有向或无向、带权的邻接表"""
    def __init__(self, directed=False):
        self.adj = {}          # 顶点 -> [(邻居, 权), ...]
        self.directed = directed

    def add_vertex(self, v):
        self.adj.setdefault(v, [])

    def add_edge(self, u, v, w=1):
        self.adj.setdefault(u, []).append((v, w))
        if not self.directed:
            self.adj.setdefault(v, []).append((u, w))

    def neighbors(self, u):
        return [v for v, _ in self.adj[u]]      # 枚举邻居：按度计价

    def weight(self, u, v, default=None):
        for nb, w in self.adj[u]:               # 查邻：按度翻找
            if nb == v:
                return w
        return default

g = AdjListGraph()
for u, v, w in [("营地","渡口",4), ("渡口","哨所",2), ("营地","哨所",7), ("哨所","高地",3)]:
    g.add_edge(u, v, w)

for place in ["营地", "渡口", "哨所"]:
    print(place, "的邻居档案:", g.adj[place])
print("营地 到 哨所 的路程:", g.weight("营地", "哨所"))
​

接下来做一场两种表示的对决实验：同一张随机图，分别用矩阵与表存储，实测内存占用，并统计"枚举全部邻居"的总代价：

import sys
import networkx as nx

# 造一张稀疏图：两千个顶点，每点平均约五个邻居
G = nx.gnm_random_graph(2000, 5000, seed=7)

# 表 vs 矩阵
adj_list = {u: list(G[u]) for u in G.nodes}
import numpy as np
adj_matrix = nx.to_numpy_array(G, dtype=np.int8)

size_list  = sum(sys.getsizeof(nb) for nb in adj_list.values())      # 档案本身
size_matrix = adj_matrix.nbytes                                       # 方阵字节
print(f"邻接表档案字节约 {size_list/1e6:.1f} MB，方阵 {size_matrix/1e6:.1f} MB")

# 枚举全部邻居的总代价：表=每点只看自己的档案；矩阵=每点都扫全行
total_deg = sum(len(nb) for nb in adj_list.values())
total_scan = 2000 * 2000
print(f"表：读 {total_deg} 条档案记录；矩阵：扫 {total_scan} 个格子")
​

数字会说明一切：稀疏图上，方阵的格子数是档案记录数的许多倍，且差距随顶点数增长越拉越大。这就是大规模图系统（图数据库、图计算引擎）几乎清一色采用邻接表或其变体的原因。

变体与工程细节

工业实现里，邻接表很少真用"字典套列表"，更常见的是数组前向星：把所有档案串在一条大数组上，另用一个头指针数组标记每个顶点的档案从哪里开始。它把零散的列表压成连续内存，缓存友好，是竞赛与图计算框架的常客。Python 的字典版胜在开发效率，教学与原型首选。

几个容易踩的细节。第一，无向图删边要同时删两端档案，漏删一半会导致"幽灵路"。第二，档案里若混入重复邻居（数据清洗不净），度数与握手定理校验会立刻露馅——上一章的体检函数在这里派上用场。第三，需要频繁查邻又想保持表结构时，可以并行维护一份"邻居集合"，插入删除双写，空间换时间。

表示互转的代价清单

三种表示既然各有地盘，实战就免不了互相搬运。把互转写成代码不难，难的是记住每次搬运都要付一次完整遍历的账——生产系统绝不轻易互转，选型时的深思熟虑就是为了避免运行时反复搬家：

def list_to_matrix(G):
    """邻接表 → 邻接矩阵：付一次全边遍历"""
    nodes = list(G.nodes)
    idx = {v: i for i, v in enumerate(nodes)}
    n = len(nodes)
    M = [[0] * n for _ in range(n)]
    for u, v, attr in G.edges(data=True):
        i, j = idx[u], idx[v]
        M[i][j] = attr.get("weight", 1)      # 无向图对称登记
        M[j][i] = attr.get("weight", 1)
    return nodes, M

nodes, M = list_to_matrix(g)
print("顶点次序:", nodes)
for row in M:
    print(row)

def matrix_to_edgelist(nodes, M, skip_zero=True):
    """邻接矩阵 → 边表：付一次全格扫描（含空格）"""
    edges = []
    for i, u in enumerate(nodes):
        for j in range(i + 1, len(nodes)):
            if M[i][j] or not skip_zero:
                edges.append((u, nodes[j], M[i][j]))
    return edges

print("边表:", matrix_to_edgelist(nodes, M))
​

两个函数的循环结构本身就是代价的证词：表转矩阵扫的是边（与边数同阶），矩阵转边表扫的是格子（与顶点数的平方同阶）——稀疏图上后者要为满屏的空白格子白白付费，这正是"能用表就别轻易转矩阵"的量化理由。把这份代价清单记在心里，下一章读遍历算法的复杂度声明时会处处遇到它的回声。

⚠️ 常见坑：把 networkx 的图对象直接当生产存储。它为灵活支付了沉重的对象开销，千万级边就会明显吃力。生产中常用稀疏矩阵（如压缩稀疏行格式）或专用图数据库；networkx 的定位是教学、原型与中小规模分析。

💡 关键直觉：看一个图算法的复杂度声明，先问"它按什么计价"。写成"顶点数加边数"的，默认邻接表；写成顶点数平方的（如 Floyd-Warshall），本质上在矩阵上作业。存储与算法是一对连体账单。

档案袋已经备好，但有些作战样式更适合把所有边摊成一张清单处理。下一节补齐第三种画法并给出完整选型决策。