由于这本书的习题非常多，并且版本（如第5版、第6版）和习题编号可能略有不同，我将不提供逐题的代码答案（这会侵犯版权，且价值有限），而是采用一种更高效的方式,为你提供：
（图片来源网络，侵删）
- 核心思想与解题模式：针对每一章的核心算法和题型,总结其解题思路和常用技巧。
- 典型习题的代码实现与解析：选择每章最具代表性的习题,提供详细的代码实现和思路讲解。
- 关键概念的总结：以问答形式梳理每章的重点和难点。
- 学习建议与资源：如何更好地学习这本书,以及可以参考的在线资源。
通用学习建议
在开始之前,请记住几个重要的学习原则：
- 动手编码，而非死记硬背：理解算法的原理比背诵代码重要得多，亲手实现每一个数据结构和算法，即使遇到困难,这个过程也能让你理解得更深刻。
- 画图辅助理解：对于树、图等非线性结构，画图是最好的理解方式，模拟插入、删除、遍历等操作的过程。
- 分析复杂度：对于每一个你实现的算法,都要能清晰地分析其时间复杂度和空间复杂度。
- 先模仿，再创造：从书上的示例代码开始，尝试修改它，解决类似的变种问题,最后尝试自己设计新的算法。
分章节答案与解析
第 1 章：引论
本章是基础,重点是理解算法分析的基本概念。
核心思想与解题模式：
- 问题：分析算法的时间/空间复杂度。
- 模式：
- 识别基本操作：找到算法中最频繁执行的操作（如循环体内的比较、赋值）。
- 计算执行次数：用数学表达式（如
n^2,n log n）表示基本操作执行次数与输入规模n的关系。 - 应用大O表示法：忽略常数项和低阶项，只保留最高阶项,得到最终的复杂度。
典型习题解析：
（图片来源网络，侵删）
习题 1.1: public static int example1(int[] arr) { int n = arr.length; int total = 0; for (int i = 0; i < n; i++) { total += arr[i]; } return total; }
- 分析：
- 基本操作是
total += arr[i]。 - 循环执行了
n次。 - 执行次数与
n成线性关系。
- 基本操作是
- 答案：时间复杂度为 O(n)。
习题 1.2: public static int example2(int[] arr) { int n = arr.length; int total = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { total += arr[i] * arr[j]; } } return total; }
- 分析：
- 基本操作是
total += arr[i] * arr[j]。 - 外层循环
n次，内层循环n次，总共执行n * n = n^2次。 - 执行次数与
n的平方成正比。
- 基本操作是
- 答案：时间复杂度为 O(n²)。
关键概念总结 (Q&A):
- Q: 什么是大O表示法？
- A: 它是一种描述算法时间/空间增长率的数学符号，用来表示算法在最坏情况下的性能上限，它关注的是当输入规模
n趋近于无穷大时，算法的增长趋势,忽略常数因子和低阶项。
- A: 它是一种描述算法时间/空间增长率的数学符号，用来表示算法在最坏情况下的性能上限，它关注的是当输入规模
- Q: O(1), O(log n), O(n), O(n log n), O(n²) 各代表什么？
- A:
- O(1): 常数时间，操作时间不随输入规模变化，数组访问
arr[0]。 - O(log n): 对数时间，每次操作都将问题规模减半,二分查找。
- O(n): 线性时间，操作时间与输入规模成正比,遍历数组。
- O(n log n): 线性对数时间，很多高效排序算法（如归并排序、堆排序）的复杂度。
- O(n²): 平方时间，通常涉及嵌套循环，简单的排序算法（如冒泡排序）。
- O(1): 常数时间，操作时间不随输入规模变化，数组访问
- A:
第 2 章：算法分析
本章深入探讨更复杂的分析技巧,如递归方程的求解。
（图片来源网络，侵删）
核心思想与解题模式：
- 问题：分析递归算法的复杂度。
- 模式：
- 写出递归方程：将算法的运行时间
T(n)表示为更小子问题的运行时间之和,加上其他操作的耗时。 - 求解递归方程：主要方法有三种：
- 代入法：猜测一个解,然后用数学归纳法证明。
- 递归树法：将递归过程画成一棵树,计算每层的代价和总代价。
- 主方法：适用于形如
T(n) = aT(n/b) + f(n)的标准分治递归方程。
- 写出递归方程：将算法的运行时间
典型习题解析：
分析二分查找的复杂度：
- 递归方程:
T(n) = T(n/2) + O(1)T(n/2): 在一半的数组中继续查找。O(1): 每次查找的比较操作是常数时间。
- 求解 (递归树法):
- 根节点代价为
O(1)。 - 它有一个子问题，规模为
n/2，代价也为O(1)。 - 这个子问题又有一个子问题，规模为
n/4，代价为O(1)。 - ...直到问题规模为 1。
- 树的高度为
log₂n。 - 总代价 = 每层代价 × 层数 =
O(1) * log₂n = O(log n)。
- 根节点代价为
- 答案：时间复杂度为 O(log n)。
关键概念总结 (Q&A):
- Q: 什么是递归方程？如何用主方法求解？
- A: 递归方程是描述递归算法运行时间的数学公式，主方法适用于
T(n) = aT(n/b) + f(n)的形式，它比较f(n)和n^(log_b a)的大小关系，根据三种情况得出结论：- 情况1:
f(n) = O(n^(log_b a - ε))(ε > 0)，则T(n) = Θ(n^(log_b a))。 - 情况2:
f(n) = Θ(n^(log_b a) * log^k n)，则T(n) = Θ(n^(log_b a) * log^(k+1) n)。 - 情况3:
f(n) = Ω(n^(log_b a + ε))(ε > 0) 且af(n/b) ≤ cf(n)(c < 1)，则T(n) = Θ(f(n))。
- 情况1:
- A: 递归方程是描述递归算法运行时间的数学公式，主方法适用于
- Q: 平摊分析是什么？
- A: 一种分析序列操作成本的方法，它不关心单个操作的最坏情况，而是计算所有操作的平均成本，如果一个昂贵的操作可以分摊到之前的多个廉价操作上，那么平摊成本可能很低,经典例子是动态数组的扩容。
第 3 章：表、栈和队列
本章介绍线性数据结构,重点是理解它们的抽象和实现。
核心思想与解题模式：
- 问题：实现或使用表、栈、队列,并分析其操作的复杂度。
- 模式：
- 数组实现 vs. 链表实现：
- 数组：访问快
O(1)，但插入/删除中间元素慢O(n),扩容有开销。 - 链表：插入/删除快
O(1)（已知节点位置），访问慢O(n),无扩容问题。
- 数组：访问快
- 栈：后进先出，使用
addFirst()/removeFirst()(LinkedList) 或push()/pop()(数组末尾)。 - 队列：先进先出，使用
addLast()/removeFirst()(LinkedList) 或offer()/poll()(循环数组)。
- 数组实现 vs. 链表实现：
典型习题解析：
习题：使用两个栈实现一个队列。
-
思路:
- 准备两个栈，
stackIn和stackOut。 - 入队: 直接压入
stackIn。O(1)。 - 出队:
stackOut不为空,直接弹出栈顶元素。stackOut为空，则将stackIn的所有元素依次弹出并压入stackOut。stackOut的栈顶元素就是队首元素,弹出它。
- peek(): 与出队逻辑类似,只是弹出后要压回去。
- 准备两个栈，
-
代码实现 (Java):
import java.util.Stack; public class MyQueue { private Stack<Integer> stackIn; private Stack<Integer> stackOut; public MyQueue() { stackIn = new Stack<>(); stackOut = new Stack<>(); } public void push(int x) { stackIn.push(x); } public int pop() { if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } return stackOut.pop(); } public int peek() { if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } return stackOut.peek(); } public boolean empty() { return stackIn.isEmpty() && stackOut.isEmpty(); } } -
复杂度分析:
- 单次操作: 最坏情况下
pop()或peek()需要转移所有元素，是O(n)。 - 均摊分析: 考虑一系列操作，每个元素从
stackIn到stackOut只会被转移一次，均摊到每个元素上的操作成本是O(1)。
- 单次操作: 最坏情况下
关键概念总结 (Q&A):
- Q: 什么是迭代器？
- A: 一个对象，它允许你遍历一个容器（如列表）中的元素，而无需关心容器内部的实现细节，Java 中的
Iterator接口提供了hasNext(),next(),remove()方法。
- A: 一个对象，它允许你遍历一个容器（如列表）中的元素，而无需关心容器内部的实现细节，Java 中的
- Q: 什么是
LinkedList的优势？- A: 在列表的两端（头和尾）进行插入和删除操作非常高效，时间复杂度为
O(1),这使得它非常适合实现栈和队列。
- A: 在列表的两端（头和尾）进行插入和删除操作非常高效，时间复杂度为
第 4 章：树
本章是全书的核心之一，重点是二叉树、二叉搜索树和平衡树。
核心思想与解题模式：
- 问题：实现树的遍历、查找、插入,或分析树的性质。
- 模式：
- 遍历：
- 前序: 根 -> 左 -> 右,常用于复制树或前缀表达式。
- 中序: 左 -> 根 -> 右,对二叉搜索树进行中序遍历可以得到有序序列。
- 后序: 左 -> 右 -> 根,常用于释放树节点内存或后缀表达式。
- 层序: 使用队列,逐层访问节点。
- 二叉搜索树:
- 性质: 左子树所有节点 < 根节点 < 右子树所有节点。
- 查找/插入/删除: 平均
O(log n)，最坏（树退化为链表）O(n)。
- 平衡树 (AVL/红黑树):
- 目的: 通过旋转操作保持树的平衡，确保查找/插入/删除操作的最坏时间复杂度为
O(log n)。
- 目的: 通过旋转操作保持树的平衡，确保查找/插入/删除操作的最坏时间复杂度为
- 遍历：
典型习题解析：
习题：判断一棵二叉树是否是二叉搜索树。
-
思路 (递归):
- 一个节点要成为BST的根，它必须大于其左子树中的所有节点,且小于其右子树中的所有节点。
- 递归地检查每个节点，并传递一个合法的范围
(min, max)。 - 初始时，根节点的范围是
(Long.MIN_VALUE, Long.MAX_VALUE)。 - 对于左子树，范围变为
(min, parent.val)。 - 对于右子树，范围变为
(parent.val, max)。
-
代码实现 (Java):
// TreeNode class definition class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } class Solution { public boolean isValidBST(TreeNode root) { return helper(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean helper(TreeNode node, long min, long max) { if (node == null) { return true; } // 当前节点的值必须在 (min, max) 范围内 if (node.val <= min || node.val >= max) { return false; } // 递归检查左右子树 return helper(node.left, min, node.val) && helper(node.right, node.val, max); } } -
复杂度分析：每个节点只被访问一次，时间复杂度为 O(n)。
关键概念总结 (Q&A):
- Q: 什么是树的旋转？
- A: 一种重构树结构的操作，用于在插入或删除节点后恢复树的平衡，它不改变中序遍历的顺序，但可以改变树的形态,常见的有左旋和右旋。
- Q: AVL树和红黑树有什么区别？
- A:
- AVL树: 更严格的平衡，任何节点的两个子树的高度差绝对值不超过1，这保证了更严格的平衡，查找可能更快，但插入/删除时的旋转操作更频繁。
- 红黑树: 更宽松的平衡，通过“红黑”着色规则和旋转来保证从根到任意叶子节点的最长路径不超过最短路径的两倍，插入/删除的旋转和重着色操作更少，因此在实践中性能通常更好（如 Java 的
TreeMap和TreeSet使用红黑树）。
- A:
第 5 章：散列
本章介绍散列表,这是一种实现字典和集合的高效数据结构。
核心思想与解题模式：
- 问题：实现散列表，处理冲突,分析性能。
- 模式：
- 核心组件:
- 散列函数: 将键映射到数组索引,好的散列函数应均匀分布。
- 冲突解决策略:
- 分离链接法: 每个桶是一个链表,冲突的元素都挂在同一个链表上。
- 开放寻址法: 冲突时，按照某种规则（如线性探测、二次探测）寻找下一个空的桶。
- 性能分析:
- 平均情况下（假设散列函数均匀），查找、插入、删除都是 O(1)。
- 最坏情况下（所有元素都冲突），退化为链表，复杂度为 O(n)。
- 核心组件:
典型习题解析：
习题：实现一个简单的基于分离链接法的散列表。
-
思路:
- 创建一个数组（桶数组），每个元素是一个链表（
LinkedList或Node链表）。 put(key, value): 计算索引hash(key) % capacity，遍历该索引处的链表，如果找到相同 key，则更新 value；否则,在链表头部添加新节点。get(key): 同样计算索引，遍历链表查找 key，找到则返回 value，否则返回 null。remove(key): 计算索引，遍历链表找到 key 并删除。
- 创建一个数组（桶数组），每个元素是一个链表（
-
代码实现 (Java):
class MyHashMap { private static final int DEFAULT_CAPACITY = 16; private LinkedList<Entry>[] buckets; private static class Entry { int key; int value; Entry next; Entry(int key, int value) { this.key = key; this.value = value; } } public MyHashMap() { buckets = new LinkedList[DEFAULT_CAPACITY]; for (int i = 0; i < DEFAULT_CAPACITY; i++) { buckets[i] = new LinkedList<>(); } } private int getIndex(int key) { return Math.abs(key % buckets.length); } public void put(int key, int value) { int index = getIndex(key); LinkedList<Entry> bucket = buckets[index]; for (Entry entry : bucket) { if (entry.key == key) { entry.value = value; // Update existing key return; } } bucket.addFirst(new Entry(key, value)); // Add new entry } public int get(int key) { int index = getIndex(key); LinkedList<Entry> bucket = buckets[index]; for (Entry entry : bucket) { if (entry.key == key) { return entry.value; } } return -1; // Not found } public void remove(int key) { int index = getIndex(key); LinkedList<Entry> bucket = buckets[index]; bucket.removeIf(entry -> entry.key == key); } } -
复杂度分析:
- 平均情况: 假设散列函数良好，每个桶的元素数量很少，操作接近 O(1)。
- 最坏情况: 所有 key 都映射到同一个桶，操作退化为链表操作，为 O(n)。
关键概念总结 (Q&A):
- Q: 什么是负载因子？为什么需要动态扩容？
- A: 负载因子 = 元素数量 / 桶的数量，它是衡量散列表冲突程度的标准，当负载因子超过某个阈值（如 Java 中的 0.75），意味着冲突变得频繁，性能下降，通过创建一个更大的桶数组，并重新散列所有元素到新数组中，来降低负载因子,保持高效性能。
- Q: 什么是完美散列？
- A: 一种没有冲突的散列技术，它通常需要两阶段散列：首先使用一个常规散列函数，然后根据 key 的集合构建一个完美的二级散列函数，它适用于静态的 key 集合。
第 6 章：优先队列（堆）
本章介绍优先队列,通常用堆来实现。
核心思想与解题模式：
- 问题：实现堆，或使用堆解决 Top-K 问题。
- 模式：
- 堆的性质: 完全二叉树，大顶堆：父节点 >= 子节点；小顶堆：父节点 <= 子节点。
- 核心操作:
insert: 添加到末尾，"上浮" 调整。deleteMin/deleteMax: 取走根节点，将末尾元素放到根，"下沉" 调整。
- 应用:
- 堆排序: 构建堆,然后反复删除堆顶。
- Top-K 问题: 使用一个大小为 K 的堆，找前 K 大个数,用一个小顶堆。
典型习题解析：
习题：找到数据流中第 K 大的元素。
-
思路:
- 使用一个小顶堆，并限制其大小为
K。 - 遍历数据流中的每个元素
num：- 将
num加入堆。 - 如果堆的大小超过
K，则弹出堆顶元素（当前堆中最小的元素）。
- 将
- 处理完所有数据后，堆顶元素就是第 K 大的元素。
- 使用一个小顶堆，并限制其大小为
-
代码实现 (Java - 使用
PriorityQueue):import java.util.PriorityQueue; public class KthLargest { private PriorityQueue<Integer> minHeap; private int k; public KthLargest(int k, int[] nums) { this.k = k; this.minHeap = new PriorityQueue<>(k); // 初始容量为k for (int num : nums) { add(num); } } public int add(int val) { minHeap.offer(val); if (minHeap.size() > k) { minHeap.poll(); // 弹出最小的，保持堆大小为k } return minHeap.peek(); // 堆顶就是第k大的 } } -
复杂度分析:
add操作：堆插入和删除操作的时间复杂度为O(log K)。- 初始化：如果数组大小为 N，则为
O(N log K)。 - 总体来看,非常适合处理数据流。
关键概念总结 (Q&A):
- Q: 堆和平衡搜索树（如红黑树）有什么区别？
- A:
- 堆: 结构更简单（完全二叉树），实现更高效，擅长找最值（堆顶），但不支持高效的查找、删除任意元素等操作。
- 平衡搜索树: 结构更复杂，支持所有字典操作（查找、插入、删除、找最值），时间复杂度均为
O(log n),但常数因子通常比堆大。
- A:
- Q: 什么是斐波那契堆？
- A: 一种更高级的堆实现，其
insert和decrease-key操作是O(1)（均摊）的，这使得它在某些图算法（如 Dijkstra 算法）中理论上更高效，但实现复杂,实际应用中不如二叉堆普遍。
- A: 一种更高级的堆实现，其
第 7 章：排序
本章详细介绍各种排序算法。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 特点 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 对小规模或基本有序的数组高效。 |
| 希尔排序 | O(n log² n) | O(n²) | O(1) | 不稳定 | 插入排序的改进，通过增量序列分组。 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 利用堆数据结构，原地排序。 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 分治法，稳定且高效，但需要额外空间。 |
| 快速排序 | O(n log n) | O(n²) | O(log n) (栈空间) | 不稳定 | 实际应用中最快的排序算法，平均性能最好。 |
| 三路快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 针对大量重复元素的优化。 |
典型习题解析：
习题：实现快速排序。
-
思路:
- 选择基准: 从数组中选择一个元素作为
pivot。 - 分区: 将数组分为三部分：
< pivot的元素、= pivot的元素、> pivot的元素，分区后，pivot最终到达其正确的位置。 - 递归: 对左右两个子数组递归地应用快速排序。
- 选择基准: 从数组中选择一个元素作为
-
代码实现 (Java - Lomuto 分区方案):
public class QuickSort { public void sort(int[] arr, int low, int high) { if (low < high) { // pi is partitioning index, arr[pi] is now at right place int pi = partition(arr, low, high); // Recursively sort elements before partition and after partition sort(arr, low, pi - 1); sort(arr, pi + 1, high); } } private int partition(int[] arr, int low, int high) { int pivot = arr[high]; // 选择最后一个元素作为pivot int i = (low - 1); // 小于pivot的元素的边界 for (int j = low; j < high; j++) { // 如果当前元素小于或等于pivot if (arr[j] <= pivot) { i++; // 交换arr[i]和arr[j] swap(arr, i, j); } } // 将pivot放到正确的位置上 swap(arr, i + 1, high); return i + 1; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } -
复杂度分析:
- 平均:
O(n log n)。 - 最坏: 当数组已经有序或逆序，且总是选择第一个或最后一个元素作为 pivot 时，分区极度不均，退化为
O(n²)。 - 空间:
O(log n),由递归调用栈的深度决定。
- 平均:
关键概念总结 (Q&A):
- Q: 什么是排序算法的稳定性？
- A: 如果待排序的序列中有两个相等的元素，排序后它们的相对位置保持不变，则该排序算法是稳定的，排序前是
(a, 1), (b, 2), (a, 2)，稳定排序后(a, 1), (a, 2), (b, 2)，不稳定排序可能会变成(a, 2), (a, 1), (b, 2)。
- A: 如果待排序的序列中有两个相等的元素，排序后它们的相对位置保持不变，则该排序算法是稳定的，排序前是
- Q: 为什么快速排序通常比归并排序快？
- A: 主要原因是缓存局部性，快速排序的分区操作是“原地”的，数据访问模式是顺序的，对 CPU 缓存更友好，而归并排序在合并阶段需要额外的数组，并且数据跳跃性访问较多,缓存命中率相对较低。
第 8 章：不相交集合（并查集）
本章介绍一种处理动态连通性问题的数据结构。
核心思想与解题模式：
- 问题：高效地处理“合并”和“查询”两个集合的操作。
- 模式:
- 数据结构: 用一个数组
parent[i]表示元素i的父节点。 - 两种优化:
- 按秩合并: 在合并时，将深度较小的树连接到深度较大的树下,避免树退化。
- 路径压缩: 在
find操作中，将查找路径上的所有节点都直接指向根节点，压缩路径,使后续查找更快。
- 应用: Kruskal 最小生成树算法。
- 数据结构: 用一个数组
典型习题解析：
习题：实现并查集，支持 find 和 union 操作。
-
思路:
- 初始化
parent数组，每个元素指向自己，rank数组为 0。 find(x):parent[x] != x，递归地find(parent[x])。- 路径压缩: 将
parent[x]直接设置为递归返回的根节点。
union(x, y):- 分别找到
x和y的根节点rootX,rootY。 rootX == rootY，已经在同一个集合,返回。- 按秩合并: 比较
rank[rootX]和rank[rootY]。rank[rootX] < rank[rootY]，将rootX的父节点设为rootY。rank[rootX] > rank[rootY]，将rootY的父节点设为rootX。- 如果相等，将任意一个设为另一个的父节点,并将秩加一。
- 分别找到
- 初始化
-
代码实现 (Java):
public class UnionFind { private int[] parent; private int[] rank; public UnionFind(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 1; // 初始时，每个集合的秩（高度）为1 } } public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x]; } public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { // 按秩合并 if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else { parent[rootY] = rootX; rank[rootX]++; } } } } -
复杂度分析:
- 使用了路径压缩和按秩合并后，
find和union操作的时间复杂度接近 O(α(n))，α(n)是阿克曼函数的反函数，增长极其缓慢，对于任何可想象的n，其值都小于 5,可以认为是常数时间。
- 使用了路径压缩和按秩合并后，
关键概念总结 (Q&A):
- Q: 路径压缩和按秩合并分别是什么？为什么它们很重要？
- A: 它们是保证并查集高效运行的关键优化。
- 路径压缩：让
find操作返回后，路径上的节点都直接“挂”到根下，使得未来的find操作更快。 - 按秩合并：合并时，总是将矮的树接到高的树下，这限制了树的深度,防止了树退化成链表。
- 重要性: 单独使用任一优化，都能获得较好的性能。同时使用两者，能使操作的时间复杂度达到近乎线性的水平，即
O(α(n)),效率极高。
- 路径压缩：让
- A: 它们是保证并查集高效运行的关键优化。
第 9 章：图算法
本章介绍图的基本表示和遍历算法,以及一些经典算法。
核心思想与解题模式：
- 问题：遍历图，或找到最短路径、最小生成树等。
- 模式:
- 图的表示:
- 邻接矩阵: 二维数组，适合稠密图，查找边快
O(1)，但空间大O(V²)。 - 邻接表: 数组 + 链表/列表，适合稀疏图，空间效率高
O(V+E)，查找边慢O(V)。
- 邻接矩阵: 二维数组，适合稠密图，查找边快
- 遍历:
- BFS (广度优先): 使用队列，按层遍历,适合找无权图的最短路径。
- DFS (深度优先): 使用栈（或递归），走到底再回溯，适合找路径、检测环。
- 最短路径:
- Dijkstra: 单源最短路径，边权非负,使用优先队列。
- Bellman-Ford: 单源最短路径，允许负权边,可检测负权环。
- Floyd-Warshall: 多源最短路径,使用动态规划。
- 最小生成树:
- Prim (普里姆): 从一个顶点开始，贪婪地选择与当前树连接的最小边权边,适合稠密图。
- Kruskal (克鲁斯卡尔): 将所有边按权值排序，从小到大选择不构成环的边，适合稀疏图,使用并查集。
- 图的表示:
典型习题解析：
习题：实现图的深度优先搜索。
-
思路:
- 访问一个未被访问的节点
v,将其标记为已访问。 - 递归地访问
v的所有未被访问的邻接节点。
- 访问一个未被访问的节点
-
代码实现 (Java - 邻接表):
import java.util.*; public class GraphDFS { private int V; // 顶点数 private LinkedList<Integer> adj[]; // 邻接表 public GraphDFS(int v) { V = v; adj = new LinkedList[v]; for (int i = 0; i < v; ++i) { adj[i] = new LinkedList(); } } public void addEdge(int v, int w) { adj[v].add(w); // 无向图需要再加 adj[w].add(v); } public void DFSUtil(int v, boolean visited[]) { // 标记当前节点为已访问，并打印 visited[v] = true; System.out.print(v + " "); // 递归访问所有邻接且未访问的节点 Iterator<Integer> i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) { DFSUtil(n, visited); } } } public void DFS(int v) { // 标记所有节点为未访问 boolean visited[] = new boolean[V]; // 从v开始调用递归辅助函数 DFSUtil(v, visited); } } -
复杂度分析:
- 时间：
O(V + E),每个顶点和每条边都被访问一次。 - 空间：
O(V)，用于存储visited数组和递归调用栈。
- 时间：
关键概念总结 (Q&A):
- Q: Dijkstra 算法为什么不能处理负权边？
- A: Dijkstra 算法的核心是，当一个节点被从优先队列中取出时，就确定了它的最短路径，但如果存在负权边，一个已经被标记为“已确定”的节点，可能通过一条负权边更新为更短的路径，这导致了算法的错误，Bellman-Ford 算法通过多轮松弛来处理这种情况。
- Q: Prim 和 Kruskal 算法的核心区别是什么？
- A:
- Prim 算法：点集驱动，从一个顶点开始
- A:
