电子工业出版社-网上书店

本书归纳了计算机的经典算法题，并按照由浅入深、循序渐进的顺序讲解。本书对图论等算法中的重点内容进行了详细的讲解，重点讲解并查集、最小生成树算法（包括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

前言


《代码随想录：跟着Carl学算法》于2021年12月出版，凭借其题目的合理编排与高质量的题解，迅速在业内赢得了良好口碑。
在《代码随想录：跟着Carl学算法》出版后，我便开始规划图论部分的编写工作。
为什么要写本书
图论既是数据结构与算法极为重要的组成部分，也是算法竞赛和求职面试中常考的知识点。
图论应用广泛，项目开发中也常常涉及相关技术。例如：通信网络（拓扑排序、最短路径算法）、社交网络（深度优先搜索、广度优先搜索）、路径优化（最短路径算法）、任务调度（拓扑排序）、生物信息学（以基因为节点，以基因关系为边）、游戏开发（A*算法等）。
为保质保量地编写本书，我详细查阅了市面上的大量相关资料。在反复确认思路正确性的过程中，不禁感慨许多算法图书在图论部分存在“缺斤少两”的现象。
以最短路径算法为例，一些经典算法图书仅介绍了Dijkstra算法（堆优化版）、SPFA算法（基于队列的Bellman-Ford算法）和拓扑排序，却未涵盖Dijkstra算法（朴素版）、Bellman-Ford算法（朴素版）、Bellman-Ford算法之单源有限最短路径、Floyd算法、A*算法，以及各最短路径算法的优劣比较。
其他算法图书对图论的诸多知识点也往往一笔带过。
在本书中，仅最短路径算法方面，我就详细讲解了以下内容：
?Dijkstra算法（朴素版）。
?Dijkstra算法（堆优化版）。
?Bellman-Ford算法。
?Bellman-Ford算法之队列优化（又称SPFA算法）。
?用Bellman-Ford算法判断负权回路。
?Bellman-Ford算法之单源有限最短路径。
?Floyd算法。
?A*算法。
为出版本书所做的准备
为了延续《代码随想录：跟着Carl学算法》的口碑，我在本书的编写过程中付出了诸多努力。
（1）夯实基础至关重要。若不能巩固和维护已有内容，急于更新图论部分的内容，则会“基础不牢，地动山摇”。
因此2022年，我决定在B站（ID：代码随想录）上更新《代码随想录：跟着Carl学算法》的讲解视频，花费大半年完成了140期算法视频，免费供读者学习。
这也使《代码随想录：跟着Carl学算法》成为作者亲自录制并提供免费视频讲解的技术图书。
同时，《代码随想录：跟着Carl学算法》配有专属网站“代码随想录”（programmercarl，com域名），同样免费向读者开放。
我的初衷是，通过书籍、网站和视频三个维度，全面助力读者学习算法。
夯实基础后，我于2022年下半年开始图论部分的写作。
图论是我在算法创作过程中绘图最多、工程量最大的主题。在写作过程中，我未回避任何“雷区”，力求为读者扫清障碍。
何谓“雷区”？
许多知识点在现有资料中或被略过，或难以讲清，需要花费大量时间才能阐释清楚。有些知识虽然自己理解后觉得简单，但要写成文字并向他人讲解却十分困难。
这些“雷区”往往是教程或视频中作者避而不谈的部分。
例如：
深度优先搜索为何有两种写法？
同样执行广度优先搜索，为何某种写法会超时？
为什么Prim算法和Dijkstra算法很像，相同点在哪儿，不同点在哪儿？
如果图中的边的权值为负数，那么为什么不能使用Dijkstra算法求解，Dijkstra算法的盲区在哪儿？
为什么Bellman-Ford算法需要松弛n-1次，多一次不行，少一次不行？
输入图的数据中，边的顺序对Bellman-Ford算法有什么影响？
负权回路对最短路径求解有何影响？
SPFA算法（队列优化版Bellman-Ford算法） 是否可以判断负权回路？
Bellman-Ford算法可以求单源有限最短路，那么使用SPFA算法是否也可以求解？使用Dijkstra算法是否可以求解？
实现Floyd算法的代码中有三层for循环，为什么最外面那层for循环的位置一定要固定？
这些问题都不是算法的主要核心逻辑，但处处都能体现图论算法的细节，也能考察读者对图论算法的理解深度。
读者在阅读《代码随想录2：图论》时，可以感受到我对细节的把控程度。
2023年下半年，图论部分正式更新完毕，首发于“代码随想录”网站，获得读者的一致好评。
这使我坚信，书中的图论内容确实稀缺，并能切实帮助读者。
此时本可安排出版，但我并未急于推出，而是希望继续精细打磨，以对得起“代码随想录”的口碑。
为了延续“代码随想录”这个IP的风格，我继续在B站上更新图论讲解视频。在录制过程中，我发现许多可优化之处，于是边录制视频边优化文字内容。
录制视频耗时费力，需要反复审核文字、优化内容、试讲并调整，最后录制、剪辑和发布。录制每期视频都需要花费数日才能完成，虽然艰难，但我坚持了下来。
当时发现读者有记录学习笔记的需求，于是创办了学习网站“卡码笔记”（notes.kamacoder，com域名），最初用于辅助读者学习“代码随想录”网站上的内容，现已逐步扩展至计算机编程学习的各个领域。
2025年8月，图论部分的所有讲解视频均已更新完毕并发布至B站。
因为对图论内容做了进一步优化，达到了出版的质量要求，所以才有了读者手中的《代码随想录2：图论》。
本书配套资源
本书采用C++语言进行讲解。使用其他编程语言的读者可访问“代码随想录”网站，查看Java、Python、Go、JavaScript等多语言版本。
代码随想录网站：programmercarl（com域名）。
代码随想录国际站：keetcoder（com域名），本站内容为英文版，方便海外读者学习。
卡码网：kamacoder（com域名），对于本书中的所有算法题目，均可在该网站提交代码验证。
卡码笔记：notes.kamacoder（com域名），读者可在此记录学习笔记，同时网站上总结了各个编程语言和计算机基础相关的常见面试题。
卡码简历：jianli.kamacoder（com域名），在线简历制作工具，可以帮助读者智能排版简历，同时网站上有各个岗位的简历模版。
在微信公众号“代码随想录”后台回复“算法学习”，可加入算法学习交流群，获取配套学习资料，包括本书代码、题目判题系统链接、视频讲解链接、简历模板、面试题资料等。
我在B站（ID：代码随想录）上更新了算法公开课系列，口碑很好，相信能帮助读者更好地学习算法。
勘误
个人能力有限，书中难免存在疏漏，恳请读者批评指正。
微信公众号“代码随想录”底部设有新的菜单入口，读者在发现书中错误时可通过该入口反馈，确认后的勘误将在此公示。
致谢
感谢录友们（“代码随想录”的朋友们，也是微信公众号的忠实读者）的口口相传。每次推荐都在帮助他人，也在助力“代码随想录”。没有录友们的自发宣传，便没有“代码随想录”这一IP的诞生与发展。在此由衷感谢每一位录友。
感谢我的父母，求学之路历历在目，愿他们身体健康。
感谢我的妻子。她是“代码随想录”的忠实读者，也是《代码随想录2：图论》从无到有的见证者。她的陪伴，使我对人生的新征程充满期待。


孙秀洋（@程序员Carl）
2025年8月28日于深圳南山

本书配套资源下载

对不起，暂无音视频资源！