一、点和边，就这两样东西

一个图由两样东西组成：点（顶点） 和 边。边可以带方向，也可以带权。 这四样一组合，就是图论里最常见的四种图：

二、同一张图，三种存法

Demo 第一段用八个点、12 条带权边，把它存了三遍。 第一种是邻接矩阵：开一个 n 乘 n 的方阵，第 i 行第 j 列放 i 到 j 的权，没边就放 0。 八乘八是 64 个格子，只有 24 个填了东西（每条边填两格，因为无向图两边都算），填满率 38%。 第二种是邻接表：每个点后面挂一串「我的邻居以及到他那条边的权」。 没边的地方根本不出现，所以八行里加起来也只有 24 条。 第三种是边表：把 12 条边原样列成 12 行三元组。 最省地方，但查「A 的邻居有谁」得把整张表从头扫一遍。 三种存法不是口味差别，是代价差别。点数一多，矩阵按 n² 涨，邻接表按边数涨。 Demo 第三段把这件事摆出来了：

三、数一数每个点连着几条边

一个点连着几条边，叫它的度。Demo 里八个点的度是：

| 点 | A | B | C | D | E | F | G | H | |---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| | 度 | 2 | 3 | 4 | 4 | 4 | 3 | 2 | 2 | 八个度加起来是 24，正好是边数 12 的两倍。这不是巧合：每条边有两个头， 数度的时候被两头的点各数了一次。所以有个恒等式：所有点的度之和等于边数的两倍。 接着就是一个很漂亮的判据。 1736 年欧拉解决哥尼斯堡七桥问题时问的是： 能不能从某点出发，每条边正好走一次，最后回到起点？答案全看奇度点的个数：

四、树：连得通，又不绕圈

n 个点要连成一整块（连通），最少要 n−1 条边。正好 n−1 条又连通，就一定没有环； 此时再多任何一条，环就出现了。

五、人工智能里的图

图不是数学系的玩具，它是这一行里最常被借用的结构：

六、动手 Demo：把一张图存三遍，再数它的度

这段代码只做三件事：建图、数度、算代价。建图那几行同时填了邻接矩阵和邻接表， 所以能直接对比两种存法的差别。 最后两段不看代码，看数：一张表是「点变多时两种存法差多少」，一张表是「一笔画要几个奇度点」。

NAMES = 'ABCDEFGH'
EDGES = [(0, 1, 2), (0, 2, 5), (1, 2, 1), (1, 3, 4), (2, 3, 2), (2, 4, 7),
         (3, 4, 1), (3, 5, 3), (4, 5, 6), (5, 6, 2), (6, 7, 4), (4, 7, 9)]

n = len(NAMES)
M = [[0] * n for _ in range(n)]        # 邻接矩阵
adj = {i: [] for i in range(n)}        # 邻接表
for a, b, w in EDGES:
    M[a][b] = M[b][a] = w
    adj[a].append((b, w))
    adj[b].append((a, w))

deg = [len(adj[i]) for i in range(n)]  # 度 = 邻居个数
assert sum(deg) == 2 * len(EDGES)      # 度之和恒等于边数的两倍

odd = [i for i in range(n) if deg[i] % 2 == 1]
# 奇度点 0 个或 2 个才画得出一笔画
print('奇度点', [NAMES[i] for i in odd])

# 稀疏与稠密的代价：矩阵按 n² 涨，邻接表按边数涨
for m in (100, 1000, 10000, 100000):
    e = m * 3 // 2                     # 平均度 3
    print(m, m * m, 2 * e)

实跑输出：

--------------------------------------------------------------------
把关系画成点和边
--------------------------------------------------------------------
==============================================================

[1] 同一张图，三种存法

  八个点、12 条带权边：
    A-B 2  A-C 5  B-C 1  B-D 4  C-D 2  C-E 7  D-E 1  D-F 3  E-F 6  F-G 2  G-H 4  E-H 9

  【邻接矩阵】一下标一条边，格子里放权，没边放 0：

      A     B     C     D     E     F     G     H    
    A     ·     2     5     ·     ·     ·     ·     ·    
    B     2     ·     1     4     ·     ·     ·     ·    
    C     5     1     ·     2     7     ·     ·     ·    
    D     ·     4     2     ·     1     3     ·     ·    
    E     ·     ·     7     1     ·     6     ·     9    
    F     ·     ·     ·     3     6     ·     2     ·    
    G     ·     ·     ·     ·     ·     2     ·     4    
    H     ·     ·     ·     ·     9     ·     4     ·    

  一共 64 个格子，里面填了 24 个非零（每条边填两格）。
  填满的比例 38% —— 剩下 40 个格子是空的。

[2] 【邻接表】只存有的那些：

    A    B(2)、C(5)
    B    A(2)、C(1)、D(4)
    C    A(5)、B(1)、D(2)、E(7)
    D    B(4)、C(2)、E(1)、F(3)
    E    C(7)、D(1)、F(6)、H(9)
    F    D(3)、E(6)、G(2)
    G    F(2)、H(4)
    H    E(9)、G(4)

  每个点后面跟的条数叫「度」：A=2  B=3  C=4  D=4  E=4  F=3  G=2  H=2
  所有度加起来 = 24，正好是边数的两倍（每条边被两头的点各数一次）。

  第三种存法是【边表】，就是把 EDGES 原样列出来：12 行三元组。
  它最省地方，但查「A 的邻居有哪些」得把整张表扫一遍。

[3] 点一多，两种存法差多少个数量级

    点数      边数             矩阵格子       邻接表条数
    ----------------------------------------------------------
    100       150（稀疏）      10000          300
    1000      1500（稀疏）     1000000        3000
    10000     15000（稀疏）    100000000      30000
    100000    150000（稀疏）   10000000000    300000

  矩阵那一列按 n² 涨，邻接表按边数涨。
  一百万个点、平均度 3 的图：矩阵要 1e+12 个格子（一万亿），
  邻接表只要 300 万条。差 6 个数量级。

  所以真实世界的图 —— 社交网络、路网、网页链接 —— 几乎都用邻接表。
  它们的共同点是【稀疏】：一个点的朋友就那么几十个，
  哪怕全网有十亿人。矩阵里 99.99% 的格子永远是 0。

[4] 奇度点决定能不能「一笔画」

  欧拉 1736 年解决哥尼斯堡七桥问题，用的就是这个判据：
  从某点出发，每条边正好走一次，能不能回到起点。

    奇度点的个数        结论
    ----------------------------------------------------
    0 个                能，而且能回到起点（欧拉回路）
    2 个                能，但从一个奇点进、另一个奇点出
    4 个                不能（多于两个奇点，一定走不通）

  上面这张图里度是奇数的点：B(3)、F(3)
  奇度点 2 个，所以画得出来。

  这个判据的道理不难想：中间经过一个点，进去一条边、出来一条边，
  用掉的是两条，所以中间点的度必须是偶数；只有起点和终点可以是奇数。

[5] 树：边数最少还能连通的图

    点数      连通需要的边      多一条会怎样
    ----------------------------------------------------
    5         4 条              出环
    10        9 条              出环
    100       99 条             出环
    1000      999 条            出环

  n 个点要连通，至少要 n−1 条边，这叫「树」。
  正好 n−1 条且连通，就一定没有环；多出任何一条，一定出现环。
  这三件事是等价的 —— 「连通」「无环」「边数 = 点数 − 1」，
  满足任意两条就自动满足第三条。

  这条性质在算法里到处用。比如判断「加这条边会不会出环」，
  只要看两个点是不是已经连通 —— 这就是最小生成树算法（Kruskal）的核心。

  最后提一句这节最容易被忽略的事实：
  图的边数最多是 n(n−1)/2，也就是 n² 量级。
  所以任何「遍历所有边」的算法，最坏情况就是平方级——
  想更快，必须利用「图是稀疏的」这个前提。

第一段最值得记的是那个 24。八个点、12 条边，度加起来正好 24。 这个恒等式（度之和等于边数两倍）不是巧合，是「每条边有两个头」的直接后果。 它还是个很好的自检：任何图算法算出来的度数之和如果是奇数， 那一定是代码写错了——奇数不可能是偶数倍。 第三段那张表是这一节最有用的一张。它说明「用什么存」不是风格问题： 同样的图，矩阵存法和邻接表存法在一百万个点时差了六个数量级。这也解释了为什么图数据库、 社交网络的存储层从来不存矩阵。 第四段那两个奇度点是欧拉判据的全部内容。B 的度是 3，F 的度也是 3，其余都是偶数， 所以从 B 出发能一笔画到 F。 顺手可以验证一下：把 B 到 D 那条边删掉，B 和 D 的度都从 3 和 4 变成 2 和 3，奇度点还是两个， 但换成了 D 和 F——仍然画得出来。 第五段那句「遍历所有边的算法最坏是平方级」要理解成条件句。平方级只在稠密图上成立； 稀疏图上按边数算，是线性的。所以「图算法快不快」这个问题，离开「这张图稀不稀疏」根本没法回答。

30 秒实验

1. 在 EDGES 里加一条 B-G（权 5），重跑。 度会变成 B=4、G=3，奇度点仍然是两个（F 和 G），还能一笔画； 但非零格子的比例会从 38% 涨到 41%。顺手验证「度之和 = 边数两倍」这个恒等式还成立。
2. 把 EDGES 换成完全图（八个点两两相连，28 条边），重跑第三段那个表。 矩阵格子不变还是 64，邻接表条数会从 24 涨到 56。这一步能让你看见： 矩阵的代价只跟点数有关，邻接表的代价跟边数有关。
3. 把树那一段的点数改成 1000000。 n−1 条边这个结论不变，但你会想清楚一件事：一百万个点的树，光存边就要一百万条， 而矩阵要一万亿格——这就是为什么「连通性判断」从不用矩阵做。

常见误区

1. 以为图一定要画出来才叫图。图是「点集 + 边集」这两个东西，画出来只是为了给人看。 一个有一百万个点的图，你永远画不出来，但它是个完全正常的图。
2. 以为邻接矩阵更「正规」，因为它是矩阵能进线性代数。 绝大多数真实的图都不是方阵能好好表示的——一万个点就是一亿个格子，而且里面 99.99% 是 0。 谱方法（图神经网络里那套）确实要用矩阵，但那是算的时候临时展开，存的时候还是邻接表。
3. 以为「度」就是「重要性」。度只数了「连了几条」，不区分连的是谁。 PageRank 之所以比度数靠谱，正是因为它把「谁连你」也算进去了。度是入口，不是终点。
4. 以为「树」是一种树。树在数据结构里指「有父子关系的树」，在图论里只是「连通且无环的图」。 前者是后者的特例（那个树也是一张图）， 但后者不一定是前者——图论里的树没有根，也没有父子。

这一节把「关系」存成了点和边。 下一节让图动起来：从一个点出发，沿着边走，找另一个点——这就是搜索。广度优先、深度优先、 Dijkstra、A*，四种走法会在同一张地图上比一次。

• ☐ （本节完，下一节 5.2 图谱搜索和最优化）

相关笔记

• 图谱搜索和最优化
• 相似度的计算
• 知识库
• 📘 图解人工智能 · 索引