本文章依据《算法导论》所编写，涵盖书中重点内容，用于期末复习。
祝大家 不挂科！

第二章：算法基础

插排：

INSERTION-SORT(A)
1. for j = 2 to length[A]
2.    key = A[j]
3.    i = j - 1
4.    while i > 0 and A[i] > key
5.        A[i + 1] = A[i]
6.        i = i - 1
7.    A[i + 1] = key

• 最坏情况下的时间复杂度为O(n^2)。
• 最好情况下，时间复杂度为O(n)。
• 平均情况下的时间复杂度为O(n^2)。

归并排序：

MERGE-SORT(A, p, r)
1. if p < r
2.    q = (p + r) / 2   // 计算中间位置
3.    MERGE-SORT(A, p, q)   // 递归地对左半部分进行排序
4.    MERGE-SORT(A, q+1, r)   // 递归地对右半部分进行排序
5.    MERGE(A, p, q, r)   // 合并左右两个已排序的子数组

MERGE(A, p, q, r)
1. n1 = q - p + 1   // 左子数组的长度
2. n2 = r - q   // 右子数组的长度
3. 创建临时数组 L[1...n1+1] 和 R[1...n2+1]
4. for i = 1 to n1
5.    L[i] = A[p + i - 1]   // 将左子数组复制到临时数组 L
6. for j = 1 to n2
7.    R[j] = A[q + j]   // 将右子数组复制到临时数组 R
8. 设置 L[n1+1] 和 R[n2+1] 为无穷大
9. i = 1
10. j = 1
11. for k = p to r
12.    if L[i] ≤ R[j]
13.        A[k] = L[i]
14.        i = i + 1
15.    else
16.        A[k] = R[j]
17.        j = j + 1

归并排序的时间复杂度为O(nlogn)，其中n是待排序数组的长度。归并排序是一种稳定的排序算法，对于任何输入数据都可以保证最坏情况下的时间复杂度为O(nlogn)。

第三章：函数的增长

O记号：渐近上界

Ω记号：渐近下界

Θ记号：渐近紧确界

第四章：分治策略

最大子数组问题：

1、暴力求解：时间复杂度为O(n^3)，其中n是数组的长度。

2、分治策略：最大子数组问题可以使用分治策略解决，通过将问题划分为更小的子问题来求解。具体步骤如下：

• 将数组划分为左右两个子数组，分别解决左右子数组的最大子数组问题。
• 跨越中点的最大子数组：从中点开始向左右两侧扩展，找到包含中点的最大子数组。
• 比较三个情况（左子数组的最大子数组、右子数组的最大子数组、跨越中点的最大子数组），选择和最大的子数组作为结果。

3、递归求解：分治策略是递归的，通过不断地将问题划分为更小的子问题，最终求解整个问题。递归的终止条件是子数组只有一个元素时，直接返回该元素作为最大子数组。

4、时间复杂度分析：使用分治策略求解最大子数组问题的时间复杂度为O(nlogn)，其中n是数组的长度。这是因为每次递归将问题的规模缩小一半，并且在每一层递归中的操作时间复杂度为O(n)。

用主方法求解递归式

用主方法（Master Theorem）是一种常用的求解递归式的方法，它可以给出递归算法的时间复杂度的上界。

主方法的一般形式如下：
T(n) = a * T(n/b) + f(n)

其中，T(n)表示问题规模为n时算法的执行时间，a表示递归产生的子问题的个数，n/b表示每个子问题的规模，f(n)表示除去递归调用之外剩余操作的执行时间。

主方法基于以下三种情况的假设，针对不同的情况，给出了递归算法的时间复杂度的上界：

使用主方法求解递归式时，我们需要确定递归式中的a、b和f(n)的值，然后根据上述三种情况中的哪一种情况符合，得出递归算法的时间复杂度的上界。

需要注意的是，主方法并不适用于所有类型的递归式，仅适用于符合上述三种情况的递归式。对于其他类型的递归式，可能需要使用其他方法进行求解。

第六章：堆排序

HEAPSORT(A)
    BUILD-MAX-HEAP(A)    // 构建最大堆
    for i = A.length downto 2
        exchange A[1] with A[i]    // 将最大值放到数组末尾
        A.heap-size = A.heap-size - 1
        MAX-HEAPIFY(A, 1)    // 对剩余元素进行最大堆的调整

具体过程如下：

1. BUILD-MAX-HEAP(A)：首先将待排序的数组A构建为一个最大堆。从数组的中间位置开始，向前遍历每个非叶子节点，对每个节点执行MAX-HEAPIFY操作，将其和其子树调整为最大堆。通过这个过程，整个数组A将满足最大堆的性质。

2. 排序过程：从数组的最后一个元素开始，逐步将最大堆的根节点（即最大值）与当前位置的元素进行交换。每次交换后，将堆的大小减1，并对交换后的根节点执行MAX-HEAPIFY操作，将其与其子树调整为最大堆。重复执行这个过程，直到堆的大小减为1。

BUILD-MAX-HEAP(A)：用于构建最大堆的辅助函数。

BUILD-MAX-HEAP(A)
    A.heap-size = A.length
    for i = floor(A.length/2) downto 1
        MAX-HEAPIFY(A, i)

MAX-HEAPIFY(A, i)：用于维护最大堆性质的辅助函数。

MAX-HEAPIFY(A, i)
    left = 2i    // 左子节点的索引
    right = 2i + 1    // 右子节点的索引
    largest = i    // 初始化最大值的索引为当前节点

    // 检查左子节点是否存在且大于当前节点的值
    if left ≤ A.heap-size and A[left] > A[i]
        largest = left

    // 检查右子节点是否存在且大于当前最大值的节点
    if right ≤ A.heap-size and A[right] > A[largest]
        largest = right

    // 如果最大值不等于当前节点，进行交换
    if largest ≠ i
        exchange A[i] with A[largest]

        // 对交换后的子节点递归调用 MAX-HEAPIFY，确保子树也满足最大堆的性质
        MAX-HEAPIFY(A, largest)

该算法从数组的中间位置开始，向前遍历每个非叶子节点，并对每个节点执行MAX-HEAPIFY操作，将其和其子树调整为最大堆。A.heap-size用于表示当前堆的大小。

堆排序的时间复杂度为O(nlogn)，其中n是待排序数组的大小。构建最大堆的过程的时间复杂度为O(n)，而每次交换和调整堆的操作的时间复杂度为O(logn)。

优先队列

第七章：快速排序

QUICKSORT(A, p, r)
    // 对数组 A[p...r] 进行快速排序
    if p < r
        q = PARTITION(A, p, r) // 将数组划分为两个子数组，并获取基准元素的位置
        QUICKSORT(A, p, q-1) // 对左子数组进行递归排序
        QUICKSORT(A, q+1, r) // 对右子数组进行递归排序

PARTITION(A, p, r)
    // 将数组 A[p...r] 划分为两个子数组，并返回基准元素的位置
    x = A[r] // 选择最后一个元素作为基准元素
    i = p - 1 // i 是小于等于基准元素的子数组的边界
    for j = p to r-1
        if A[j] <= x
            i = i + 1
            exchange A[i] with A[j] // 将小于等于基准元素的元素交换到左侧
    exchange A[i+1] with A[r] // 将基准元素放在正确的位置上
    return i + 1 // 返回基准元素的位置

快速排序的时间复杂度为平均情况下的 O(nlogn)，其中 n 是待排序数组的大小。它是一种原地排序算法，不需要额外的存储空间

第八章：线性时间排序

计数排序：

CountingSort(array, k):
    n = length(array)  // 获取数组长度
    count = new Array[k]  // 创建计数数组，长度为待排序元素的最大值加1
    output = new Array[n]  // 创建输出数组，用于存储排序结果

    // 初始化计数数组
    for i = 0 to k-1:
        count[i] = 0

    // 统计待排序元素的出现次数
    for j = 0 to n-1:
        count[array[j]] = count[array[j]] + 1

    // 计算每个元素的最终位置
    for i = 1 to k-1:
        count[i] = count[i] + count[i-1]

    // 将元素放入正确的位置
    for j = n-1 to 0:
        output[count[array[j]] - 1] = array[j]
        count[array[j]] = count[array[j]] - 1

    return output

基数排序：

桶排序：

BUCKET-SORT(A)
1. n = length[A]
2. 创建一个空的数组 B[0..n-1]
3. 对数组 A 中的每个元素 A[i] 进行循环
    a. 创建一个空的链表 B[i]
4. 对数组 A 中的每个元素 A[i] 进行循环
    a. 将元素 A[i] 插入链表 B[⌊nA[i]⌋] 中
5. 对数组 B 中的每个链表 B[i] 进行循环
    a. 对链表 B[i] 进行插入排序
6. 将链表 B[0]，B[1]，...，B[n-1] 依次连接起来形成一个新的链表 C
7. 返回链表 C 中的所有元素作为排序结果

第九章：中位数和顺序统计量

最小值和最大值：

为了找到最小值，必须要做 n - 1 次比较。同时找到最小值和最大值，至多是 3|n/2| 向下取整次 比较。

期望为线性时间的选择算法：

RANDOMIZED-SELECT(A, p, r, i)
1. 如果 p = r，则返回 A[p] 作为第i小的元素
2. q = RANDOMIZED-PARTITION(A, p, r)   // 将数组 A[p..r] 划分为两个子数组，返回主元的位置 q
3. k = q - p + 1   // 计算主元在当前划分中的相对位置
4. 如果 i = k，则返回 A[q] 作为第i小的元素
5. 如果 i < k，则递归调用 RANDOMIZED-SELECT(A, p, q-1, i) 在左侧子数组中寻找第i小的元素
6. 否则，在右侧子数组中寻找第 (i - k) 小的元素，即调用 RANDOMIZED-SELECT(A, q+1, r, i-k)

第十三章：红黑树

1. 红黑树定义：红黑树是一种具有以下性质的二叉搜索树：
   • 每个节点都有一个颜色，红色或黑色。
   • 根节点是黑色的。
   • 所有叶子节点（NIL节点）都是黑色的。
   • 如果一个节点是红色的，则其两个子节点都是黑色的。
   • 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点（即具有相同的黑色高度）。

插入：

RB-INSERT(T, z)
1. y = NIL   // 初始化一个空节点作为插入节点的父节点
2. x = T.root   // 从根节点开始向下搜索
3. while x ≠ NIL   // 在树中找到适当的位置插入节点
4.    do y = x
5.       if z.key < x.key
6.          then x = x.left
7.          else x = x.right
8. z.p = y   // 将插入节点的父节点指向 y
9. if y = NIL   // 如果 y 为空，说明插入的是根节点
10.    then T.root = z
11.    else if z.key < y.key   // 将 z 插入到正确的位置
12.            then y.left = z
13.            else y.right = z
14. z.left = NIL   // 初始化插入节点的左子节点为空
15. z.right = NIL   // 初始化插入节点的右子节点为空
16. z.color = RED   // 新插入的节点为红色
17. RB-INSERT-FIXUP(T, z)   // 调整红黑树以维持平衡性

• 步骤1-2：初始化 y 为 NIL（表示空节点）和 x 为根节点，用于搜索插入位置。
• 步骤3-7：通过比较节点的键值，向下搜索找到适当的插入位置。如果待插入节点的键值小于当前节点的键值，继续向左子树搜索；否则，继续向右子树搜索。
• 步骤8：将插入节点的父节点指针 z.p 指向找到的位置 y。
• 步骤9-13：根据 y 的值来确定 z 的插入位置。如果 y 是 NIL，表示插入的是根节点，将根节点指向 z。否则，根据 z 的键值与 y 的键值比较结果，决定将 z 作为 y 的左子节点还是右子节点。
• 步骤14-15：将插入节点的左子节点和右子节点初始化为空。
• 步骤16：将新插入的节点 z 的颜色设为红色。
• 步骤17：调用 RB-INSERT-FIXUP 过程，以修复插入后可能破坏红黑树性质的问题，以保持红黑树的平衡性。

第十五章：动态规划

钢条切割：

CUT-ROD(p, n)
1. if n == 0   // 钢条长度为 0，返回收益 0
2.    then return 0
3. q = -∞   // 初始化最大收益为负无穷
4. for i = 1 to n   // 尝试不同的切割位置
5.    do q = max(q, p[i] + CUT-ROD(p, n - i))   // 递归调用，计算最大收益
6. return q   // 返回最大收益

15.2 矩阵链乘法

1. 定义子问题： 首先，我们定义子问题来解决矩阵相乘的分割点。对于矩阵链 Aᵢ, Aᵢ₊₁, …, Aⱼ，我们将其划分为两个子链 Aᵢ, Aᵢ₊₁, …, Aₖ 和 Aₖ₊₁, Aₖ₊₂, …, Aⱼ，其中 i ≤ k < j。

2. 确定状态： 定义子问题的状态为矩阵链的起始位置 i 和结束位置 j。

3. 定义状态转移方程： 我们使用 m[i, j] 表示计算矩阵链 Aᵢ, Aᵢ₊₁, …, Aⱼ 的最小乘法次数。那么，我们可以得到以下状态转移方程： m[i, j] = min {m[i, k] + m[k+1, j] + pᵢ×pₖ₊₁×pⱼ}，其中 i ≤ k < j。

   这个状态转移方程的意思是，对于每个分割点 k，我们计算分割点前半部分和分割点后半部分的乘法次数，并将它们加起来，再加上当前分割点的乘法次数 pᵢ×pₖ₊₁×pⱼ。然后，我们在所有可能的分割点 k 中选择最小的乘法次数作为 m[i, j] 的值。

4. 确定边界条件： 最小子问题的解为单个矩阵的乘法次数为 0，即 m[i, i] = 0（对于所有 i）。

5. 计算最优解： 使用自底向上的迭代方法，从小规模的问题开始计算，逐步扩展到整个矩阵链。我们通过填充一个表格来保存中间结果和最小乘法次数。首先计算单个矩阵的乘法次数为 0，然后按照从小到大的顺序计算所有子问题的最小乘法次数。最终，我们将获得整个矩阵链的最小乘法次数 m[1, n]

15.3 动态规划原理

动态规划的原理和基本步骤：

1. 定义最优子结构： 动态规划的第一步是定义问题的最优子结构。最优子结构是指一个问题的最优解包含了其子问题的最优解。也就是说，如果我们知道了子问题的最优解，就可以通过组合子问题的最优解来得到原问题的最优解。
2. 刻画子问题的重叠性质： 动态规划的第二步是刻画子问题的重叠性质。子问题的重叠性质是指在解决原问题时，子问题之间存在重复计算的情况。如果我们能够发现子问题之间存在重叠，那么就可以使用记忆化或者自底向上的方法，避免重复计算，提高算法的效率。
3. 构建状态转移方程： 动态规划的核心是构建状态转移方程。状态转移方程描述了子问题之间的关系，并且用于推导原问题的最优解。通过定义状态变量和状态转移方程，可以将问题的求解过程转化为一个递推的过程。在状态转移方程中，通常使用递归的方式表达子问题之间的依赖关系。
4. 确定边界条件： 边界条件是指最小规模子问题的解。在动态规划中，我们通常需要确定最小子问题的解，这些解是无法再继续分解的，而是直接给出的。边界条件是递推过程的终止条件，也是问题求解的起点。
5. 通过递推计算最优解： 最后一步是通过递推的方式计算原问题的最优解。我们可以根据状态转移方程，从边界条件开始，逐步计算出子问题的最优解，直到计算得到原问题的最优解。

第十六章：贪心算法

16.1 活动选择问题

问题：
假设有一个会议室和一组预定了开始时间和结束时间的活动。现在要求你设计一个算法，选择出最大可能的相互兼容的活动子集，使得可以同时进行最多的活动。请使用贪心算法解决这个问题，并给出算法的思路和伪代码。

答案：
算法思路：

1. 对活动按照结束时间进行排序。
2. 选择第一个活动（结束时间最早的活动）加入活动子集。
3. 依次考虑后续的活动，如果它的开始时间晚于或等于前一个已选活动的结束时间，那么将其加入活动子集。
4. 重复上一步骤，直到考虑完所有的活动。
5. 返回活动子集作为最大相互兼容的活动子集。

伪代码：

GreedyActivitySelection(start, end):
    n = length(start)
    activities = []
    activities.append(0)  // 加入第一个活动
    k = 0
    
    for i = 1 to n-1:
        if start[i] >= end[k]:
            activities.append(i)
            k = i
    
    return activities

这个算法的时间复杂度为 O(n log n)，其中 n 是活动的个数。通过这个贪心算法，可以选择出最大相互兼容的活动子集，使得可以同时进行最多的活动。

16.2 贪心算法原理

1. 贪心选择性质：
   贪心算法的核心是贪心选择性质。贪心选择性质指的是，在求解问题的最优解时，每一步都选择当前看起来最优的解决方案，而不考虑之前的选择或者将来的影响。这种局部最优选择希望最终能够导致全局最优解。贪心选择性质要求每一步的选择必须是局部最优的，但并不要求最终的解决方案是全局最优的。
2. 最优子结构性质：
   贪心算法通常利用问题的最优子结构性质来实现。最优子结构性质指的是问题的最优解可以通过子问题的最优解构建而来。换句话说，问题的最优解具有一种递归的结构，通过找到子问题的最优解并组合起来，可以得到原问题的最优解。贪心算法通常通过反证法来证明问题具有最优子结构性质。
3. 贪心算法的设计：
   贪心算法的设计过程可以分为以下步骤：
   • 理解问题的特性：首先要充分理解问题的特性，包括问题的约束条件和优化目标。
   • 确定贪心选择策略：根据问题的特性，确定一种贪心选择策略，选择当前看起来最优的解决方案。
   • 证明贪心选择性质：通过证明贪心选择策略的局部最优性，即每一步的选择都是当前最优的，来推导出贪心选择策略的整体最优性。
   • 设计贪心算法：基于贪心选择策略，设计出贪心算法的具体实现。
   • 分析算法的正确性和效率：对贪心算法进行正确性和效率的分析，确保算法能够得到正确的解，并且具有高效的运行时间。

问题：
考虑一个背包问题，背包的容量为W，有n个物品，每个物品有自己的重量和价值。现在要设计一个算法，选择出最优的物品组合放入背包，使得背包中物品的总价值最大化。使用贪心算法解决该问题，并给出算法的思路和伪代码。

答案：
算法思路：

1. 计算每个物品的单位价值（价值与重量的比值）。
2. 按照单位价值从高到低对物品进行排序。
3. 初始化背包的剩余容量为W，总价值为0。
4. 依次考虑每个物品，如果当前物品的重量小于等于背包的剩余容量，则将其放入背包，并更新背包的剩余容量和总价值。
5. 重复上述步骤，直到背包无法容纳更多物品或所有物品都被考虑完。
6. 返回背包中物品的总价值作为最优解。

伪代码：

GreedyKnapsack(weights, values, W):
    n = length(weights)
    value_per_unit = []
    for i = 0 to n-1:
        value_per_unit[i] = values[i] / weights[i]
    
    sort(value_per_unit, weights, values) // 按单位价值排序
    
    total_value = 0
    remaining_capacity = W
    
    for i = 0 to n-1:
        if weights[i] <= remaining_capacity:
            total_value = total_value + values[i]
            remaining_capacity = remaining_capacity - weights[i]
    
    return total_value

这个算法的时间复杂度为 O(n log n)，其中 n 是物品的个数。通过这个贪心算法，可以选择出最优的物品组合放入背包，使得背包中物品的总价值最大化。然而，请注意贪心算法在0-1背包问题中不一定能得到最优解的情况。

16.3 赫夫曼编码

1. 问题描述：
   赫夫曼编码用于将给定的文本数据进行压缩，以减少存储空间和传输带宽。赫夫曼编码的核心思想是将出现频率较高的字符用较短的编码表示，而将出现频率较低的字符用较长的编码表示。

2. 赫夫曼树：
   赫夫曼编码的基础是赫夫曼树。赫夫曼树是一种特殊的二叉树，其中每个叶子节点表示一个字符，而每个非叶子节点表示一个字符出现的频率。赫夫曼树的构建过程通常使用优先队列（最小堆）来选择频率最低的两个节点，并将它们合并为一个新节点，直到只剩下一个根节点为止。

3. 赫夫曼编码的构建：
   构建赫夫曼编码的过程可以分为以下步骤：

   • 统计字符出现的频率。
   • 根据字符频率构建赫夫曼树。
   • 通过遍历赫夫曼树，给每个字符分配唯一的二进制编码。通常，左子树表示编码中的0，右子树表示编码中的1。
   • 将文本数据根据字符的赫夫曼编码进行替换，实现压缩。

4. 赫夫曼编码的性质：

   • 前缀码：赫夫曼编码是一种前缀码，即没有任何一个字符的编码是另一个字符编码的前缀。
   • 最优性：赫夫曼编码是最优的，即它可以达到最小的编码长度。

5. 赫夫曼编码的应用：
   赫夫曼编码在数据压缩领域广泛应用，尤其在文本文件压缩中效果显著。通过使用赫夫曼编码，可以大大减小文件的大小，节省存储空间和传输带宽。

第二十二章：基本的图算法

BFS——广度优先搜索

1. 算法原理：
   • BFS使用队列数据结构来维护待访问的节点。起始时，将起始节点放入队列。
   • 从队列中取出第一个节点，并将其标记为已访问。
   • 遍历该节点的所有邻接节点，将未被访问过的邻接节点放入队列中。
   • 重复上述过程，直到队列为空，即所有可达节点都被访问。
2. 算法步骤：
   • 初始化一个空队列和一个标记数组，用于记录节点的访问状态。
   • 将起始节点放入队列，并将其标记为已访问。
   • 从队列中取出节点，并遍历其所有邻接节点。
   • 对于每个未被访问的邻接节点，将其放入队列，并将其标记为已访问。
   • 重复以上两个步骤，直到队列为空。
3. 时间复杂度：
   • 对于具有|V|个顶点和|E|条边的图，BFS的时间复杂度为O(|V| + |E|)，其中|V|表示顶点数，|E|表示边数

BFS(G, s):
1. for each vertex u ∈ G.V - {
    s}  // 初始化所有顶点的状态
2.    u.color = WHITE            // WHITE表示未访问
3.    u.d = ∞                    // 从起始顶点s到顶点u的最短距离
4.    u.π = NIL                  // 从起始顶点s到顶点u的前驱节点
5. s.color = GRAY               // 起始顶点s标记为灰色，表示已访问但未完成探索
6. s.d = 0                      // 起始顶点s到自身的最短距离为0
7. s.π = NIL                    // 起始顶点s没有前驱节点
8. Q = ∅                       // 创建一个空队列Q
9. ENQUEUE(Q, s)               // 将起始顶点s入队
10. while Q ≠ ∅                // 队列不为空时继续循环
11.    u = DEQUEUE(Q)          // 取出队列的头部节点u
12.    for each v ∈ G.Adj[u]    // 遍历u的邻接节点v
13.       if v.color == WHITE   // 如果邻接节点v未被访问
14.          v.color = GRAY    // 标记为灰色，表示已访问但未完成探索
15.          v.d = u.d + 1     // 更新起始顶点s到顶点v的最短距离
16.          v.π = u           // 设置顶点v的前驱节点为u
17.          ENQUEUE(Q, v)    // 将顶点v入队
18.    u.color = BLACK         // 当u的邻接节点都被探索完成后，将u标记为黑色，表示已完成探索

DFS——深度优先搜索

1. 算法原理：
   • DFS使用栈数据结构来维护待访问的节点。起始时，将起始节点放入栈。
   • 从栈中取出顶部节点，并将其标记为已访问。
   • 遍历该节点的邻接节点，如果邻接节点未被访问，则将其放入栈中。
   • 重复上述过程，直到栈为空，即所有可达节点都被访问。
2. 算法步骤：
   • 初始化一个空栈和一个标记数组，用于记录节点的访问状态。
   • 将起始节点放入栈，并将其标记为已访问。
   • 从栈中取出节点，并遍历其所有邻接节点。
   • 对于每个未被访问的邻接节点，将其放入栈，并将其标记为已访问。
   • 重复以上两个步骤，直到栈为空。
3. 时间复杂度：
   • 对于具有|V|个顶点和|E|条边的图，DFS的时间复杂度为O(|V| + |E|)，其中|V|表示顶点数，|E|表示边数。

DFS(G):
1. for each vertex u ∈ G.V  // 初始化所有顶点的状态
2.    u.color = WHITE      // WHITE表示未访问
3.    u.π = NIL            // 从起始顶点s到顶点u的前驱节点
4. time = 0               // 初始化时间变量
5. for each vertex u ∈ G.V  // 遍历所有顶点
6.    if u.color == WHITE  // 如果顶点u未被访问
7.       DFS-VISIT(u)      // 调用DFS-VISIT进行深度优先探索

DFS-VISIT(u):
1. time = time + 1         // 增加时间变量，表示顶点u被发现的时间
2. u.d = time              // 记录顶点u的发现时间
3. u.color = GRAY          // 标记顶点u为灰色，表示正在访问中
4. for each vertex v ∈ G.Adj[u]  // 遍历顶点u的邻接节点v
5.    if v.color == WHITE       // 如果邻接节点v未被访问
6.       v.π = u               // 设置顶点v的前驱节点为u
7.       DFS-VISIT(v)          // 递归调用DFS-VISIT对顶点v进行深度优先探索
8. u.color = BLACK         // 当u的所有邻接节点都被探索完成后，将u标记为黑色
9. time = time + 1         // 增加时间变量，表示顶点u的探索完成时间
10. u.f = time             // 记录顶点u的探索完成时间

22.4 拓扑排序

拓扑排序是一种对有向无环图（DAG）进行排序的算法，它将图中的节点按照一定的顺序进行排列，使得所有的有向边从排在前面的节点指向排在后面的节点。

1. 算法原理：
   • 拓扑排序算法利用有向无环图的拓扑结构，通过选择没有前驱节点的节点，逐层进行排序。
   • 首先找到没有前驱节点的节点，将其加入结果序列。
   • 删除该节点及其所有出边，更新剩余节点的前驱节点集合。
   • 重复上述过程，直到所有节点都被处理。
2. 应用：
   • 拓扑排序常用于任务调度、依赖关系分析等场景，可以确定任务的执行顺序或找出各个任务之间的依赖关系。
   • 如果有向图中存在环路，则无法进行拓扑排序，因为无法找到没有前驱节点的节点。
3. 时间复杂度：
   • 对于具有|V|个顶点和|E|条边的有向图，拓扑排序的时间复杂度为O(|V| + |E|)，其中|V|表示顶点数，|E|表示边数。

拓扑排序是一种非常有用的算法，通过确定节点之间的依赖关系，可以有效地解决任务调度等问题。它要求图是有向无环图，因此在使用拓扑排序之前需要先判断图是否是有向无环图。如果是有向无环图，拓扑排序可以给出一种满足依赖关系的节点排序顺序。

第二十三章：最小生成树

这一章介绍了解决连接图中所有顶点的最小生成树问题的算法。下面是对该章节的概述：

1. 最小生成树问题：
   • 在一个连通无向图中，最小生成树是一个生成树，它的权重和最小。
   • 生成树是原图的一个子图，它包含了图中的所有顶点，并且是一个树结构，即没有环路。
2. 算法原理：
   • 最小生成树算法主要有两种经典算法：Kruskal算法和Prim算法。
   • Kruskal算法基于贪心策略，按照边的权重从小到大逐步选择边，同时保证所选边不会形成环路，直到选择了足够的边构成最小生成树。
   • Prim算法也是一种贪心算法，从一个起始顶点开始，逐步扩展最小生成树，每次选择与当前树相连的权重最小的边对应的顶点加入到树中。
3. Kruskal算法步骤：
   • 将图中的边按照权重从小到大进行排序。
   • 初始化一个空的最小生成树集合。
   • 逐个考虑每条边，如果加入该边不会形成环路，则将其加入最小生成树集合。
   • 重复上述步骤，直到最小生成树集合中包含了所有顶点。
4. Prim算法步骤：
   • 选择一个起始顶点，将其标记为已访问。
   • 初始化一个空的最小生成树集合和一个优先队列（最小堆），用于保存与当前树相连的边的权重。
   • 将起始顶点的所有邻接边加入优先队列。
   • 重复以下步骤，直到最小生成树集合包含了所有顶点：
     • 从优先队列中取出权重最小的边对应的顶点v，如果v未被访问，则将其加入最小生成树集合，并将v标记为已访问。
     • 将顶点v的所有邻接边中，未被访问的边加入优先队列。

问题：
给定下面的无向图和边的权重，使用Prim算法找出最小生成树，并计算最小生成树的总权重。

图示：

      4     3
   (0)--(1)--(2)
   |   / \   |
  6| 8/   \5 |7
   | /     \ |
   (3)----- (4)
        2

答案：
最小生成树的边集合为：{(0, 1), (1, 2), (2, 4), (3, 0)}
最小生成树的总权重为：14

解释：

1. 从顶点0开始，将其标记为已访问。
2. 将边(0, 1)加入最小生成树集合，权重为4。
3. 将边(1, 2)加入最小生成树集合，权重为3。
4. 将边(2, 4)加入最小生成树集合，权重为7。
5. 将边(3, 0)加入最小生成树集合，权重为6。
6. 最小生成树的总权重为4 + 3 + 7 + 6 = 20。

注意：在Prim算法中，起始顶点的选择可能会影响最终的最小生成树，但最小生成树的总权重是唯一的。在本题中，起始顶点为0，可以得到上述的最小生成树和总权重。

题目：使用Kruskal算法和Prim算法分别求解以下无向带权图的最小生成树。

给定以下无向带权图（使用邻接矩阵表示）：

       A   B   C   D   E
   ----------------------
A |  0   4   0   0   0
B |  4   0   7   8   0
C |  0   7   0   9   14
D |  0   8   9   0   10
E |  0   0   14  10  0

a) 使用Kruskal算法求解最小生成树，并给出最小生成树的边集合和总权重。

b) 使用Prim算法求解最小生成树，并给出最小生成树的边集合和总权重。

答案：

a) Kruskal算法求解最小生成树的过程：

• 边集合：{(A, B), (C, D), (D, E)}
• 总权重：4 + 9 + 10 = 23

b) Prim算法求解最小生成树的过程：

• 边集合：{(A, B), (B, C), (B, D), (D, E)}
• 总权重：4 + 7 + 8 + 10 = 29

注意：这是一个示例题目，实际的最小生成树问题可能会更复杂，需要根据具体图的情况进行求解。

第二十四章：单源最短路径

这一章介绍了解决从一个源节点到其他所有节点的最短路径问题的算法。

1. 单源最短路径问题：
   • 给定一个带权有向图和一个源节点，单源最短路径问题是求解从源节点到图中所有其他节点的最短路径的问题。
   • 最短路径是指路径上的边权重之和最小的路径。
2. 算法原理：
   • 最短路径算法主要有两种经典算法：Dijkstra算法和Bellman-Ford算法。
   • Dijkstra算法适用于边权重为非负数的图，它通过贪心策略逐步扩展最短路径集合，选择当前路径权重最小的节点。
   • Bellman-Ford算法适用于边权重可以为负数的图，它通过对边进行松弛操作来逐步逼近最短路径。
3. Dijkstra算法步骤：
   • 初始化一个距离数组，用于保存源节点到每个节点的最短距离，初始时源节点的距离为0，其他节点的距离为正无穷。
   • 初始化一个空的最短路径集合，用于保存已确定最短路径的节点。
   • 重复以下步骤，直到最短路径集合包含了所有节点：
     • 从未确定最短路径的节点中选择距离最小的节点u。
     • 将节点u加入最短路径集合。
     • 对于节点u的所有邻接节点v，如果通过节点u可以得到比当前距离更短的路径，则更新节点v的距离。
   • 返回距离数组作为最短路径的结果。
4. 应用：
   • 单源最短路径算法可以应用于导航系统、网络路由、资源调度等场景，用于确定最佳路径或最短时间的路线。

24.3 Dijkstra算法

Dijkstra(G, w, s):
    Initialize-Single-Source(G, s)  // 初始化节点距离和前驱节点
    S = {
    }  // 已确定最短路径的节点集合
    Q = G.V  // 所有节点的集合
    
    while Q is not empty:
        u = Extract-Min(Q)  // 从Q中选择距离最小的节点u
        S = S U {
    u}  // 将节点u加入已确定最短路径的集合
        
        for each v in G.Adj[u]:  // 遍历u的邻接节点v
            Relax(u, v, w)  // 松弛操作，更新节点v的最短距离
    
    return dist[]  // 返回最短距离数组

Relax(u, v, w):
    if dist[v] > dist[u] + w(u, v):  // 如果通过节点u可以得到更短的路径
        dist[v] = dist[u] + w(u, v)  // 更新节点v的最短距离
        prev[v] = u  // 更新节点v的前驱节点

Initialize-Single-Source(G, s):
    for each v in G.V:
        dist[v] = infinity  // 初始化节点v的距离为正无穷大
        prev[v] = NIL  // 初始化节点v的前驱节点为空
    dist[s] = 0  // 源节点的距离为0

——————————————送上四道经典LeetCode题

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

// class Solution {
    
//     public int[] twoSum(int[] nums, int target) {
    
//         int len = nums.length;
//         for(int i = 0; i < len; i++){
    
//             for(int j = i + 1; j < len; j++){
    
//                 if(nums[i] + nums[j] == target){
    
//                     return new int[]{i,j};
//                 }
//             }
//         }
//         return new int[0];
//     }
// }

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        int len = nums.length;
        Map<Integer, Integer> hashtable = new HashMap<Integer,Integer>();
        for(int i = 0; i < len; i++){
    

            if(hashtable.containsKey(target - nums[i])){
      //i为0 此时key为2，找有没有7，7对应的val为hashtable.get(7);
                return new int[]{
    i , hashtable.get(target - nums[i])};
            }

            hashtable.put(nums[i],i);   //key 2,val 0;;; key 7,val 1;;;  key 11,val 2......

        }
        return new int[0];
    }
}

55. 跳跃游戏（贪心）

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

class Solution {
    
    public boolean canJump(int[] nums) {
    
        int len = nums.length;
        int most = 0;  //最大位置的下表
        for(int i = 0; i < len; i++){
    
            if(i <= most){
      //此时的位置在most位置之前，要替换更新most
                most = Math.max(most , i + nums[i]);  //此时的i跳num[i]后 是否比most大
                if(most >= len-1){
      //只要当 能跳到的最大位置（most） 到达/超过 最后一个位置的下标 就ture
                    return true;
                }
            }
        }
        //遍历完了 还不能超过最后位置
        return false;
    }
}

378. 有序矩阵中第 K 小的元素（分治）

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

暴力解：

class Solution {
    
    public int kthSmallest(int[][] matrix, int k) {
    
        int n = matrix[0].length;
        int[] sor = new int[n * n];
        int index = 0;

        //把二维数组每一个放入一维数组
        for(int[] row : matrix){
      //遍历二维数组每一行
            for(int num : row){
      //遍历每一行的每一个
                sor[index] = num;
                index++;
            }
        }

        //重新排序
        Arrays.sort(sor);

        return sor[k-1];  //返回第k小的元素
    }
}

416. 分割等和子集（动态规划DP）

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
    
   public boolean canPartition(int[] nums) {
    
       int len = nums.length;

       //算出总和，为奇数，false
       int sum = 0;
       for(int n : nums){
    
           sum += n;
       }
       if(sum % 2 == 1) return false;

       //创建二维数组，0-1 背包问题。行：数组索引，列：容量  
       int target = sum/2;
       boolean[][] dp = new boolean[len] [target + 1];

       //先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满
       if(nums[0] <= target){
    
           dp [0] [nums[0]] = true;
       }

       //再填后面几行
       for(int i = 1; i < len; i++){
    
           for(int j = 0; j <= target; j++){
    
               //从上一行把结果抄下来，再修正
               dp[i][j] = dp[i-1][j];

               if(nums[i] == j){
    
                   dp[i][j] = true;
                   continue;
               }

               if(nums[i] < j){
    
                   dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
               }
           }
       }

       return dp[len-1][target];
   }
}