Graphs

✨ 高级数据结构：图（Graphs）—— 学习笔记

欢迎来到激动人心的“图”世界！大家已经掌握了数组、链表、栈和队列等线性结构，现在我们要开始学习能够处理更复杂、非线性关系的结构了。

图是计算机科学中最强大的概念之一，无论是社交网络还是导航系统，它都是构建各类现实世界问题的核心。如果起初觉得有些难理解也不必担心——我们将通过这一节的学习，把相关术语和方法拆解得明明白白！

1. 定义图（Graph）数据结构

图（Graph）是一种用于表示对象之间复杂关系或连接的数据结构。

你可以把图想象成一张城市交通系统的地图。

1.1 核心术语

• 顶点（Vertex/Node）： 图中的一个独立实体或点。
  （类比：地图上的城市或公交车站。）
• 边（Edge/Arc）： 连接两个顶点的纽带或关系。
  （类比：连接两个城市的道路或公交线路。）
• 图（Graph）： 所有顶点和边的集合。

1.2 图的类型

根据边的属性，图可以分为几种不同的类别：

a) 加权图（Weighted） vs. 非加权图（Unweighted）

• 加权图： 每条边都有一个关联的数值，称为权值（Weight）（通常代表成本）。
  （例如：如果顶点是城市，权值可能代表它们之间的距离、旅行时间或机票价格。）
• 非加权图： 所有边被视为相等（或者权值均为1）。这类图的目标通常仅仅是找到路径中最少的步数。

b) 有向图（Directed） vs. 无向图（Undirected）

• 无向图： 边仅表示连接关系，不区分移动方向。如果顶点 A 与顶点 B 相连，那么你可以从 A 走到 B，也可以从 B 走到 A。
  （例如：允许双向通行的乡村公路。）
• 有向图（Digraph）： 边带有箭头或方向，意味着移动只能单向进行。如果存在边 A → B，你只能从 A 到 B，而不能从 B 到 A（除非额外存在一条 B → A 的边）。
  （例如：单行道或社交媒体上的关注关系。）

重点总结： 图用于建模关系。顶点是对象，边是连接。权值增加了成本，方向则增加了流向控制。

2. 在内存中表示图

要在计算机中存储图结构，我们通常采用两种主要方法：邻接矩阵（Adjacency Matrix）或邻接表（Adjacency List）。

2.1 邻接矩阵

邻接矩阵使用一个二维数组来存储顶点之间的连接关系。

• 如果图有 \(N\) 个顶点，矩阵的大小就是 \(N \times N\)。
• 位置 (i, j) 处的元素表示从顶点 \(i\) 到顶点 \(j\) 的边。
• 对于非加权图： (i, j) 通常为 1（表示相连）或 0（表示不相连）。
• 对于加权图： (i, j) 存储边的权值（成本）。如果没有连接，我们通常填 0 或一个特殊的无穷大值。

小知识： 在无向图中，邻接矩阵始终是对称的（(i, j) 的值等于 (j, i) 的值）。

2.2 邻接表

邻接表使用一个数组（或列表），其中每个索引对应一个顶点。每个索引处存储一个其相邻顶点的列表。

例子： 如果顶点 A 与 B 和 C 相连，那么主列表中 A 的位置将包含一个列表 [B, C]。对于加权图，这个列表会存储成对的数据：[(B, 5), (C, 10)]，其中第二个数字即为权值。

2.3 矩阵 vs. 列表的对比（考试重点！）

选择哪种表示方法，主要取决于图的属性以及最常执行的操作。

邻接矩阵的优势（O(1) 查找）

• 检测边的存在： 检查两个特定顶点之间是否存在边非常快（只需检查数组中的一个位置）。这在实际中非常常用。
• 添加/删除边： 操作简单迅速——只需更改一个单元格的值即可。
• 适用场景： 当图是稠密图（Dense）时（即相对于顶点的数量，边非常多）。

邻接表的优势（空间效率）

• 空间效率： 它仅存储实际存在的边。如果图是稀疏图（Sparse）（即边很少），邻接表比始终占用 \(N^2\) 空间的矩阵节省大量内存。
• 适用场景： 当图是稀疏图时。
• 查找邻居： 查找特定顶点的所有邻居非常高效。

3. 图的遍历算法

遍历是指系统地访问图中的每一个顶点。我们需要一些方法来确保自己不会迷路，也不会重复访问同一个顶点。

3.1 广度优先搜索（BFS）

BFS 就像往池塘里丢一颗石子——它会先探索当前深度（或距离）的所有顶点，然后再移动到下一层。

• 策略： 使用一个队列（Queue，先进先出 FIFO）来管理待访问顶点的顺序。
• 流程：
  1. 从源顶点（A）开始，将其加入队列并标记为已访问。
  2. 只要队列不为空：
  3. 从队列中取出（Dequeue）当前顶点（V）。
  4. 找到 V 所有未被访问的邻居，将它们标记为已访问并入队（Enqueue）。
• 典型应用： 在非加权图中查找最短路径（因为它逐层查找，一旦首次发现目标，该路径保证是边数最少的）。

3.2 深度优先搜索（DFS）

DFS 就像在迷宫中沿着一条路走到底，直到遇到死胡同，然后再回溯去尝试其他的路。

• 策略： 使用一个栈（Stack，后进先出 LIFO），或者更常用的方法——递归，来管理这一过程。
• 流程：
  1. 从源顶点（A）开始，将 A 标记为已访问。
  2. 探索 A 的一个邻居（B）。
  3. 对 B 递归地执行 DFS。
  4. 如果 B 走到死胡同，回溯到 A 并尝试 A 的下一个未访问邻居。
• 典型应用： 走迷宫或检查连通性（是否图的所有部分都是可达的）。

注意难点： BFS 和 DFS 都需要一种机制（如布尔数组）来跟踪哪些节点已经被访问过。这可以防止在包含环（路径返回自身）的图中陷入无限循环。

4. 最短路径算法（Dijkstra 算法）

如果图是加权图怎么办？此时，仅仅计算边的数量是不够的；我们需要最小化总权值（成本）。这就是 Dijkstra 算法发挥作用的地方。

4.1 Dijkstra 最短路径算法

Dijkstra 算法用于查找从单一起始顶点到加权图中所有其他顶点的最短路径（前提是权值为非负数）。

• 目的： 计算从起始节点到每个其他节点所需的最小总权值（成本）。
• 应用： 广泛应用于网络路由（如 GPS 导航和互联网流量路由），以计算最便宜或最快的路径。

给学生的重要提示（大纲 3.11.1）：
你必须能够使用一组数据追踪（Trace） Dijkstra 最短路径算法的执行过程。
除非考试题目中明确给出了算法步骤，否则你不需要背诵具体步骤，也不需要编写实现它的程序代码。请重点理解“累积最小成本”这一核心理念。

重点总结： BFS 用于在非加权图中查找最短路径（边数最少）；Dijkstra 用于在加权图中查找最短路径（成本最低）。