第一章：图——世界的另一种语言
想象这样一个场景：周一早晨，你从家出发，步行穿过小区门口的便利店，买了一份热腾腾的豆浆和油条，然后坐地铁前往学校。途中，你需要在建国路站换乘一次线路，最后在学校的站下车，步行进入校门。这看似再普通不过的早晨通勤，其实暗藏着一种极其重要的结构——如果我们把途中的每一个地点（家、便利店、地铁站、学校）看作一个点，把连接这些地点的路径（街道、地铁线路、人行道）看作线，那么这张由点和线构成的"地图"，正是我们今天要深入探讨的主题：图（Graph）。
从欧拉七桥说起：图论的开端
要理解图的概念，我们不妨把时间拨回到1736年的普鲁士城市哥尼斯堡（今俄罗斯加里宁格勒）。这座城市被普雷格尔河分割成四个陆地部分，河上有七座桥梁连接这些区域。当时的市民热衷于讨论一个有趣的问题：能否找到一条路线，使得你从任意一点出发，沿着河岸和桥梁行走，最终恰好经过每座桥一次后回到出发点？这就是著名的“哥尼斯堡七桥问题”。
数学家莱昂哈德·欧拉（Leonhard Euler）对这个问题产生了浓厚的兴趣。他在1736年发表了一篇论文，证明了这样的路线是不存在的。欧拉的论证方法极具开创性：他将地图中的陆地抽象为“点”（也就是我们今天要学习的“节点”或“顶点”），将桥梁抽象为连接这些点的“线”（也就是“边”）。通过这种抽象，原本复杂的地理问题被转化为一个纯粹的数学问题。
欧拉证明了，如果要一次性走遍所有边而不重复，那么图中最多只能有两个奇数度的节点（度是指连接该节点的边的数量）。在哥尼斯堡的七桥问题中，四个陆地节点都是奇数度（分别是5、3、3、3），因此这样的路径根本不存在。
这篇仅有两页纸的论文，被公认为图论（Graph Theory）这门数学分支的开端。欧拉用到的这种将实际问题抽象为“点和线”结构的思维方式，至今仍是计算机科学和数学领域最重要的方法论之一。
节点与边：图的基本构成
在图论中，图是由节点（Vertex，也称为顶点）和边（Edge，也称为弧）组成的数据结构。节点代表了问题中的实体或对象，而边则代表了这些实体之间的关系或连接。
举几个贴近生活的例子来帮助理解：
社交网络是最直观的例子。在这个场景中，每个用户就是一个节点，如果用户A和用户B互相关注或成为好友，我们就用一条边连接节点A和节点B。在微信这样的社交平台中，节点代表的是一个个真实的人，而边则代表着“好友关系”或“关注关系”。
道路交通系统同样可以用图来表示。每个路口是一个节点，每条道路是一条边。如果道路是双向的，那么对应的边也是双向的（称为无向边）；如果某些道路是单向的，那就需要用带箭头的边来表示方向（称为有向边）。城市导航系统如高德地图或百度地图，其底层就是依赖图结构来计算最短路径的。
分子结构是化学领域的经典案例。在表示分子时，每个原子是一个节点，原子之间的化学键就是边。水分子（H₂O）可以表示为一个包含三个节点的图：两个氢原子节点和一个氧原子节点，氢原子和氧原子之间各有一条边相连。科学家们正是通过分析这种图结构，来研究分子的化学性质和反应规律的。
计算机网络中的图结构同样无处不在。互联网中的每台服务器或计算机是一个节点，网络中的网线、Wi-Fi信号、路由器等连接设备形成了边。网络工程师需要解决的问题，如如何优化数据传输路径、如何提高网络可靠性，都依赖于对这种图结构的深入分析。
有向与无向：边的方向性
在图的结构中，边的方向性是一个至关重要的概念。根据是否考虑方向，图可以分为两大类：
无向图（Undirected Graph）
在无向图中，边没有方向性。如果节点A和节点B之间存在一条边，那么这条边可以双向通行。这意味着从A到B和从B到A是等价的。
典型的无向图应用场景包括：
- **朋友关系**：在微信中，你添加了某人为好友，双方的联系是对等的
- **道路网络**：大多数城市街道都是双向通行的
- **以太网连接**：两台直接相连的计算机可以互相通信
- **化合物中的单键**：化学键通常没有方向性
数学上，无向图中的边可以表示为一个无序对，记作$\{A, B\}$。
有向图（Directed Graph，也称为Digraph）
在有向图中，每条边都有明确的方向，从起始节点指向终止节点。这种方向性使得有向图能够表达更加丰富和精确的关系。
有向图的典型应用场景包括：
- **关注关系**：在微博或抖音上，用户A关注用户B，并不意味着B也关注A
- **网页链接**：网页A链接到网页B，但网页B不一定回链到A
- **工作流程**：任务A必须在任务B开始之前完成，存在先后依赖关系
- **交通系统中的单行道**：某些道路只允许单向行驶
数学上，有向图中的边可以表示为一个有序对，记作$(A, B)$，其中A是边的起点（尾部），B是边的终点（头部）。
用一个具体的社交网络例子来说明：假设小明、小红、小刚三位同学构成了一个小型的社交圈子。在这个圈子中：
- 小明和小红是互相关注的朋友关系（双向边）
- 小红关注了小刚，但小刚没有回关（单向边，从小红指向小刚）
- 小明和小刚互相关注（双向边）
如果用有向图来表示，其中$A \to B$表示A关注B，那么这个社交网络可以表示为：
```mermaid graph LR A["小明 👤"] <--> B["小红 👤"] B --> C["小刚 👤"] A <--> C ```
如果仅用无向图来表示同样的关系，那就只能表达“是否存在联系”，而无法区分“谁关注了谁”。
有权与无权：边的度量
除了方向性之外，边是否带有“权重”也是图的重要属性。
无权图（Unweighted Graph）
在无权图中，所有边被视为具有相同的“成本”或“长度”。边的存在与否是唯一重要的信息。
无权图特别适用于那些只需要关心“是否存在连接”的场景：比如，判断两个用户之间是否通过共同好友间接认识（社交网络分析中的“度数”计算）；或者检查网络中的两台设备之间是否存在通信路径（网络连通性分析）。
有权图（Weighted Graph）
在有权图中，每条边都关联着一个数值，称为权重（Weight）。权重可以根据实际问题的需要，代表距离、时间、成本、容量等任何可量化的度量。
有权图的应用极为广泛：
导航系统中的每条道路都有关联的行程时间或距离权重。当你在手机地图上搜索从家到学校的路线时，导航系统会综合考虑各条道路的权重，计算出时间最短或距离最短的最优路径。
航空网络中的边权重代表两个城市之间的飞行距离或机票价格。如果你计划一次跨国旅行，规划最优航线就需要考虑这些权重因素。
物流配送问题中，边权重可能代表运输成本、时间成本或风险成本。物流公司需要综合这些因素，优化配送路线以降低成本。
蛋白质相互作用网络中，边的权重可以表示两个蛋白质之间相互作用的强度或置信度。这在生物信息学和药物研发中非常重要。
一个直观的对比例子：假设从家到学校有两条路径。路径A需要经过两段路：家到地铁站（步行10分钟）和地铁站到学校（地铁25分钟），总耗时35分钟。路径B是直接步行，虽然只需要一段路，但需要50分钟。如果我们把“时间”作为权重：
- 路径A的总权重：10 + 25 = 35分钟
- 路径B的总权重：50分钟
在这种情况下，系统会选择路径A，因为它的时间总权重更小。
图的数学表示方法
了解了图的基本概念之后，我们来看看如何用数学和计算机语言来表示图结构。主要有三种常用的表示方法：邻接矩阵、邻接表和边列表。
邻接矩阵（Adjacency Matrix）
对于一个有$n$个节点的图，邻接矩阵是一个$n \times n$的二维数组。矩阵中的第$i$行第$j$列元素表示节点$i$和节点$j$之间的关系。
对于无权图：
$$A_{ij} = \begin{cases} 1 & \text{如果节点 } i \text{ 和节点 } j \text{ 之间存在边} \\ 0 & \text{否则} \end{cases}$$
对于有权图，矩阵中存储的是边的权重，如果两节点之间不存在边，通常用0或无穷大（$\infty$）来表示。
让我们用一个具体的例子来说明。假设有四个节点A、B、C、D，它们之间的连接关系如下：
```mermaid graph LR A["A"] <--> B["B"] B --> C["C"] C --> D["D"] A --> D ```
对应的邻接矩阵为：
$$ \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} $$
邻接矩阵的优点是查询高效：判断任意两个节点之间是否存在边只需要O(1)的时间复杂度。但它的缺点也很明显——对于节点数量很多但边数量较少的稀疏图，会浪费大量的存储空间。邻接矩阵的空间复杂度是$O(n^2)$，其中$n$是节点数量。
邻接表（Adjacency List）
邻接表是一种用链表或动态数组来表示图的方法。对于图中的每个节点，邻接表存储一个列表，包含所有与该节点直接相连的邻居节点。
对于同样的四个节点A、B、C、D：
```mermaid graph LR A["A"] <--> B["B"] B --> C["C"] C --> D["D"] A --> D ```
用邻接表表示：
``` A: → B → D B: → A → C C: → B → D D: → C → A ```
如果是有权图，邻接表中还需要存储每条边的权重：
``` A: → (B, weight=3) → (D, weight=7) B: → (A, weight=3) → (C, weight=2) C: → (B, weight=2) → (D, weight=5) D: → (C, weight=5) → (A, weight=7) ```
邻接表的优点是空间效率高：对于稀疏图，只需要存储实际存在的边，空间复杂度为$O(n + m)$，其中$n$是节点数量，$m$是边的数量。但查询两个特定节点之间是否存在边时，需要遍历邻接表，时间复杂度为$O(degree)$，其中degree是节点的度数。
边列表（Edge List）
边列表是最简单直观的表示方法，它只存储所有边的信息，每条边记录其两个端点（对于有权图还包括权重）。
对于同样的例子，边列表表示为：
``` (A, B) (A, D) (B, C) (C, D) ```
如果包含权重：
``` (A, B, 3) (A, D, 7) (B, C, 2) (C, D, 5) ```
边列表的优点是极其简单，特别适合边的遍历操作。但查询效率最低，判断两个节点是否相连需要遍历整个列表。
三种表示方法的对比
| 表示方法 | 空间复杂度 | 查询边是否存在 | 遍历邻居节点 | 适用场景 | |---------|-----------|----------------|--------------|---------| | 邻接矩阵 | $O(n^2)$ | $O(1)$ | $O(n)$ | 密集图、需要频繁查询边 | | 邻接表 | $O(n + m)$ | $O(degree)$ | $O(degree)$ | 稀疏图、需要频繁遍历邻居 | | 边列表 | $O(m)$ | $O(m)$ | $O(m)$ | 需要遍历所有边 |
在实际应用中，选择哪种表示方法取决于具体的问题场景和数据特征。
生活中的图结构：一起来发现
其实，图结构远比我们想象的要普遍得多。让我们一起来“图”眼看世界，发现身边的图结构。
你的班级座位表
开学第一天，老师重新安排了班级座位。每个同学是一个节点，如果两个同学是同桌或者前后桌（取决于你如何定义“相邻”），就在他们之间画一条边。这就是一个简单的无向图。你可以分析：班级里有多少个“孤立的”同学（没有同桌或邻桌）？谁的“连接数”最多？
快递配送网络
仔细观察快递的配送路径。从你下单到收到商品，货物可能经过了这样的路线：仓库 → 分拣中心A → 分拣中心B → 配送站 → 你家门口的快递柜。每一个站点是一个节点，每一段运输路程是一条边。这条路线构成了一个有权图，其中边的权重可以是运输时间、距离或物流成本。
如果你对物流优化感兴趣，可以思考：为什么快递公司要设置多个分拣中心，而不是直接从仓库送到每个用户手中？这涉及到图论中一个著名的概念——图的连通性和中转枢纽的作用。
你的知识图谱
回想一下你学过的知识。以数学为例，加减乘除运算是基础节点，它们组合形成分数运算，分数运算又与小数、百分比相互关联。这个知识网络也是一种图结构！每个知识点是一个节点，“前置知识”“包含关系”“应用场景”等构成了边。
有趣的是，科学家们正在尝试用图结构来构建知识图谱（Knowledge Graph）。搜索引擎如Google就使用知识图谱来理解用户查询的语义，提供更精准的搜索结果。
游戏的关卡地图
许多电子游戏都采用关卡制的设计。回想一下你玩过的游戏，是不是有一个“关卡地图”界面？每个关卡是一个节点，关卡之间的解锁关系（需要先通关A才能解锁B）构成了有向边。这种结构帮助玩家理解游戏进度，也帮助游戏设计师规划玩家的体验流程。
图的度数：理解节点的连接数
在图论中，有一个非常基础但重要的概念——度数（Degree）。对于无向图，一个节点的度数就是与该节点相连的边的数量。对于有向图，节点的度数分为入度（In-degree，指向该节点的边的数量）和出度（Out-degree，从该节点指出的边的数量）。
度数的概念在许多实际问题中都有应用：
社交网络影响力分析：在微博上，拥有大量粉丝（高入度）的用户往往具有更大的影响力。而那些主动关注很多人（高出度）的用户，可能是活跃的信息传播者。
网络基础设施规划：在通信网络中，如果某个路由器（节点）的连接数（度数）特别大，一旦它发生故障，可能会影响大量其他节点的网络连接。这种“枢纽”节点需要特别保护或配备冗余。
流行病传播建模：在传染病的传播模型中，高度数的人（社交活跃、接触频繁）更容易成为超级传播者。理解度数分布有助于制定更有针对性的防控策略。
化学分子性质预测：在化学中，原子的度数与其化学性质密切相关。碳原子之所以能够形成如此多样的有机化合物，正是因为碳原子通常形成4个化学键（度数为4）。
数学上，有一个经典的握手定理（Handshaking Lemma）：在任何无向图中，所有节点的度数之和等于边数的两倍。这是因为每条边贡献两个端点的度数。
$$\sum_{v \in V} \deg(v) = 2|E|$$
这个定理有一个著名的推论：度数为奇数的节点一定是偶数个。
路径与连通性：图的“交通网络”
路径（Path）是图论中的另一个核心概念。在图中，路径是一系列相邻节点组成的序列，路径上相邻节点之间都有边相连。
简单路径与回路
如果一条路径上没有重复的节点（除了可能首尾相同），则称为简单路径（Simple Path）。如果路径的首尾节点相同，形成一个闭环，则称为环（Cycle）或回路。
```mermaid graph LR A["A"] --> B["B"] B --> C["C"] C --> D["D"] D --> A
E["E"] --> F["F"] F --> G["G"] G --> E ```
在上面的例子中，A → B → C → D → A 形成了一个包含4个节点的环，而E → F → G → E 形成了另一个环。
连通图与非连通图
如果从图中的任意节点出发，都存在一条路径能够到达图中的任何其他节点，那么这个图就是连通的（Connected）。否则，就是非连通的（Disconnected），其中能够相互到达的节点集合称为连通分量（Connected Component）。
现实世界中的许多网络都是“近似连通”的：虽然整体连通，但存在少数“孤岛”区域。例如：
- 互联网虽然全球连通，但某些特殊网络可能因为安全原因完全隔离
- 某些偏远地区可能只有公路连接，与主要交通网络相对独立
- 社交媒体上可能存在一些“潜水”用户，他们几乎没有互动
理解连通性对于网络设计至关重要。如果你的社交网络是连通的，意味着任何人通过“朋友的朋友”的链条，最终都能联系到世界上的任何人。实际上，社会学家做过著名的“小世界实验”，发现地球上任意两个人之间的平均距离（以认识链条计算）只有6左右，这就是著名的“六度分隔”理论。
最短路径问题
最短路径（Shortest Path）是图论中最经典的问题之一。给定一个图和两个节点，找出它们之间“代价最小”的路径。
最短路径的“代价”定义取决于具体问题：可能是距离（导航系统）、时间（通信延迟）、成本（物流费用）或跳数（网络中的中转次数）。
著名的最短路径算法包括：
- **Dijkstra算法**：适用于边权重为非负数的情况，是单源最短路径问题的经典解法
- **Bellman-Ford算法**：可以处理负权重边，但效率较低
- **Floyd-Warshall算法**：计算图中所有节点对之间的最短路径
这些算法是现代导航系统、路由协议、航班查询等应用的技术基础。
图在计算机科学中的地位
图结构在计算机科学中占据着举足轻重的地位，是算法与数据结构领域的核心主题之一。
历史沿革
图论与计算机科学的关系经历了几个重要的发展阶段：
前计算机时代（1736-1936年）：图论作为纯数学分支发展了近两百年。欧拉之后，数学家们继续研究图的性质，包括四色问题（能否只用四种颜色给任意地图染色，使得相邻区域颜色不同）、哈密顿回路（是否存在经过每个节点恰好一次的回路）等经典问题。
计算机诞生时代（1936-1970年）：随着计算机的出现，图算法开始快速发展。1946年，世界上第一台通用电子计算机ENIAC诞生。1956年， Dijkstra发表了其著名的最短路径算法。1962年，Tarjan等计算机科学家开始系统研究图的遍历算法。计算机科学家发现，许多现实世界的问题都可以建模为图问题。
互联网时代（1990-2010年）：万维网的诞生让图结构的重要性呈指数级增长。网页之间的链接构成了一个巨型有向图，搜索引擎需要分析这个图来排名网页。社交网络的兴起进一步