Graphs

欢迎来到图论（Graphs）的世界！

在本章中，我们将探索图（Graphs）。虽然你可能会想到数学课里的条形图或折线图，但在计算机科学中，“图”是用来表示事物之间如何连接的一种方式。

试想一下 Facebook：你是其中的一个“点”，而友谊就是连接你与他人的“线”。或者想想 Google 地图：城市是点，道路是线。图在我们的生活中无处不在！如果一开始觉得这概念有点抽象也别担心，我们会把它拆解成小部分来学习。

1. 基础概念：什么是图？

图（Graph）是一种用于表示对象对之间复杂关系的数学结构。它由两个主要部分组成：

• 顶点（Vertex 或 Node）：图中的“对象”或“点”（例如一个人或一个城市）。
• 边（Edge 或 Arc）：连接顶点之间的“线”（例如一段友谊或一条道路）。

有向图（Directed）与无向图（Undirected）

想象节点 A 和 B 之间存在一种关系。

无向图：边没有方向。如果 A 和 B 之间有一条边，你可以双向通行。
类比：双向行车道或 Facebook 的好友关系（你们互为好友）。

有向图：边有特定的方向，通常用箭头表示。你只能沿着箭头的方向移动。
类比：单行道或 Twitter 的“关注”（你可能会关注某位名人，但对方不一定会关注你！）。

加权图（Weighted Graphs）

有时候，节点之间的连接会有“成本”或“数值”。这被称为加权图。“权重（Weight）”可以代表距离、时间，甚至两个城市之间航班的票价。

快速复习：
• 顶点（Vertex）：一个点。
• 边（Edge）：一种连接。
• 加权（Weighted）：连接带有数值（例如：5 英里）。
• 有向（Directed）：连接是单向的。

重点总结：图只是节点及其之间连接的集合。它们能帮助我们建模所有事物，从互联网到化学分子！

2. 电脑如何存储图

由于电脑无法直接“看见”图的绘图，我们需要一种方法将其转化为数据。主要有两种方法：

方法 A：邻接矩阵（Adjacency Matrix）

这是一个二维数组（网格）。行和列都代表顶点。如果两个节点之间有连接，我们在对应位置填入 1；否则填入 0。对于加权图，我们则在网格中存储权重而非 1。

包含 3 个节点（A, B, C）的图的矩阵示例：
\( \begin{matrix} & A & B & C \\ A & 0 & 1 & 0 \\ B & 1 & 0 & 1 \\ C & 0 & 1 & 0 \end{matrix} \)

方法 B：邻接表（Adjacency List）

这就像一本通讯录。对于每个节点，我们保留一个列表，列出所有与它直接相连的其他节点。
示例：
A: [B]
B: [A, C]
C: [B]

哪种方法比较好？

• 邻接矩阵：适合“稠密图（Dense Graphs）”（几乎所有节点都相连的情况）。它检查“A 是否连接到 B？”非常快，但如果连接稀疏，存储大量的 0 会浪费内存。
• 邻接表：适合“稀疏图（Sparse Graphs）”（大部分节点没有直接连接的情况）。它节省内存，因为只会存储实际存在的连接。

你知道吗？大多数现实世界中的图，例如万维网（World Wide Web），都是“稀疏”的。绝大多数网站只链接到所有网站中极小的一部分！

重点总结：连接多时用矩阵（速度快），连接少时用表（节省空间）。

3. 图的遍历（Graph Traversal）：探索连接

遍历的意思是“访问图中的每一个节点”。根据你的目标，有两种主要方法：

深度优先搜索（Depth-First Search, DFS）

在 DFS 中，你会尽可能沿着一条路径走到底，然后再回溯（back-tracking）去寻找新的路径。
记忆小撇步：把“深度（Depth）”想象成“深（Deep）”。你潜入图的深处。
• 类比：走迷宫时，沿着一条路径一直走，直到遇到死胡同。
• 数据结构：使用栈（Stack）（后进先出，LIFO）。
• 常见用途：走迷宫或检查两点之间是否存在路径。

广度优先搜索（Breadth-First Search, BFS）

在 BFS 中，你会先访问起始节点的所有直接相邻节点，然后再访问它们的所有邻居，以此类推。
记忆小撇步：把“广度（Breadth）”想象成“宽（Wide）”。你在图上向四面八方扩展。
• 类比：往池塘丢一颗石头，看着涟漪一圈一圈向外扩散。
• 数据结构：使用队列（Queue）（先进先出，FIFO）。
• 常见用途：在无权图（无权重图）中寻找最短路径（例如：你在 LinkedIn 上与陌生人之间最少经过几个“跳跃”）。

快速复习：
• DFS：使用栈，深入探索，适合走迷宫。
• BFS：使用队列，广泛扩散，寻找最短路径（无权图）。

4. Dijkstra 最短路径算法

虽然 BFS 以“跳跃次数”来寻找最短路径，但 Dijkstra 算法是在边有权重（例如英里或分钟）时，寻找最短路径的方法。

运作原理（核心概念）：

1. 从起始节点开始，将其距离设为 0，将其他所有节点的距离设为“无穷大”。
2. 查看当前节点的所有未访问邻居。
3. 计算到每个邻居的距离：（当前节点的距离 + 边的权重）。
4. 如果这个新距离比该邻居目前存储的距离更小，就更新它！
5. 将当前节点标记为“已访问”。你之后再也不会访问它了。
6. 移动到距离最小的未访问节点，重复上述步骤，直到所有节点都被访问。

常见错误：学生常会忘记在发现更短的路径时更新距离。务必检查新计算的路径是否比旧的“更便宜”！

现实世界应用：这正是你的卫星导航或 Google 地图计算回家最快路线的方法。它将每个路口视为节点，将每条道路视为加权边。

重点总结：Dijkstra 是在加权图中寻找最短路线的“黄金标准”。它是一个最优化（Optimisation）算法。

5. 总结检查清单

在完成本章之前，确保你可以：
• 定义顶点（Vertex）和边（Edge）。
• 解释有向图与无向图的区别。
• 为简单的图绘制邻接矩阵和邻接表。
• 描述 DFS 和 BFS 如何探索图，以及它们分别使用什么数据结构。
• 解释 Dijkstra 算法的目的，并将其识别为加权图中的最短路径工具。

继续练习手绘这些图表——一旦你能画出矩阵和表，算法的逻辑就会变得非常容易可视化！