欢迎来到图论（Graphs）的世界！
在本章中，我们将探讨一种最强大且灵活的数据组织方式：图（Graphs）。别担心，这可不是你在数学课上看到的条形图或折线图！在计算机科学中，图是用来表示不同事物之间如何相互连接的一种方式。
试想一下 Facebook 的好友关系、Google 地图的导航，甚至是互联网本身的连接方式——这些都是现实生活中图的应用例子。读完这些笔记后，你将了解计算机是如何“看待”这些连接，以及如何在其中进行搜索和导航。
1. 什么是图（Graph）？
简单来说，图就是一组“点”和连接这些点的“线”。在计算机科学中，我们使用特定的术语来称呼它们：
- 顶点（Vertices 或 Nodes）： 这些就是代表对象（如城市、人物或网页）的“点”。单数形式称为顶点（Vertex）。
- 边（Edges 或 Arcs）： 这些就是连接顶点的“线”。它们代表了顶点之间的关系（例如城市之间的道路，或人与人之间的友谊）。
现实生活中的类比
想象一张地铁系统地图。每个车站就是一个顶点，连接它们的路轨就是边。图能帮助我们理解如何从车站 A 到达车站 B。
关键重点：
图（Graph）是一种由顶点（Vertices）经由边（Edges）连接而成的数学结构。
2. 图的类型
并非所有的连接都是一样的。根据我们试图建立的模型，我们会使用不同类型的图：
无向图（Undirected Graphs）
在无向图中，边是没有方向的。如果 A 人与 B 人之间有连接，那么这种关系是双向的。例子：Facebook 的好友关系。如果我是你的好友，你自然也是我的好友。
有向图（Directed Graphs / Digraphs）
在有向图中，边带有箭头，表示特定的方向。例子：Twitter 或 Instagram 的关注关系。你关注某位名人，并不代表他们也会关注你！
加权图（Weighted Graphs）
有时候，连接会带有“代价”或“数值”，这称为权重（Weight）。例子：在地图上，两个城市之间的边可能有 50 的权重，代表距离 50 英里。
快速复习：
- 无向图： 双向道。
- 有向图： 单行道。
- 加权图： 需要付过路费或具有特定距离的道路。
3. 计算机如何存储图
计算机无法“看到”图的绘图，所以我们必须以计算机能理解的方式存储数据。主要有两种方法：
方法 A：邻接矩阵（Adjacency Matrix）
这是一个二维表格（或网格），行与列代表顶点。如果有边连接，我们就在对应单元格填入 1，若没有则填入 0。如果是加权图，我们则存储权重（Weight），而不是 1。
优点： 检查两个节点之间是否存在特定连接非常快速。
缺点： 如果节点很多但连接很少（这种图称为稀疏图），会浪费大量内存。
方法 B：邻接表（Adjacency List）
这就像一本通讯录。每个顶点都有一个列表，记录了它直接连接的所有其他顶点。
例子：节点 A: [B, C], 节点 B: [A], 节点 C: [A]。
优点： 对于稀疏图来说，节省内存空间。
缺点： 检查两个特定节点是否相连可能会较慢，因为你必须在列表中进行搜索。
常见错误提醒：
学生常忘记在无向图中，A 与 B 之间的边必须在矩阵中记录两次（在 A 行 B 列，以及 B 行 A 列各记录一次），因为路径是双向的！
关键重点：
对于“稠密图”（大量连接）使用邻接矩阵，对于“稀疏图”（少量连接）使用邻接表。
4. 图的遍历（Traversing a Graph）
“遍历”简单来说就是依照特定顺序访问图中的节点。你需要掌握两种主要方法：
深度优先搜索（Depth-First Search, DFS）
核心概念： 沿着一条路径尽可能深入，直到无法继续，然后回溯并尝试另一条路径。想象探索迷宫时，沿着左边墙壁一直走，直到遇到死胡同为止。
- 记忆技巧： DFS 使用栈（Stack）（后进先出，LIFO）。
- 类比： 就像一个人在漆黑的洞穴中探索，顺着一条隧道走到尽头，再返回上一个交叉路口。
广度优先搜索（Breadth-First Search, BFS）
核心概念： 先查看所有直接相邻的节点，然后再查看它们的邻居。它是以“层级”向外扩展的。
- 记忆技巧： BFS 使用队列（Queue）（先进先出，FIFO）。想象商店里的“排队”，先来先服务。
- 类比： 就像水面上的涟漪，从丢入石子的中心点向外扩散。
BFS 的步骤：
1. 选择一个起始节点并将其加入队列（Queue）。
2. 将其标记为“已访问”。
3. 当队列不为空时：
a. 移除队列最前端的节点。
b. 查看该节点所有未访问的邻居。
c. 将这些邻居加入队列并标记为“已访问”。
你知道吗？
Google 地图经常使用这些算法的变体来计算你家与你最爱披萨店之间的最短路径！
5. 总结清单
如果内容看起来很多，别担心！这里有一份考试前必备的“速查表”：
- 图的组成： 顶点由边连接。
- 方向： 无向（双向）与 有向（单向）。
- 权重： 边上的数值，代表成本或距离。
- 存储： 矩阵（二维数组）与 列表（邻居列表）。
- DFS： 向深处探索；使用栈（Stack）。
- BFS： 向宽处（逐层）探索；使用队列（Queue）。
加油：图论是许多进阶课题的基础。一旦你掌握了矩阵与列表、栈与队列的区别，你就已经攻克最难的部分了！