本书归纳了计算机的经典算法题，并按照由浅入深、循序渐进的顺序讲解。本书对图论等算法中的重点内容进行了详细的讲解，重点讲解并查集、最小生成树算法（包括Prim和Kruskal算法）和最短路径算法（包括 Dijkstra、Bellman-Ford、Floyd和A*算法），既注重理论推导，也强调代码实现与调试技巧。每一章均有清晰的思路分析、代码模板和常见错误总结，兼顾基础知识巩固与应用能力提升。

哈尔滨工业大学计算机科学与技术专业硕士，先后在腾讯和百度从事技术研发，对数据结构与算法有深刻理解，擅长将一个个算法串联在一起并用通俗易懂的方式讲解出来。

目录


第1章　图论理论基础 1
1.1　图论的第一印象 2
1.1.1　连通性 4
1.1.2　图的构造 7
1.1.3　图的遍历方式 11
1.1.4　小结 12
1.2　为什么使用ACM输入/输出模式 12
第2章　深度优先搜索与广度优先搜索 13
2.1　深度优先搜索的理论基础 14
2.1.1　深度优先搜索与广度优先搜索的区别 14
2.1.2　深度优先搜索的搜索过程 14
2.1.3　代码框架 17
2.1.4　深度优先搜索三部曲 18
2.2　可达路径 20
2.2.1　解题思路 23
2.2.2　图的存储 23
2.2.3　求解过程 24
2.2.4　输出结果 26
2.2.5　实现代码 27
2.2.6　小结 30
2.3　广度优先搜索的理论基础 30
2.3.1　广度优先搜索的使用场景 30
2.3.2　广度优先搜索的搜索过程 30
2.3.3　代码框架 32
2.4　岛屿问题（一） 34
2.4.1　解题思路 35
2.4.2　深度优先搜索的实现代码 36
2.5　岛屿问题（二） 39
2.6　岛屿问题（三） 42
2.6.1　解题思路 44
2.6.2　深度优先搜索的实现代码 44
2.6.3　广度优先搜索的实现代码 47
2.7　岛屿问题（四） 49
2.7.1　解题思路 50
2.7.2　实现代码 52
2.8　岛屿问题（五） 55
2.8.1　解题思路 56
2.8.2　实现代码 58
2.9　岛屿问题（六） 59
2.9.1　解题思路 61
2.9.2　实现代码 61
2.9.3　优化思路 64
2.10　岛屿问题（七） 68
2.10.1　解题思路 69
2.10.2　优化思路 70
2.11　岛屿问题（八） 76
2.11.1　解题思路 78
2.11.2　具体解法 78
2.12　字符串迁移 81
2.12.1　解题思路 82
2.12.2　实现代码 84
2.13　有向图的完全连通 86
2.13.1　解题思路 87
2.13.2　实现代码 90
2.14　拓扑排序 93
2.14.1　拓扑排序的应用 95
2.14.2　拓扑排序的解题思路 95
2.14.3　模拟拓扑排序的过程 97
2.14.4　判断图中是否有环 99
2.14.5　实现代码 100
第3章　并查集 105
3.1　并查集理论基础 106
3.1.1　背景 106
3.1.2　基本原理 106
3.1.3　路径压缩 108
3.1.4　代码模板 110
3.1.5　常见误区 111
3.1.6　模拟过程 114
3.1.7　拓展路径压缩的思路 116
3.1.8　复杂度分析 119
3.2　并查集寻找路径 120
3.2.1　解题思路 121
3.2.2　实现代码 121
3.3　并查集寻找无向边 123
3.3.1　解题思路 125
3.3.2　实现代码 126
3.3.3　常见疑问 127
3.4　并查集寻找有向边 128
3.4.1　解题思路 130
3.4.2　实现代码 131
第４章　最小生成树 136
4.1　Prim算法 137
4.1.1　解题思路 138
4.1.2　模拟过程 139
4.1.3　实现代码 147
4.1.4　拓展思路 149
4.1.5　小结 152
4.2　Kruskal算法 153
4.2.1　解题思路 153
4.2.2　实现代码 156
4.2.3　题目拓展（一） 158
4.2.4　题目拓展（二） 160
第5章　最短路径算法 162
5.1　Dijkstra算法（朴素版） 163
5.1.1　解题思路 165
5.1.2　Dijkstra算法的工作过程 165
5.1.3　Dijkstra算法与Prim算法的区别 183
5.2　Dijkstra算法（堆优化版） 184
5.2.1　解题思路 184
5.2.2　实现代码 190
5.2.3　拓展思路 194
5.3　Bellman-Ford算法 196
5.3.1　解题思路 198
5.3.2　什么是松弛 199
5.3.3　模拟过程 200
5.3.4　实现代码 205
5.3.5　拓展思路 206
5.4　Bellman-Ford算法之队列优化 208
5.4.1　背景 208
5.4.2　模拟过程 209
5.4.3　实现代码 214
5.4.4　效率分析 216
5.4.5　拓展思路 218
5.5　Bellman-Ford算法之判断负权回路 219
5.5.1　解题思路 220
5.5.2　实现代码 222
5.5.3　拓展思路 223
5.6　Bellman-Ford算法之单源有限最短路径 228
5.6.1　解题思路 230
5.6.2　拓展一（边的顺序对结果的影响） 237
5.6.3　拓展二（本题本质） 240
5.6.4　拓展三（SPFA算法） 240
5.6.5　拓展四（能否使用Dijkstra算法） 244
5.7　Floyd算法 247
5.7.1　解题思路 249
5.7.2　实现代码 256
5.7.3　空间优化 257
5.7.4　小结 259
5.8　A*算法 259
5.8.1　解题思路 261
5.8.2　A*算法的解题过程 263
5.8.3　复杂度分析 267
5.8.4　拓展思路 267
5.8.5　A*算法的缺点 268