图论入门：把连接关系画出来

下面有六个地点。字母只是方便我们指认它们的名字：$A$ 是家，$E$ 是学校。一条线表示两端有直接相通的路。现在每条路都可以往返走；线画得长或短，都没有记录路程。

这些代表地点的点叫作顶点，代表直接连接的线叫作边。没有连线的两个点不能一步走到，但仍可能绕经别的点到达。这样，我们把“能不能直接到达”的信息单独留下来了。

先在下面选择一个地点，看它连着哪些边。再点选边的按钮，增加或移除一条连接。地点的位置始终不变，所以你能看清究竟是哪条关系变了。

现在固定回最初的七条路。我们先问一个很小的问题：从某个地点出发，有几条路可以直接走？与一个顶点相接的边数，叫作这个顶点的度。这里没有自己连回自己的边，也没有同一对地点之间的多条边。

例如，$A$ 接着 $AB$、$AC$ 两条边，所以它的度是 $2$。下面每按一次“下一步”，就加入一条边，同时在它的两端各记一次。金色线是刚加入的边；表格保留已经记下的次数。

为什么总次数一定是边数的两倍？因为每条边有两个端点。无论端点属于哪两个地方，我们都在一端记一次、另一端再记一次。因此，每加一条边，总次数增加 $1+1=2$；把所有边处理完，就得到下面的等式。

这常被叫作握手定理：一次握手，参与的两个人各记一次。我们用每条边的两个端点推出了它，所以它适用于任意一个本页这种有限无向图，而不只适用于七条路的例子。

只看直接相连的地方还不够：学校和家没有直接连接，但我们可以经过商店和图书馆。沿着相接的边依次走，就是一条行走路线。路线的长度在这里指走过的边数；从 $A$ 到 $B$ 走一条边，再到 $D$ 走一条，再到 $E$ 走一条，所以共走 $1+1+1=3$ 条边。

我们把没有重复顶点的路线称为简单路径。如果从一个点出发，最后回到它，途中没有重复别的顶点，并且至少经过三条边，就得到本页这种无向简单图里的环。比如 $A,B,D,C,A$：最后一个 $A$ 只是回到起点，其他地点各经过一次。

下面只允许你选择与当前位置直接相连的下一个地点。试着从家走到学校；重置后，你还可以试着从学校走回家。数字标签表示经过顶点的次序；同一点如果经过多次，下方的路线仍会完整保留。

如果任意两个顶点之间都能找到路径，我们说这个无向图是连通的。把学校两侧的路都移除，学校就与其他地方断开；即使另外五个地方仍互相可达，整个图也不再连通。

还有一种情况是单行路：能从 $A$ 去 $B$，并不表示能从 $B$ 回 $A$。我们用箭头记录允许的方向，得到有向图。后面的寻找过程也能遵守箭头，但“能到达”必须指定出发点和方向。

随意试路容易反复走到同一个地方。我们可以把已经发现、但还没检查它周围道路的地点，按发现顺序排成一队。先加入的地点先处理，这样的等候记录叫作队列。下面队首在左边，新发现的地点放在右边。

一开始，我们只知道起点本身，因此把起点标成 $0$ 步，再放进队列。接着取出队首，逐条检查它允许走出的连接。遇到还没发现的地点，就记下从哪里找到它、到达它需要几步，再把它放到队尾。遇到已经发现的地点，就不再排一次队。

为什么新地点的步数要加 $1$？我们已经知道一条到达当前地点的路线，再沿刚检查的一条边走过去，就比那条路线多走一条边。比如当前地点记了 $2$ 步，新地点就记 $2+1=3$ 步。

这种按距离一层一层寻找的方法，叫作广度优先搜索，英文简称 BFS。只有当前这一层处理完，才会处理下一层。用“下一步”逐条查看队列和道路；它不会自行前进。灰色是尚未发现，绿色是已发现，金色边是当前正在检查的连接。

我们现在解释，为什么刚才记下的步数确实最少。起点需要 $0$ 步；所有与起点直接相邻的地点，都在处理起点时被发现，所以它们需要 $1$ 步。队列使这些一步能到的地点，全部排在后来发现的两步地点前面。

把这个理由继续往下用：当我们处理第 $k$ 层，也就是最少走 $k$ 条边能到的那些地点时，所有更近的层都已经处理过。一个尚未发现的邻点可以用 $k+1$ 步到达，因为我们在已有的 $k$ 步后加了一条边。

它会不会有更短的路线？假如有，那条更短路线的倒数第二个点，最少步数就小于 $k$。这个点早已经被处理过，连接也已检查过；目标应当那时就被发现。这与“现在还没发现”矛盾。所以新记录的 $k+1$ 步就是最少步数。

从第 $0$ 层开始，这个理由保证每一层都正确。每个新发现的点只入队一次，而顶点总数有限，所以队列最终会空。此时还没发现的点确实不可达：若存在一条通向它的路线，沿路线找第一个没发现的点，它前面的点本应在检查连接时发现它。

这里最少的是边数。如果每条路的时间相同，最少边数也给出最少时间；如果时间不同，就不能这样推断。比如直达路花 $10$ 分钟，经过中间一站的两段路各花 $2$ 分钟，两段合计 $2+2=4$ 分钟，比直达更快。把时间等数值记在边上，叫作边的权重；BFS 的层数没有把这些数值相加。

试着写下你的答案。下面的展开内容给出了计算过程，可以用来核对。答案使用本页最初的七条边；你可以回到上面的图逐条检查。