算法详解(卷2)——图算法和数据结构

算法是计算机科学的核心与灵魂。算法的应用范围极广，网络路由、计算基因组学、公钥加密学和数据库系统等的实现都需要算法。研究算法可以帮助我们成为更优秀的程序员，可以让我们具有更缜密的思维，并成功应对各种场合的技术面试。 这是一本非常容易上手的算法入门图书，它可作为程序员的学习用书，也适合想要学习算法和想提升算法思维能力的读者阅读。 本书主要包括以下内容： 图的搜索和应用； 散列表； 最短路径算法； 布隆过滤器； 随机化算法； 堆； 搜索树。

算法详解系列图书共有4卷，本书是第2卷—图算法和数据结构。本书共有6章，主要介绍了3个主题，分别是图的搜索和应用、最短路径以及数据结构。附录简单回顾了渐进性表示法。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。

蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大学计算机科学系的教授,也是该校管理科学和工程系的客座教授，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第一卷，基于他从2012年开始定期举行的在线算法课程编写。

第1章图的基础知识
1.1基本术语
1.2图的一些应用
1.3图形的度量
1.3.1图的边数量
1.3.2稀疏图和稠密图
1.3.3小测验1.1的答案
1.4图的表示方法
1.4.1邻接列表
1.4.2邻接矩阵
1.4.3图的表示形式之间的比较
1.4.4小测验1.2和小测验1.3的答案
1.5本章要点
1.6章末习题
第2章图的搜索及其应用
2.1概述
2.1.1一些应用
2.1.2零代价的基本算法
2.1.3通用的图搜索算法
2.1.4宽度优先的搜索和深度优先的搜索
2.1.5GenericSearch算法的正确性
2.2宽度优先的搜索和最短路径
2.2.1高层思路
2.2.2BFS的伪码
2.2.3BFS的一个例子
2.2.4正确性和运行时间
2.2.5最短路径
2.2.6小测验2.1的答案
2.3计算连通分量
2.3.1连通分量
2.3.2连通分量的应用
2.3.3UCC（无向图连通分量）算法
2.3.4UCC算法的一个例子
2.3.5UCC算法的正确性和运行时间
2.3.6小测验2.2的答案
2.4深度优先的搜索
2.4.1DFS的一个例子
2.4.2DFS的伪码
2.4.3正确性和运行时间
2.5拓扑排序
2.5.1拓扑顺序
2.5.2什么时候存在拓扑顺序
2.5.3计算拓扑顺序
2.5.4通过DFS的拓扑排序
2.5.5拓扑排序的一个例子
2.5.6正确性和运行时间
2.5.7小测验2.3和小测验2.4的答案
2.6计算强连通分量
2.6.1强连通分量的定义
2.6.2为什么要使用深度优先的搜索
2.6.3为什么要使用反转的图
2.6.4Kosaraju的伪码
2.6.5一个例子
2.6.6正确性和运行时间
2.6.7小测验2.5和小测验2.6的答案
2.7Web的结构
2.7.1Web图
2.7.2蝴蝶结
2.7.3主要发现
2.8本章要点
2.9章末习题
第3章Dijkstra最短路径算法
3.1单源最短路径问题
3.1.1问题定义
3.1.2一些前提条件
3.1.3为什么不使用宽度优先的搜索
3.1.4小测验3.1的答案
3.2Dijkstra算法
3.2.1伪码
3.2.2一个例子
3.3为什么Dijkstra算法是正确的
3.3.1一种虚假的简化
3.3.2Dijkstra算法的一个糟糕例子
3.3.3非负边长时的正确性
3.4算法的实现及其运
……