内容
算法详解系列图书共有4卷，本书是第2卷—图算法和数据结构。本书共有6章，主要介绍了3个主题，分别是图的搜索和应用、最短路径以及数据结构。附录简单回顾了渐进性表示法。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。 本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维和计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。
作者
Tim Roughgarden 是斯坦福大学计算机科学系的教授,也是该校管理科学和工程系的客座教授，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第一卷，基于他从2012年开始定期举行的在线算法课程编写。
目录
第1章图的基础知识1
1.1 基本术语 1
1.3 图形的度量 3
1.3.2 稀疏图和稠密图 4
1.4 图的表示方法 7
1.4.2 邻接矩阵 8
1.4.4 小测验1.2和小测验1.3的答案 10
1.6 章末习题 12
2.1 概述 14
2.1.2 零代价的基本算法 16
2.1.4 宽度优先的搜索和深度优先的搜索 20
2.2 宽度优先的搜索和最短路径 23
2.2.2 BFS的伪码 24
2.2.4 正确性和运行时间 27
2.2.6 小测验2.1的答案 31
2.3.1 连通分量 32
2.3.3 UCC（无向图连通分量）算法 34
2.3.5 UCC算法的正确性和运行时间 36
2.4 深度优先的搜索 37
2.4.2 DFS的伪码 39
2.5 拓扑排序 41
2.5.2 什么时候存在拓扑顺序 43
2.5.4 通过DFS的拓扑排序 46
2.5.6 正确性和运行时间 48
*2.6 计算强连通分量 50
2.6.2 为什么要使用深度优先的搜索 52
2.6.4 Kosaraju的伪码 57
2.6.6 正确性和运行时间 60
2.7 Web的结构 61
2.7.2 蝴蝶结 63
2.8 本章要点 65
第3章 Dijkstra最短路径算法 70
3.1.1 问题定义 70
3.1.3 为什么不使用宽度优先的搜索 72
3.2 Dijkstra算法 74
3.2.2 一个例子 76
3.3.1 一种虚假的简化 77
3.3.3 非负边长时的正确性 78
3.5 本章要点 84
第4章 堆数据结构 88
4.1.1 选择正确的数据结构 88
4.2 堆所支持的操作 90
4.2.2 其他操作 92
4.3.1 应用：排序 93
4.3.3 应用：中位值维护 96
4.4.1 为什么要使用堆 98
4.4.3 维持不变性 101
*4.5 实现细节 104
4.5.2 数组形式的堆 106
4.5.4 在O (log n)时间内实现ExtractMin操作 111
4.7 章末习题 114
5.1 有序数组 117
5.1.2 有序数组不支持的操作 119
*5.3 实现细节 122
5.3.2 搜索树的高度 123
5.3.4 在O（高度）时间内实现Min和Max 125
5.3.6 在O(n)时间内实现OutputSorted操作 127
5.3.8 在O（高度）时间内实现Delete操作 129
5.3.10 小测验5.1的答案 134
5.4.1 努力实现更好的平衡 134
5.5 本章要点 137
第6章 散列表和布隆过滤器 140
6.2 散列表的应用 143
6.2.2 应用：两数之和问题 145
6.2.4 小测验6.2的答案 148
6.3.1 两个简单的解决方案 148
6.3.3 冲突是不可避免的 150
6.3.5 解决冲突的方法：开放地址法 153
6.3.7 小测验6.3至小测验6.5的答案 160
6.4.1 负载和性能 162
6.4.3 选择散列函数 165
6.4.5 小测验6.6的答案 166
6.5.1 布隆过滤器支持的操作 167
6.5.3 布隆过滤器的实现 169
6.6.1 启发式假设 172
6.6.3 假阳性率 175
6.6.5 小测验6.7的答案 177
6.8 章末习题 179
部分习题答案 187