一、图就是点加线

五个点 A 到 E，五条线：A 连 B、A 连 C、B 连 D、C 连 D、D 连 E。 画出来是一张网。没有根，没有上下级，只有「连没连」。 每个点连着几条线，叫它的度。演示里数了一遍：A 是 2，D 是 3，E 是 1。

这些数不是摆设。度大的点是枢纽，删掉它整个图可能就断成两半——网络规划、路网优化，看的都是这个。 教材说地图、社交关系、地铁线路都是图。共同点是：「谁和谁有关」比「谁比谁大」重要。

二、树是图的特例

树其实就是图，只是多两条限制：不能有圈，而且任意两点之间只有一条路。 所以树能说的「父子关系」，图说不了； 图能说的「互相连着」，树也经常说不了（树里两点之间只有一条路，图里可以有好几条）。 这个包含关系值得记住：树 ⊂ 图。所有对图成立的算法，在树上都能用；反过来不成立。

反过来说也成立：如果一个数据本来有层级，却硬按图来存，你会丢掉「谁是谁的上级」这条现成的信息， 每次都要重新算出来。能用树就别用图。

三、从 A 出发能走到哪些点

演示从 A 出发，走遍全部五个点，顺序是 A、B、C、D、E。 这个走法叫广度优先：先把一圈邻居全收进来，再收邻居的邻居。 它靠一个队列实现——先进先出，所以同一层的点会挨着处理。正是 3.2 那个队列。

换成堆栈就成了深度优先：一条路走到黑，走不动了再回头。同一张图，换个容器，走法完全不同。 这也是数据结构真正的位置：它不是主角，是算法的零件。选错容器，算法就换了性格。

四、专题 3：下标从 0 还是从 1

演示里那个小例子最能说明问题：days 存周一到周日。 从 0 开始时 days[0] 是周一；从 1 开始时 days[1] 是周二。 同一句「第 1 个」，两种约定给出两个答案。 这就是 off-by-one（差一错）的来源，也是所有下标错的统一名字。

想取「第 5 个」写成 days[5]，报 IndexError: list index out of range； 正解是 days[4]，星期五。

五、没有哪个更对，只有跟谁一致

从 0 开始不是「先进」，是为了省一次减法：地址能直接用下标乘出来。 从 1 开始也不是「落后」，是贴近人的数法。 所以这不是对错问题，是跟谁一致的问题。一门语言内部一致、一个项目内部一致，就不会出事。 真正会出事的是混着用：同一份数据，一半地方当下标 0 起、一半地方当 1 起。早晚错一次。

而且错的那次往往不报错——只是少算了一行、跳过了第一个。报错反而是好事，不报错才难查。 所以写循环时的第一条纪律：下标的范围和边界，先在纸上写清楚再写代码。

六、动手 Demo：一张五个点的图，加上下标 0 与 1 的对照

先用邻接表把五个点的图存起来，数一数每个点连着几条线。 再从 A 出发广度优先走一遍，看能不能走到全部五个点。 最后把「第 1 个」在下标 0 和下标 1 两种约定下各试一次。

from collections import deque

g = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'],
     'D': ['B', 'C', 'E'], 'E': ['D']}
for k in g:
    print(k, '连着', g[k], '共', len(g[k]), '条')

seen, q, order = {'A'}, deque(['A']), []
while q:
    v = q.popleft()
    order.append(v)
    for w in g[v]:
        if w not in seen:
            seen.add(w)
            q.append(w)
print('广度优先', ' -> '.join(order), '共', len(seen), '个点')

days = ['周一', '周二', '周三', '周四', '周五', '周六', '周日']
print('下标 0 起：第 1 个是', days[0])
print('下标 0 起：第 5 个是', days[4])
print('下标 1 起：第 1 个是', days[1])
try:
    days[5]
except IndexError as e:
    print('写 days[5] 会报错：', e)

实跑输出：

--------------------------------------------------------------------
图，以及下标从 0 还是 1
--------------------------------------------------------------------


  ① 图就是一堆点加一堆连线
  --------------------------------------------------------------------
  A-B  A-C  B-D  C-D  D-E
  这个图有 5 个点、5 条边（每条算一次）

| 点 | 连着谁 | 几条线 |
|---|---|---:|
| A | B、C | 2 |
| B | A、D | 2 |
| C | A、D | 2 |
| D | B、C、E | 3 |
| E | D | 1 |

  树是图的一种特例：树不能有圈，图可以有。地图、社交关系、地铁线路都是图。

  ② 从 A 出发，能走到哪些点
  --------------------------------------------------------------------
  广度优先走一遍：A -> B -> C -> D -> E
  能到达 5 个点（全部）
  先把一圈邻居都收进来，再收邻居的邻居——这就是广度优先。换成堆栈就变成一条路走到底，那是深度优先。

  ③ 下标从 0 还是从 1，差别在哪
  --------------------------------------------------------------------
  从 0 开始：第 1 个是 days[0] = 周一
  从 1 开始：第 1 个是 days[1] = 周二
  同一句「第 1 个」，两种约定给出两个答案。这就是 off-by-one 的来源。
  想取「第 5 个」写成 days[5]：IndexError: list index out of range
  正解是 days[4] = 周五

| 语言／场景 | 起始下标 | 原因 |
|---|---|---|
| C、Java、Python | 0 | 地址等于首地址加下标乘大小 |
| Fortran、MATLAB | 1 | 当年给数学家和工程师用 |
| Excel 单元格 | 1 | 人看的第一行就是第 1 行 |
| 书页码 | 1 | 没有第 0 页 |

  没有哪个更对，只有「跟谁一致」。
  混着用才是灾难——同一份数据两套下标，早晚会错一次，而错的那次往往不报错，只是少算了一行。

①g 这个字典叫邻接表：每个点当键，值是「它连着谁」。图最常用的存法就这一种。 ②广度优先那段里 seen 必须在入队时就记上，不能等出队。否则同一个点会被好几个邻居重复塞进队列。 ③走出来的顺序 A B C D E 正好是按层：先 A，再 A 的邻居 B、C，再 B、C 的邻居 D，最后 E。 ④最后一行那个下标 5 故意留在代码里——它越界了，正确写法是 4。这就是 off-by-one 最常见的样子。

30 秒实验

1. 把 deque 换成堆栈（q.pop()），看走出来的顺序变成什么，那就是深度优先。
2. 给图加一条 E 连 A 的线，看广度优先的结果还一样不一样。
3. 手算一下：days 有 7 个元素，合法下标是 0 到几？把它写下来再验证。

常见误区

1. 「图比树高级。」树是图的特例，有层级的数据用树更省事。能用树就别用图。
2. 「下标从 0 开始是编程语言的怪癖。」是为了省一次减法，地址能直接乘出来。
3. 「下标错会报错，好查。」很多下标错不报错，只是少算一行。这才是它讨厌的地方。

第 3 章五种结构到此齐了。 下一章开始动手写算法本身：从最小的样子——循环加累加——开始，一路做到排名和时间差。

• ☐ （本篇完，下一篇 4.1 循环：算法的基础）

相关笔记

• 树与二叉树
• 堆栈与队列
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引