Step 6 06. 图论入门

<!-- Title: 06. 图论：连接万物的网络 --> <!-- ID: 245 --> <!-- Series: 程序员的数学修养 (ID: 16) --> <!-- Author: 潘卫 --> # 图论：连接万物的网络 ## 1. 世界是一张图 图 (Graph) 是描述“关系”的最强数学模型。 $G = (V, E)$，其中 $V$ 是节点（Vertex），$E$ 是边（Edge）。 * **互联网**：网页是节点，超链接是边（PageRank 算法的基础）。 * **社交网络**：人是节点，关注/好友关系是边。 * **城市交通**：路口是节点，道路是边。 * **代码依赖**：库是节点，引用是边。 ## 2. 深度优先 (DFS) 与广度优先 (BFS) 这是遍历图的两种基本姿势，也是面试必考题。 * **DFS (不撞南墙不回头)**: 一条路走到黑，直到无路可走再回溯。 * *应用*：走迷宫、生成全排列、检测环。 * **BFS (层层推进)**: 像水波纹一样向外扩散。 * *应用*：**寻找最短路径**（无权图）、社交网络里的“三度人脉”搜索、垃圾回收（GC）的可达性分析。 ## 3. 最短路径算法：导航的秘密 打开高德/谷歌地图，输入起点终点，它怎么知道哪条路最近？ * **Dijkstra 算法**: 贪心策略。适用于加权图（路有长短/拥堵程度）。 * **A* (A-Star) 算法**: Dijkstra 的改进版，加入了“启发式函数”（预估距离）。它是游戏寻路（如《魔兽争霸》单位移动）的标准算法。 ## 4. 拓扑排序 (Topological Sort)：解决依赖地狱 **场景**： 你要编译一个大型项目。 A 依赖 B，B 依赖 C，C 依赖 D。 你也可能遇到 A 依赖 B，B 依赖 A（循环依赖/死锁）。 如何确定编译顺序？ 这就需要**拓扑排序**。 它只能应用于 **DAG（有向无环图）**。 算法逻辑： 1. 找到所有“入度”为 0 的节点（不依赖别人的模块）。 2. 执行它们，并从图中移除。 3. 重复步骤 1，直到所有节点被执行。 4. 如果最后还有节点剩下来，说明图中有**环**（循环依赖），报错。 Webpack、Maven、Systemd 启动服务，底层都在跑这个算法。 ## 5. 树 (Tree) 是特殊的图 树是一种**无环连通图**。 它是图论中最简单、最常用的结构。 * **DOM 树**：HTML 结构。 * **文件系统**：目录结构。 * **AST (抽象语法树)**：编译器如何理解你的代码。 理解了图论，你就会发现，从文件管理到AI神经网络，计算机科学的半壁江山都是建立在图的基础之上的。