图的基础 | ReConcept Lab

问题从哪里来

想象一栋楼里有很多房间，房间之间由门连接。现在不需要记录每个房间的形状，只需要回答一个小问题：从这个房间出发，一步能到哪些房间？

房间变成节点现在只保留房间和直接相连的门，先忽略房间大小、走廊形状和实际距离。

图模型保留直接连接关系，暂时丢掉当前问题不需要的平面图细节。

第一个朴素想法

一个直接做法是写路线卡片，比如 “Lobby -> Hall -> Lab” 或 “Cafe -> Hall -> Lab”。路线少的时候，这很清楚。

路线卡片很自然少量路线建议很容易读，但它把原始结构和人为决策混在了一起。

大厅 -> 走廊 -> 实验室不变

原始建议卡片

楼梯 -> 咖啡区 -> 走廊 -> 实验室不变

原始建议卡片

咖啡区 -> 走廊 -> 实验室不变

原始建议卡片

路线卡片描述完整行程，而不是可复用的局部事实。

它为什么会痛

现在新增一扇从 Cafe 到 Lab 的门。建筑事实只变了一次，但多张路线建议都要复查：有的仍然有效，有的已经过期，还有新的直接路线缺失。

新增一扇门，建议就要复查刻意加入 Cafe-Lab 这条变体边后，图事实改变了，路线卡片需要人工复查。

大厅 -> 走廊 -> 实验室不变

仍然有效。

楼梯 -> 咖啡区 -> 走廊 -> 实验室有效但需复查

仍能到实验室，但现在需要复查。

咖啡区 -> 走廊 -> 实验室过期

建议应改成 Cafe -> Lab。

咖啡区 -> 实验室缺失

缺少新的直接建议。

图事实改变了；建议卡片现在需要复查。

路线卡片是人工维护的建议，不是算法。真正的问题是，完整路线把稳定的结构和具体走法混在了一起。

核心发明

图（graph）存储局部关系事实。节点（node）表示一个对象，边（edge）表示一个直接关系，邻接关系（adjacency）记录一个节点的直接邻居。

选择模型保留什么这一页保留房间和直接连接的门，不把每条完整路线都存下来。

保留房间、直接连接的门

丢掉房间大小、走廊弯曲、装饰

本页不存完整路线建议，例如 Cafe -> Hall -> Lab

图是一种建模选择，不是对建筑的必然复制。

互动可视化

邻居检查器

选择一个房间，只查看算法下一步能检查的一步邻居。

选中: 走廊

一步邻居:大厅实验室咖啡区

走廊大厅, 实验室, 咖啡区

形式化版本

图常写作 G = (V, E)。V 是顶点或节点集合，E 是边集合。在这一页里，Lobby 是 V 中的节点，Lobby-Hall 是 E 中的一条边。

从图像到记号大厅成为 V 中的一个元素；大厅-走廊这扇门成为 E 中的一条边。

形式记号记录的是和图像相同的直接事实。

边可以是无向的，也可以是有向的。像 ["lobby", "hall"] 这样的无向边会产生两个邻居事实：Lobby 的行列出 Hall，Hall 的行也列出 Lobby。

实现草图

存完整路线建议很脆弱：

const routeAdvice = [["cafe", "hall", "lab"]];

邻接表（adjacency list）改为存局部事实：

const adjacency = {
  lobby: ["hall", "stairs"],
  hall: ["lobby", "lab", "cafe"],
  lab: ["hall"],
  stairs: ["lobby", "cafe"],
  cafe: ["hall", "stairs"]
};

存局部事实，而不是每次行程Cafe 的邻接行比一组完整路线建议更容易随结构变化而维护。

路线建议[["cafe","hall","lab"], ...]

邻接关系cafe: ["hall", "stairs"]

大厅走廊, 楼梯

走廊大厅, 实验室, 咖啡区

实验室走廊

楼梯大厅, 咖啡区

咖啡区走廊, 楼梯

一条存储的无向边会产生两个邻居事实。

表示不变量

当每一扇直接门都按约定出现在表示里时，这个表示就是正确的。对于无向图，每扇门都要出现在两个房间的邻接行中。

邻接表每一行列出一步门就能到达的房间。

大厅走廊, 楼梯

走廊大厅, 实验室, 咖啡区

实验室走廊

楼梯大厅, 咖啡区

咖啡区走廊, 楼梯

走廊直接连接大厅、实验室和咖啡区。

复杂度和取舍

当每个节点只有少量邻居时，邻接表很紧凑。邻接矩阵（adjacency matrix）像一张查询表：选一行、选一列，就能读出是否有直接边。

表示法对比

结果: 选择一个操作，对比两种表示法。

邻接表

大厅走廊, 楼梯

走廊大厅, 实验室, 咖啡区

实验室走廊

楼梯大厅, 咖啡区

咖啡区走廊, 楼梯

邻接矩阵

行表示出发房间，列表示到达房间。
	大厅	走廊	实验室	楼梯	咖啡区
大厅	0	1	0	1	0
走廊	1	0	1	0	1
实验室	0	1	0	0	0
楼梯	1	0	0	0	1
咖啡区	0	1	0	1	0

邻接矩阵行和列是查询标签，不是物理位置。

行表示出发房间，列表示到达房间。
	大厅	走廊	实验室	楼梯	咖啡区
大厅	0	1	0	1	0
走廊	1	0	1	0	1
实验室	0	1	0	0	0
楼梯	1	0	0	0	1
咖啡区	0	1	0	1	0

(Lab, Cafe) 单元格是 0，因为没有直接门。

有向和带权变体

有向边只改变一个方向的邻接行。带权边会增加代价标签，但不会改变两个节点是否相邻。

单向边Cafe -> Lab 只改变 Cafe 这一行，不会自动加入 Lab -> Cafe。

方向决定哪一行得到这个邻居。

代价标签不改变邻接关系即使代价分别是 2 和 5，走廊和楼梯仍然都是大厅的一步邻居。

权重改变代价，不改变是否相邻。

常见混淆

边是一条直接连接。路径（path）是多条边串起来。邻居（neighbor）只隔一条边。可达节点可能需要走多条边。

四个常见混淆边与路径、邻居与可达、有向反转、权重与邻接。

边 vs 路径

Hall-Lab 是一条边；Lobby -> Hall -> Lab 是一条路径。

邻居 vs 可达

Lab 可以从 Lobby 到达，但不是 Lobby 的邻居。

有向反转

Lab -> Hall 不会自动允许 Hall -> Lab。

权重 vs 邻接

Lobby-Hall 代价 2 和 Lobby-Stairs 代价 5 都是一步邻居。

同一个例子让词汇始终有具体参照。

图谱连接

BFS 会反复使用图的基础问题：从当前节点出发，哪些相邻节点可以下一步访问？Dijkstra 之后会保留节点、边和邻接关系，再加入边的代价来选择最便宜的下一批前沿。

预测练习

Lobby 的一步邻居有哪些？
如果 Cafe -> Lab 是一条单向边，哪一行邻接表会改变？
在基础例子中，矩阵单元格 (Lab, Cafe) 是多少？
Lobby -> Hall -> Lab 是一条边，还是一条路径？

图谱连接 : 图的基础