图论算法导论
欢迎！今天我们将深入探讨计算机科学中最强大的工具之一：图（Graphs）。别被它的名字误导了——这可不是数学课里看到的条形图或折线图。在计算机科学中，图是一种用来描绘事物之间关系的映射方式。
想想 Instagram 这类社交网络，或是 Google Maps 这类地图应用程序。这些 App 是如何知道谁是你的“建议好友”，或是如何找到前往咖啡店的最快路径？答案就在于图算法（Graph Algorithms）。在本章中，我们将学习如何表示这些连接，以及如何有效地“遍历”这些路径。
1. 什么是图？
简单来说，图就是由“点”与连接这些点的“线”所组成的集合。
关键术语：
- 顶点（Vertex 或 Node）： 单一个点或对象（例如一个城市或一个人）。复数为 Vertices。
- 边（Edge）： 连接两个顶点之间的连线（例如城市之间的道路或人与人之间的友谊）。
图的类型
并非所有的连接都是一样的！我们根据边的运作方式对图进行分类：
- 无向图（Undirected Graph）： 连接是双向的。如果甲是乙的朋友，那么乙也是甲的朋友。可以想象成一条双向道。
- 有向图（Directed Graph / Digraph）： 连接有特定的方向。例如在 X（前身为 Twitter）上，你可能会关注某位明星，但他们不一定会关注你。这就像是一条单行道。
- 加权图（Weighted Graph）： 边上带有“成本”或“数值”。例如，连接两个城市的边可能有一个权重 50，代表 50 公里。
- 无权图（Unweighted Graph）： 所有边都是相等的。我们只关心连接是否存在，而不考虑距离或成本。
快速回顾： 将图想象成一张地图。城市就是顶点，连接它们的道路就是边。如果道路是单行道，它就是有向图；如果道路标示了距离，它就是加权图。
2. 在代码中表示图
计算机无法“看见”图的绘图，所以我们必须以计算机理解的方式来存储数据。主要有两种方法：
A. 邻接矩阵（Adjacency Matrix）
这是一个二维数组（网格），行与列代表顶点。如果顶点 A 与顶点 B 之间有连接，我们就在对应的网格中填入 1，否则填入 0。
矩阵示例：
如果我们有 3 个节点（0, 1, 2），且 0 与 1 之间有连接：
\( \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \)
- 优点： 检查两个特定节点是否连接时速度非常快。
- 缺点： 如果节点多但连接少（全是零），会浪费大量内存。
B. 邻接列表（Adjacency List）
这就像一本“通讯录”。每个顶点都保存着一个列表，记录了所有与它直接相连的其他顶点。
列表示例：
节点 0: [1, 2]
节点 1: [0]
节点 2: [0]
- 优点： 节省空间！我们只存储实际存在的连接。
- 缺点： 检查特定连接是否存在较慢，因为你必须在列表中进行搜索。
内存小撇步： 当图是“稠密”的（连接很多）时，使用矩阵；当图是“稀疏”的（大部分空间是空的）时，使用列表。
3. 图遍历：探索连接
遍历是一个专业术语，意指“访问图中的每一个节点”。主要有两种方法，它们的操作方式就像探索一栋建筑或一个迷宫一样。
A. 广度优先搜索（Breadth-First Search, BFS）
想象你把一颗小石子丢进池塘里。涟漪会一圈圈地向外扩散，先触及最近的点，然后是下一个圈，依此类推。这就是 BFS！
运作原理：
- 从一个节点开始，并将其标记为“已访问”。
- 首先访问它所有的直接相邻节点。
- 然后访问这些邻居的邻居。
- 使用队列（Queue，先进先出）来追踪下一个要访问的节点。
适用情境： 在无权图中寻找最短路径。
B. 深度优先搜索（Depth-First Search, DFS）
想象你在探索一个迷宫。你选定一条路并尽可能地深入，直到碰到死胡同为止。然后你回头并尝试下一个可用的转弯。这就是 DFS！
运作原理：
- 从一个节点开始，并将其标记为“已访问”。
- 顺着一条路径尽可能地走到底。
- 当碰到死胡同（或已访问过的节点）时，回溯到上一个还有未访问邻居的节点。
- 使用栈（Stack，后进先出）或递归（Recursion）来追踪路径。
适用情境： 检查两个节点之间是否存在路径，或是解决需要尝试所有可能性的谜题。
别担心，如果觉得很复杂！ 只要记住：BFS 用于 Breadth（广度，向外扩散），而 DFS 用于 Depth（深度，往深处走）。
4. 要避免的常见陷阱
- 无限循环： 如果你不追踪“已访问”的节点，你的算法可能会永远绕圈子。务必将访问过的节点标记下来！
- 错误的数据结构： 记得 BFS 使用队列，而 DFS 使用栈。搞混它们会改变算法探索图的方式。
- 有向图 vs 无向图： 在有向图中，能从 A 到 B 不代表能从 B 到 A。一定要看清楚箭头方向！
重点总结
顶点是点，边是线。图可以是有向的（单向）或无向的（双向），也可以是加权的（带有成本）或无权的（无成本）。要存储它们，请使用邻接矩阵（适用于大量连接）或邻接列表（节省空间）。要搜索它们，请使用 BFS（广度/队列）来找最短路径，或使用 DFS（深度/栈）来探索所有路径。
你知道吗？ “六度分隔理论”（世界上任何人之间通过六个或更少的中间人就能建立联系）其实就是一个可以用广度优先搜索来解决的图论问题！