前言
资源与支持
第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.5 GenericSearch算法的正确性
2.2 宽度优先的搜索和最短路径
2.2.1 高层思路
2.2.2 BFS的伪码
2.2.3 BFS的一个例子
2.2.4 正确性和运行时间
2.2.5 最短路径
2.2.6 小测验2.1的答案
2.3 计算连通分量
2.3.1 连通分量
2.3.2 连通分量的应用
2.3.3 UCC(无向图连通分量)算法
2.3.4 UCC算法的一个例子
2.3.5 UCC算法的正确性和运行时间
2.3.6 小测验2.2的答案
2.4 深度优先的搜索
2.4.1 DFS的一个例子
2.4.2 DFS的伪码
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.4 Kosaraju的伪码
2.6.5 一个例子
2.6.6 正确性和运行时间
2.6.7 小测验2.5和小测验2.6的答案
2.7 Web的结构
2.7.1 Web图
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.2 Dijkstra算法
3.2.1 伪码
3.2.2 一个例子
*3.3 为什么Dijkstra算法是正确的
3.3.1 一种虚假的简化
3.3.2 Dijkstra算法的一个糟糕例子
3.3.3 非负边长时的正确性
3.4 算法的实现及其运行时间
3.5 本章要点
3.6 章末习题
挑战题
编程题
第4章 堆数据结构
4.1 数据结构概述
4.1.1 选择正确的数据结构
4.1.2 进入更高层次
4.2 堆所支持的操作
4.2.1 Insert和ExtractMin
4.2.2 其他操作
4.3 堆的应用
4.3.1 应用:排序
4.3.2 应用:事件管理器
4.3.3 应用:中位值维护
4.4 Dijkstra算法的提速
4.4.1 为什么要使用堆
4.4.2 计划
4.4.3 维持不变性
4.4.4 运行时间
*4.5 实现细节
4.5.1 树形式的堆
4.5.2 数组形式的堆
4.5.3 在O (log n)时间内实现Insert操作
4.5.4 在O (log n)时间内实现ExtractMin操作
4.6 本章要点
4.7 章末习题
挑战题
编程题
第5章 搜索树
5.1 有序数组
5.1.1 有序数组支持的操作
5.1.2 有序数组不支持的操作
5.2 搜索树支持的操作
*5.3 实现细节
5.3.1 搜索树的属性
5.3.2 搜索树的高度
5.3.3 在O(高度)时间内实现Search
5.3.4 在O(高度)时间内实现Min和Max
5.3.5 在O(高度)时间内实现Predecessor
5.3.6 在O (n)时间内实现OutputSorted操作
5.3.7 在O(高度)时间内实现Insert操作
5.3.8 在O(高度)时间内实现Delete操作
5.3.9 强化的搜索树支持Select操作
5.3.10 小测验5.1的答案
*5.4 平衡搜索树
5.4.1 努力实现更好的平衡
5.4.2 旋转
5.5 本章要点
5.6 章末习题
编程题
第6章 散列表和布隆过滤器
6.1 支持的操作
6.2 散列表的应用
6.2.1 应用:消除重复
6.2.2 应用:两数之和问题
6.2.3 应用:搜索巨大的状态空间
6.2.4 小测验6.2的答案
*6.3 实现的高层思路
6.3.1 两个简单的解决方案
6.3.2 散列函数
6.3.3 冲突是不可避免的
6.3.4 解决冲突的方法:链地址法
6.3.5 解决冲突的方法:开放地址法
6.3.6 良好的散列函数是怎么样的
6.3.7 小测验6.3至小测验6.5的答案
*6.4 更多的实现细节
6.4.1 负载和性能
6.4.2 管理散列表的负载
6.4.3 选择散列函数
6.4.4 选择冲突解决策略
6.4.5 小测验6.6的答案
6.5 布隆过滤器的基础知识
6.5.1 布隆过滤器支持的操作
6.5.2 布隆过滤器的应用
6.5.3 布隆过滤器的实现
*6.6 布隆过滤器的启发式分析
6.6.1 启发式假设
6.6.2 部分位被设置为1
6.6.3 假阳性率
6.6.4 结束语
6.6.5 小测验6.7的答案
6.7 本章要点
6.8 章末习题
编程题
附录 快速回顾渐进性表示法
部分习题答案
· · · · · · (
收起)
3 有用 威士忌的碎冰 2022-09-03 10:30:55 江苏
最短路径讲的很精彩, 跳过了二分搜索树.
0 有用 老文化新青年 2023-05-04 19:45:23 北京
要说没收获吧,作者讲的内容确实不错。 要说有收获吧,感觉详略安排不好,很多点没看太明白,序言说适合新手,实际上对新手不友好,提供的社区解决问题也不是太方便,我主张这类书一定是要能让读者很轻松就能获取代码的。
0 有用 ruanwsh 2024-04-23 23:03:36 广东
讲得比较详细,不过前后的几章关系不是很大。
0 有用 G雨殇(私信) 2024-07-19 16:20:46 山西
对新手不友好 看的比较费劲 需要自己动脑才能明白他说了点什么
0 有用 游戏人间 2025-07-08 18:11:48 福建
《算法详解 卷2》把图算法和数据结构讲得太透彻了!从BFS、DFS的图搜索,到Dijkstra的最短路径,再到堆、搜索树、散列表这些核心数据结构,覆盖得系统又清晰。每种算法都讲清时间复杂度,像Dijkstra优化后O((m+n)logn),堆操作O(logn),实用又好懂。案例贴合应用,比如BFS算最短路径、散列表去重,新手能快速上手。想扎实掌握图算法和数据结构的同学,这本书绝对值得入手!