黑链接：算法入门笔记【超全版本】（排序、树、图论、字符串）

算法 笔记

参考书： 算法（第四版）

优秀的算法因为能解决实际问题而变得尤为重要

高效算法的代码也可以很简单

理解某个实现的性能特点是一项有趣而令人满足的挑战

在解决同一个问题的多种算法之间进行选择时，科学方法时一种重要的工具

迭代式改进能让算法的效率越来越高

---

1. 排序

三大实际意义

• 对排序算法的分析将有助于全面理解书中比较算法性能的方法
• 类似的技术也能有效解决其他类型的问题
• 排序算法常常是我们解决其他问题的第一步

1.1. 前言

1.1.1 模板

/**排序算法模板**/public class Example {public static void sort(Comparable[] a) {//具体算法见本书}private static boolean less(Comparable v, Comparable w) {return v.compareTo(w) < 0;}private static void exch(Comparable[] a, int i, int j) {Comparable t = a[i];a[i] = a[j];a[j] = t;}private static void show(Comparable[] a) {for(int i=0; i<a.length; i++)StdOut.print(a[i] + " ");StdOut.println();}public static boolean isSorted(Comparable[] a) {for(int i=1; i<a.length; i++) {if(less(a[i], a[i-1]))//默认升序排列return false;}return true;}public static void main(String[] args) {String[] a = null;sort(a);assert isSorted(a);//断言show(a);}}

在研究排序算法时，需要比较的是比较和交换的数量。对于不交换元素的算法，比较访问数组的次数

1.1.2 简述

本节接下来即将研究经典的几种排序算法：

选择排序

插入排序

希尔排序

归并排序

快速排序

堆排序

1.2 选择排序

1.2.1 简述

选择排序的基本思想是：

在当前的轮数 i i i 中，找到从索引 i + 1 i+1 i+1到末尾的元素的最小值，并于 a [ i ] a[i] a[i] 比较，若小于当前元素则交换

1.2.2 代码

public static void sort(Comparable[] a) {int N = a.length;for(int i=0; i<N; i++) { //升序排列int min = i;for(int j=i+1; j<N; j++) {if(less(a[j], a[min]))//每次比较两个元素大小，找到当前的最小元素min = j;}exch(a, i, min);}}

选择排序的轨迹

1.2.3 复杂度分析

显然可以看出，最坏的情况总共需要 N N N 次交换， 以及 ( N − 1 ) + ( N − 2 ) + ( N − 3 ) + . . . + 2 + 1 = n 2 2 (N-1)+(N-2)+(N-3)+...+2+1 = \frac {n^2} {2} (N−1)+(N−2)+(N−3)+...+2+1=2n2​ 次的比较

时间复杂度为 O ( n 2 ) O(n^2) O(n2)

1.3 插入排序

1.3.1 简述

相当于我们在玩扑克牌时理牌过程的模拟，将第j张牌移动到前面合适的位置

1.3.2 代码

public static void sort(Comparable[] a) {int N = a.length;for (int i = 1; i < N; i++) {for (int j = i; j > 0 && less(a[i], a[j - 1]); j--) { // 将a[j]置入前面序列中合适的位置exch(a, j, j - 1);}}}

插入排序的轨迹

1.3.3 复杂度分析

首先，我们先思考一下最好情况的情形：所有对象都已升序，这时便不需要交换，仅仅比较 N − 1 N-1 N−1次

接下来我们再看最坏情况下的分析：当所有对象都是逆序排列时，显然，需要 N 2 2 \frac {N^2} {2} 2N2​ 次比较和 N 2 2 \frac {N^2} {2} 2N2​ 次交换

时间复杂度 O ( n 2 ) O(n^2) O(n2)

1.3.4 进一步思考

我们现在考虑更加一般的情况：部分有序的数组

下面是几种典型的部分有序的数组

• 数组中每个元素离它最终的位置不远
• 一个有序数组接一个小数组
• 数组中只有几个元素位置不对

插入排序对这样的数组很有效，选择排序则相反

1.3.5 插入排序和选择排序的比较

根据可视化的轨迹图，我们可以发现：

• 插入排序不会访问索引右侧的元素
• 而选择排序不会访问索引左侧的元素

两个算法的时间复杂度均为 O ( n 2 ) O(n^2) O(n2)，虽然两者都是平方级别的，但还是有所差异的

在本书1980年第一版完成之时，插入排序就比选择排序快一倍， 现在仍是这样

1.4 希尔排序

1.4.1 简述

希尔排序是基于插入排序的快速的排序算法

可以看成是对插入排序的优化

由于对于大规模乱序的数组而言，插入排序的速度很慢，因为总是需要将相邻的两个元素交换，如果最小的元素在数组的

最右端，那么就需要N-1次移动才能慢慢将它移到正确的位置

1.4.2 代码

public static void sort(Comparable[] a) {int N = a.length;int h = 1; // h大小的子数组进行排序,优化了插入排序中最小值在最右端要一次一次移动带来的高开销while (h < N / 3)h = h * 3 + 1;while (h >= 1) {for (int i = h; i < N; i++) {for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)exch(a, j, j - h);}h /= 3;}}

希尔排序的轨迹

1.4.3 分析

贯穿本书的一个重要理念：

通过提升速度来解决其他方式无法解决的问题是研究算法的设计和性能的主要原因之一

尽管希尔排序在数学上对于平均次数的分析比较复杂，但我们已经知道它已经突破了前两个算法的平方级别

有经验的程序员会使用希尔排序，它对于中等规模数组的运行时间是可以接受的，它的代码量很小，且不需要额外的内存空间

如果你要解决一个排序问题而有没有系统排序函数可以用，不妨先用希尔排序，然后再考虑使用其他更加复杂的排序算法

1.5 归并排序

归并排序是一种简单的递归排序算法：

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果合并起来

你将会看到，归并排序吸引人的性质在于时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，但主要的缺点是需要的额外空间和数组规模 n n n成正比

1.5.1 原地归并的抽象方法

我们知道，当用归并对大数组进行排序的时候，需要很多次归并，因此每次归并时创建一个新的数组会带来一些问题

我们更希望用一种原地归并的方法，能够在数组中移动而无需额外的空间，乍一看很容易，但实际上却是非常复杂的

//原地归并的抽象方法public static void merge(Comparable[] a, int lo, int mid, int hi){ //将a[lo....mid]和a[mid+1.....hi]归并 int i=lo; int j=mid+1; for(int k=lo; k<=hi; k++){//a[lo....hi]复制到辅助数组aux[lo.....hi] aux[k] = a[k]; } for(int k=lo; k<=hi; k++){ if(i > mid)a[k] = aux[j++];//左半边用完，右半边元素依次放入 else if(j > hi)a[k] = aux[i++];//右半边用完，左半边元素依次放入 else if(less(aux[i], aux[j]))a[k] = aux[i++];//放入较小元素 else a[k] = aux[j++]; }}

1.5.2 自顶向下的归并排序

基于原地归并的抽象方法，实现了另一种递归归并，这也是分治思想的一个典型例子

分治算法

将问题划分成较小规模，利用小问题解决初始问题

假设一个递归算法把一个规模为 n n n的问题分成 a a a个子问题，其中每个子问题的规模为 n b \frac {n}{b} bn​（为简单起见，假设b是n的倍数）。此外，假设把子问题的解组合成原来问题的算法处理需要总量为 g ( n ) g(n) g(n)的额外运算

那么，如果 f ( n ) f(n) f(n)表示求解规模为n的问题需要的运算数，则满足 f f f递推关系式

​ f ( n ) = a f ( n b ) + g ( n ) f(n) = af(\frac {n}{b}) + g(n) f(n)=af(bn​)+g(n)

这就叫做分治递推关系

//自顶向下public static void sort(Comparable[] a) {aux = new Comparable[a.length];sort(a, 0, a.length - 1);}public static void sort(Comparable[] a, int lo, int hi) {int mid = (lo + hi) / 2;if (lo < hi) {sort(a, lo, mid); // 左半边排序sort(a, mid + 1, hi); // 右半边排序merge(a, lo, mid, hi); // 归并(见2.5.1代码)}}

1.5.3 调用轨迹

要理解归并排序就要仔细研究该方法的调用情况，例如输入为

"m" "e" "r" "g" "e" "s" "o" "r" "t"

加入调试语句后，我们通过控制台打印出来的调用轨迹

左半部份排序：

调用了sort(a, 0,15)
调用了sort(a, 0,7)
调用了sort(a, 0,3)
调用了sort(a, 0,1)
调用了merge(a, 0,0,1)
调用了sort(a, 2,3)
调用了merge(a, 2,2,3)
调用了merge(a, 0,1,3)
调用了sort(a, 4,7)
调用了sort(a, 4,5)
调用了merge(a, 4,4,5)
调用了sort(a, 6,7)
调用了merge(a, 6,6,7)
调用了merge(a, 4,5,7)
调用了merge(a, 0,3,7)

右半部分排序：

调用了sort(a, 8,15)
调用了sort(a, 8,11)
调用了sort(a, 8,9)
调用了merge(a, 8,8,9)
调用了sort(a, 10,11)
调用了merge(a, 10,10,11)
调用了merge(a, 8,9,11)
调用了sort(a, 12,15)
调用了sort(a, 12,13)
调用了merge(a, 12,12,13)
调用了sort(a, 14,15)
调用了merge(a, 14,14,15)
调用了merge(a, 12,13,15)
调用了merge(a, 8,11,15)
调用了merge(a, 0,7,15)

另外，我们可以通过树结构图来理解

1.5.4 自底向上的归并排序

现在，我们换一种思路——先归并小数组，然后再成对归并已得到的子数组，如此这般，我们将整个数组调整到一起

首先是归并两个大小为1的数组，然后再归并两个大小为2的，然后是大小为4的数组，……

有可能数组的总大小并不是2的幂次，但对于 m e r g e （ ） merge（） merge（）函数来说，这并不是问题

//自底向上public static void sort(Comparable[] a) {int N = a.length;aux = new Comparable[N];for(int size = 1; size<N; size+=size) {//size 子数组大小for(int lo = 0; lo<N-size; lo += size+size) {//lo 子数组索引merge(a, lo, lo+size-1 , Math.min(lo+size+size-1, N-1));//若数组大小非2的幂次，右半部分数组最多只能到末尾}}}

1.5.5 调用轨迹

同样的输入，我们来观察一下自底向上归并排序的调用轨迹

size = 1

调用了merge(a, 0,0,1)
调用了merge(a, 2,2,3)
调用了merge(a, 4,4,5)
调用了merge(a, 6,6,7)
调用了merge(a, 8,8,9)
调用了merge(a, 10,10,11)
调用了merge(a, 12,12,13)
调用了merge(a, 14,14,15)

size = 2

调用了merge(a, 0,1,3)
调用了merge(a, 4,5,7)
调用了merge(a, 8,9,11)
调用了merge(a, 12,13,15)

size = 4

调用了merge(a, 0,3,7)
调用了merge(a, 8,11,15)

size = 8

调用了merge(a, 0,7,15)

1.5.6 两种方式小结

当数组长度为2的幂时，两者所用的比较次数和数组访问次数刚好相等，只是顺序不同

自底向上适用于链表组织的数据，按照这种方法只用重新组织链表的排序方式，不需要额外的链表辅助节点

用自顶向下还是自底向上实现都很自然，归并排序告诉我们，当我们使用一种方式解决时，都应该去尝试另一种

有时，我们看问题的角度会决定了我们解决问题的方式

1.6 快速排序

1.6.1 前言

快速排序是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序

快速排序和归并排序是互补的：

• 归并排序将数组分成两个子数组分别排序，并将有序子数组归并（递归调用发生在处理数组之前）
• 快速排序则是当两个子数组都有序时整个数组也就自然有序了（递归调用发生在处理数组之后）

在快速排序中，切分( p a r t i t i o n partition partition)的位置取决于数组内容

//快速排序算法public static void sort(Comparable[] a) {sort(a, 0, a.length-1);}private static void sort(Comparable[] a, int lo, int hi) {if(lo >= hi)return;int j = partition(a, lo, hi);//切分（后续介绍）sort(a, lo, j-1);//lo...j-1排序sort(a, j+1, hi);//j+1...hi排序}

1.6.2 切分

快速排序算法的关键————切分

现在我们需要实现切分方法：

一般的策略是先随意地选取a[lo]作为切分元素。然后从数组左端向右，数组右端向左，直到找到一个比a[lo]大的a[i]和比a[lo]小的a[j]，交换a[i]和a[j]

如此反复，我们就可以保证左指针i的左侧都不大与切分元素，右指针j的右侧都不小于切分元素

当两指针相遇时，我们只需将a[lo]和a[j]交换，并返回j即可

//切分private static int partition(Comparable[] a, int lo, int hi) {int i = lo;int j = hi+1;while(true) {//扫描左右，检查是否结束并交换while(less(a[++i], a[lo]))if(i == hi)break;while(less(a[lo], a[--j]))if(j == lo)break;if(i >= j)break;exch(a, i, j);//交换i，j}exch(a, lo, j);//将a[lo]放入适当的位置，此时a[lo...j-1]都比a[j]小，a[j+1....hi]都比a[j]大return j;}/*思考：为什么最后是lo和j交换？i指针一直在移动，但i指针停止移动说明了当前的i元素大于lo元素那么，j<=i时，意味着当前的j元素小于lo元素那么交换lo和j也就顺理成章了*/

我们观察一下切分的轨迹

1.6.3 算法的改进

（预留）

1.7 堆排序

1.7.1 优先队列

一般而言，支持——【删除最大元素】、【插入元素】的数据结构称为优先队列

优先队列的使用和队列及栈类似，但高效地实现则更有挑战性

我们接下来会学习【二叉堆】数据结构，这是一种优先队列的经典实现，用数组保存元素并按一定条件排序，以实现高效地（对数级别）删除最大元素和插入元素

优先队列的应用场景：

• 模拟系统，系统按照时间顺序处理所有事件
• 任务调度，优先级决定了应该首先执行哪些任务
• 数值计算，键值代表计算错误，需要按照键值指定顺序修正

1.7.2 初级实现

数组无序实现：

插入方法和栈的push()一样，但是删除最大元素需要遍历所有数组找到最大值

数组有序实现：

删除最大元素方法和栈的pop()一样，但插入元素需要将较大元素向右放，以保证最次都能删除最右边的元素（最大元素）

使用无序序列解决为惰性方法，我们仅在必要的时候采取行动（找最大元素）

而使用有序序列解决会积极方法，因为我们会尽可能未雨绸缪（插入时就保证序列有序）

1.7.3 二叉堆

当一棵二叉树的每个节点都大于等于它的两个子节点时，称为【堆有序】

相应地，堆有序的二叉树中，每个节点都小于等于它的父节点

完全二叉树只需用数组就可以清楚的表示，具体方法时将节点按照层级顺序放入数组：

根节点在1——子节点在2，3——子节点的子节点在4，5，6，7

二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级存储（不使用数组第一个位置）

在一个堆中，位置k的节点，其父节点为【k/2】，子节点为【2k】和【2k+1】

1.7.4 堆算法

1.7.4.1 由下至上堆有序——上浮(swim)

如果堆的某个节点比起父节点大，就打破了堆有序的规则

这时候我们就需要进行修复：反复将该节点与父节点交换，直到恢复堆有序

//若某个节点比其父节点 大，则需要修正堆，进行上浮【swim】操作private void swim(int k) {while(k > 1 && less(k/2, k)) {exch(k, k/2);k = k/2;//重复该过程，直到满足堆有序}}

1.7.4.2 由上至下堆有序——下沉(sink)

如果某节点比起两个子节点还要小，这时候我们就需要下沉【sink】操作：将子节点中较大的节点和其父节点交换，反复执行，直到恢复堆有序

//若某节点比起子节点小，则需要进行下沉【sink】操作private void sink(int k) {while(k*2 <= N) {int j = k*2;if(j < N && less(j, j+1))j = j+1;if(!less(k, j))break;exch(k, j);k = j;}}

1.7.5 基于堆的优先队列实现

public class MaxPQ<Key extends Comparable<Key>> {private Key[] pq; // 基于堆的完全二叉树private int N = 0; // 数据存在a[1.....N]中，a【0】不用// 创建一个最大容量max的优先队列public MaxPQ(int max) {pq = (Key[]) new Comparable[max + 1];}// 是否为空public boolean isEmpty() {return N == 0;}// 返回元素个数public int size() {return N;}// 比较方法private boolean less(int i, int j) {return pq[i].compareTo(pq[j]) < 0;}// 交换private void exch(int i, int j) {Key t = pq[i];pq[i] = pq[j];pq[j] = t;}// 若某个节点比其父节点 大，则需要修正堆，进行上浮【swim】操作private void swim(int k) {while (k > 1 && less(k / 2, k)) {exch(k, k / 2);k = k / 2; // 重复该过程，直到满足堆有序}}// 若某节点比起子节点小，则需要进行下沉【sink】操作private void sink(int k) {while (k * 2 <= N) {int j = k * 2;if (j < N && less(j, j + 1))j = j + 1;if (!less(k, j))break;exch(k, j);k = j;}}// 插入元素public void insert(Key v) {pq[++N] = v;swim(N); // 插入到最后，然后执行上浮操作}// 删除并返回最大元素public Key delMax() {Key ret = pq[1];exch(1, N--); // 和最后一个元素交换pq[N + 1] = null; // 防止越界sink(1); // 执行下沉操作return ret;}// 返回最大元素public Key max() {return pq[1];}}

1.7.6 堆排序

1.7.6.1 堆的构造

给定N个元素如何构造堆？

我们首先想到的是从左遍历数组，用swim（）扫描指针左侧所有元素，保证为一颗堆有序的完全树，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

一个更聪明且有效的方法是从右到做用sink（）函数构造子堆

public static void sort(Comparable[] a){ int N = a.length; for(int k = N/2; k>=1; k--){ sink(a, k, N);//第一阶段：构造了堆 } /* 思考：为什么k初值使N/2 N/2意味着，当前初始值是从堆的倒数第二层（或倒数第一层【满二叉树时】）进行下沉 */ while(N > 1){ exch(a, 1, N--); sink(a, 1, N);//第二阶段：下沉排序 }}

1.7.6.2 下沉排序

堆排序的主要工作由下沉排序sink（）函数来完成

//k-n之间进行下沉操作private static void sink(Comparable[] a, int k, int n) {int j = k*2;while(k <= n) {if(j < n && less(j, j+1))j = j+1;if(!less(k, j))break;exch(a, k, j);k = j;}}

1.7.7 小结

堆排序在排序复杂性的研究中有着重要地位，因为它是我们所知的唯一能同时最优地利用时间和空间的方法

在最坏的情况下保持与 2 N l g N 2NlgN 2NlgN 成正比

当空间十分紧张时他很流行，因为它只用几行代码就行实现较好的性能，但现代系统的许多应用很少使用，因为它无法利用缓存

另一方面，堆实现的优先队列越来越重要，是因为能在【插入操作】和【删除最大元素操作】保证对数级别运行时间

2. 符号表

2.1 符号表

主要目的是将一个【键】和一个【值】联系起来

2.1.1 相关规定

我们所有的实现都遵循以下规则：

• 每个【键】都对应着一个值（表中不存在重复的键）
• 当向表中存入键值和已有的键冲突时，覆盖对应【键】的值

这些规则定义了关联数组的抽象形式，你可以将符号表想象成一个数组，键即索引，值即数组的元素

【键】不能为空

我们还规定值不能为空，应为我们的API定义中，当键不存在时get（）方法会返回null，这也意味着任何不在表中的键关联的值为空

2.1.2 删除操作

在符号表中，删除的实现有两种方法

• 延时删除：将键对应的值置为null，然后在某个时候删去所有值为null的键
• 即时删除：立刻从表中删除对应的键

2.2 基于链表实现的无序符号表

2.2.1 实现

public class SequentialSearchST<Key, Value> {private Node first;//头结点private class Node{//私有内部类Key key;Valueval;Node next;public Node(Key key, Valueval, Node next) {this.key = key;this.val = val;this.next = next;}}/** * 查找给定的键，返回对应值 */public Value get(Key key) {for(Node x = first; x != null; x = x.next) {if(key.equals(x))return x.val;}return null;}/** * 查找给定的键，找到则更新其值，否则表头新建节点 */public void put(Key key, Valueval) {for(Node x = first; x != null; x = x.next) {if(key.equals(x))x.val = val;}first = new Node(key, val, first);//未命中，新建节点}}

命题：

在含有N对键值的基于无序链表的符号表中，未命中的查找和插入操作都需要N次比较。命中的查找在最坏情况下也需要N次比较。

像一个空表插入N个节点需要1+2+3+…+N次比较

上述命题说明了基于链表实现的顺序查找是非常低效的，根本无法满足大数据量操作的需求（时间复杂度达到了平方级别）

2.3 有序数组的二分查找

该算法实现的核心在rank（）方法，它返回表中小于给定键的数量

而我们使用有序数组存储键的原因是二分查找法能够根据数组的索引大大减少每次查找所需要的比较次数

2.3.1 实现

/** * 思考？为什么循环结束时，lo值正好等于表中小于被查找的键的数量 */public int rank(Key key) {int lo = 0;int hi = N-1;while(lo <= hi) {int mid = (lo+hi)/2;int cmp = key.compareTo(keys[mid]);if(cmp < 0) hi = mid-1;else if(cmp > 0) lo = mid+1;else return mid;}return lo;}

2.3.2 复杂度分析

命题

在N个键的有序数组中进行二分查找最多需要(logN+1)次比较

尽管能够保证查找所需时间是对数级别的，该算法仍然无法保证处理大型问题，因为put（）方法太慢了

二分查找虽然减少了比较次数，但无法减少运行所需时间，因为它无法改变以下事实：

在键是随机排列的情况下，构造一个基于有序数组的符号表需要访问数组的次数是数组长度的平方级别

命题

x向大小N的有序数组插入一个新的元素最坏情况下需要访问~2N次数组，因此像一个空符号表插入N个元素需要 访问~N²次数组

2.4 二叉查找树

2.4.1 定义

我们可以将二叉树定义为一个空链接，或者一个有左右两个链接的节点，每个连接都指向一个（独立的）子二叉树

一颗二叉查找树(BST)是一颗二叉树，其中每个节点都含有一个Comparable的键且每个节点的键都大于其左子树的任意节点，小于右子树的任意节点

2.4.2 实现

/** * 二叉查找树 * */public class BST<Key extends Comparable<Key>, Value> {private Node root;//根节点private class Node{private Key key;private Valueval;private Node left;private Node right;private int N;//节点总数public Node(Key key, Valueval, int N) {this.key = key;this.val = val;this.N = N;}}//计算树的总节点数public int size() {return size(root);}private int size(Node x) {if(x == null)return 0;elsereturn size(x.left)+size(x.right) + 1;}public Value get(Key key) {return get(root, key);}private Value get(Node x, Key key) {if(x == null)return null;int cmp = key.compareTo(x.key);if(cmp < 0)return get(x.left, key);else if(cmp > 0)return get(x.right, key);else return x.val;}/** * 查找key， 找到则更新它的值，否则为它创建一个新的节点 */public void put(Key key, Valueval) {root = put(root, key, val);}/** * 如果key存在于以x为根节点的子树中更新它的值 * 否则将以key和val作为新节点插入该子树中 */private Node put(Node x,Key key, Valueval) {if(x == null)return new Node(key, val, 1);int cmp = key.compareTo(x.key);if(cmp < 0)x.left = put(x.left, key, val);else if(cmp > 0)x.right =put(x.right, key, val);else x.val = val; x.N = size(x.left) + size(x.right) + 1;return x;}}

2.4.3 插入

上述代码中的查找代码几乎和二分查找一样简单，这种间接性是二叉查找树的重要特性之一

而二叉查找树的另一个重要特性是插入的实现难度和查找差不多

当查找一个不存在于树中的节点并结束与一条空链接时，我们需要做的就时让链接指向一个新节点：

• 如果树是空的，返回一个新节点
• 如果被查找的键小于根节点的键，就继续递归地在左子树中插入该键
• 否则，在右子树中插入该键

2.4.4 递归

因为树本身就是递归定义的，很自然地我们会想到用递归的思想来解决问题

我们可以将调用前的代码想象成沿着树向下走：它会将给定的键和每个节点的键相比较并根据结果向左或者向右移动

对于调用后的代码可以想象成沿着树向上爬(这时候会更新树结构)

2.4.5 算法分析

使用二叉查找树的算法的运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序

最好的情况——N个节点的树是完全平衡的

最坏的情况——搜索路径上可能有N个节点，这就变成线性表了

对于很多应用来说，下图的简单模型都是适用的：

我们假设键的分布是（均匀）随机的，或者说他们的插入顺序是随机的

对于这个模型的分析而言，二叉查找树和快速排序几乎是双胞胎————树的根节点就是快速排序第一个切分的元素，左侧的键都小于它，右侧的键都大于它，而这对于所有的子树同样使用，这和快速排序中对子数组的第归排序是完全对应

命题

在由N个随机键构造的二叉查找树中，查找命中平均所需要的比较次数为~~2lnN（约1.39lgN）

2.4.6 最大键和最小键

如果根节点的左儿子为空，那么一颗二叉查找树的最小键就是根节点，否则，则一直递归到最左侧

/** * 递归的找最大键 */public Key max() {return max(root);}private Key max(Node x) {if(x.right == null)return x.key;else return max(x.right);}/** * 递归的找最小键 */public Key min() {return min(root);}private Key min(Node x) {if(x.left == null)return x.key;else return min(x.left);}

2.4.7 向上取整和向下取整

• 如果给定的键小于二叉查找树的根节点的键，那么小于等于key的最大键（floor）一定在根节点的左子树中
• 如果给定的键key大于根节点，那么只有当根节点右子树中存在小于等于key的节点时，小于等于key的最大键才会出现在右子树中

/** * 小于等于key的最大键 */public Key floor(Key key) {return floor(root, key);}private Key floor(Node x, Key key) {if(x == null)return null;int cmp = key.compareTo(x.key);if(cmp < 0)return floor(x.left, key);else if(cmp == 0)return x.key;Key t = floor(x.right, key);//看小于等于key的最大键是否在右子树中，很精彩！if(t != null)return t;else return x.key;}

2.4.8 选择

二叉查找树的选择操作和之前我们学过的(2.6.2)基于切分的数组的选择操作类似

我们在每个节点中维护子树节点数N就是用来支持此操作的

/** * 返回排名为k的节点 */public Key select(int k) {return select(root, k);}private Key select(Node x, int k) {if(x == null)return null;int t = size(x.left);if(k < t )return select(x.left, k);else if(k > t)return select(x.right,k-t-1);else return x.key;}

2.4.9 排名

rank()是select()的逆方法，它会返回给定键的排名

• 如果给定的键和根节点的键相等，则返回左子树节点总数（小于当前节点的个数）
• 如果小于根节点，我们则返回在左子树的排名（递归）
• 同理，若大于根节点，则返回在（左子树的节点总数 + 1 + 右子树中的排名）

下面，我们需要考虑递归时的基准情况(Base Case)：

• 若根节点为null，返回0
• 若根节点不为null，分为小于、等于和大于三种情况

/** * 返回小于root.key的数量 */public int rank(Key key) {return rank(root, key);}private int rank(Node x, Key key) {if(x == null)return 0;int cmp = key.compareTo(x.key);if(cmp == 0) return size(x.left);else if(cmp < 0)return rank(x.left, key);else return rank(x.right, key) + 1 + size(x.left);}

2.4.10 删除最大键和最小键

二叉查找树中最难实现的时delete（）方法

作为热身，我们先从删除最小键和最大键开始（同样地，还是用递归思想来解决）

我们的递归方法接受一个指向节点的链接，并返回一个指向节点的链接，这样我们就能够方便地改变树的结构，将返回的链接赋给作为参数的链接

对于删除最小键，我们要不断深入树的左子树，直到遇到一个空节点。这时候我们返回该节点的右节点即可改变当前树的结构了（此时没有任何链接指向的节点会被回收）

/** * 删除最小键 */public void deleteMin() {root = deleteMin(root);}private Node deleteMin(Node x) {if(x.left == null)return x.right;else {x.left = deleteMin(x.left);x.N = size(x.left) + size(x.right) + 1;return x;}}/** * 删除最大键 */public void deleteMax() {root = deleteMax(root);}private Node deleteMax(Node x) {if(x.right == null)return x.left;else {x.right = deleteMin(x.right);x.N = size(x.left) + size(x.right) + 1;return x;}}

2.4.11 删除操作

• 删除算法实现并不简单，请仔细理解正文的讲解

我们可以用类似的方法来删除任意一个只有一个子节点（或者没有子节点）的节点

但是我们怎样删除一个拥有两个子节点的节点呢？删除之后，我们要处理两个子树

解决方法：当删除了x后，将用x的右子树中最小节点来作为当前新的x

我们能用4个简单的步骤完成替换操作

将指向即将删除的节点保存为T

将x指向它的后继节点 min（x.right）

将x的有链接指向 deleteMin（t.right）

将x的左连接设为t.left

/** * 删除任意节点 */public void delete(Key key) {root = delete(root, key);}private Node delete(Node x, Key key) {if(x == null)return null;int cmp = key.compareTo(x.key);if (cmp < 0)x.left = delete(x.left, key);//更新左子树结构else if(cmp > 0)x.right = delete(x.right, key);//更新右子树结构else {//首先处理某树只有一个节点的情况if(x.left == null)return x.right;if(x.right == null)return x.left;//处理有两个子节点的情况，需要用其右子树的最小节点作为当前的根节点Node t = x;x = minNode(t.right);deleteMin(t.right);x.left = t.left;}x.N = size(x.left) + size(x.right) + 1;//更新节点计数器return x;}private Node minNode(Node x) {if(x.left == null)return x;else return minNode(x);}

2.4.12 二叉树遍历

具体见《OneNote笔记》

思路：当每一轮遍历时，把当前该子树想象成一个新的树，不断地递归

（递归的实现很简单，那么迭代呢？）

2.4.13 性能分析

在一个二叉树中，树的高度决定了所有操作在最坏情况下的性能

总的来说，二叉查找树的实现并不困难，但是二叉查找树在最坏情况下的恶劣性能时不能接受的

如果所有键都是按顺序或逆序插入符号表就会使得二叉查找树的性能直接变成了线性符号表的等级

为了避免这种极端情况的发生，我们引入了————平衡二叉树

2.5 2-3查找树

定义：

• 2- 节点，含有一个键、两条连接
• 3- 节点，含有两个键、三条连接，左儿子小于节点，中儿子位于两键之间，右儿子大于节点

2.5.1 查找

2.5.2 插入

为了保持插入后树的平衡性：

如果未命中的查找结束于2- 节点，我们只需要把2- 节点换成3- 节点，将新键插入其中

如果未命中的查找结束于3- 节点，事情会麻烦一点

2.5.2.1 向一颗只含有一个3- 节点的树插入新键

为了将新键插入，我们要先临时建立一个4- 节点（含有三个键和四条链接）

然后将其转换成一个含有三个2- 节点的树（中键作为根）

2.5.2.2 向一个父节点为2-节点的3-节点插入新键

在这种情况下，我们先像刚才一样构造一个4- 节点，并将其分解

按我们此时不会为中键创建一个新节点，而是将其移动到原来的父节点中，你可以将这次转换看成：

指向原3- 节点的一条连接替换为新父节点的原中键左右两边的两条链接，并分别指向两个新的2- 节点

2.5.2.3 向一个父节点为3- 节点的3- 节点中插入新键

我们构造一个4- 节点然后分解它，然后将他的中键插入到父节点中

但是父节点仍然是一个3- 节点，需要再次构造一个4- 节点，在这个节点上做相同的变换，一直不断向上分解，直到遇到一个2- 节点并替换为不需要再分解的3- 节点【即3.5.2.2的情况】

2.5.2.4 分解根节点

如果从插入节点到根节点的路径上全部是3- 节点，我们的根节点最终也会变成一个4- 节点

此时我们可以按照一颗只有一个3- 节点的树中插入新键的做法，将其分解为3个2- 节点（树高+1）

2.5.3 小结

4- 节点的分解是一次局部变换，不会影响树的有序性和平衡性

只有当根节点为4- 节点时，分解后树高才会+1

标准二叉查找树自上向下的生长：每次的插入都是无脑的放在叶子节点上，很容易导致树的“倾斜”

2-3树是自下向上生长的：插入的时候“稳一手”，防止其无脑向下“伸展”，用一个4-节点hold住，然后调整树的局部平衡性

一棵大小N的2-3树中，查找和插入操作访问的节点必然不超过lgN个

2.5.4 不足

但是我们和真正的实现还有距离，因为需要处理的情况实在太多：

需要维护两种不同类型的节点，将节点从一种数据结构（2节点）换到另一种数据结构（3节点）很麻烦

幸运的是，我们只需要一点点代价就能用一种统一的方式完成————红黑树

2.6 红黑树

2.6.1 定义

红黑树背后的基本思想——就是用标准的二叉查找树（完全由2-节点构成）和一些额外的信息（替换3-节点）来表示2-3树

我们将连接分成两种类型：

• 红链接将两个2-节点连接起来构成3-节点

• 黑链接则是2-3树的普通链接

另一种定义是：

• 红链接均为左链接
• 没有任何一个节点同时和两条红链接相连
• 树完美黑色平衡：任意空连接到根的路径上黑节点的数量相同

那么，红黑树就将二叉树高效的查找方法和2-3树的高效平衡插入两者的优点结合到了一起

2.6.2 节点表示

我们用布尔量表示颜色——true=红色，false=黑色（空节点默认黑色）

private static final boolean RED = true;private static final boolean BLACK = false;private class Node{ Key key; Valueval; Node left,right; int N;//节点总数 boolean color;//颜色 Node(Key key, Valueval, int N, boolean color){ this.key = key; this.val = val; this.N = N; this.color = color; } }private boolean isRed(Node x){ if(x == null)return false; return x.color == RED; }

2.6.3 旋转

我们在实现的某些操作中，可能会出现红色右连接或者两条连续的红链接，这种时候，我们需要小心地旋转并修复

首先，假设我们有一个红右连接，我们需要转换成红左连接————称为左旋转

同理，右旋转则相反

2.6.3.1 在旋转后重置父节点的链接

在旋转之后，我们总是会返回相应的链接，这也使得出现一种情况——产生连续两条的红链接

但我们的算法会继续用旋转在纠正它

2.6.3.2 向2- 节点插入新键

一棵只含有一个键的红黑树只含有1个2- 节点，插入另一个键后，我们马上就需要将它们旋转

• 如果新键小于老键，我们只需要增加一个红节点，这于3- 节点完全等价
• 如果新键大于老键，那么新增的红色节点会产生一条红链接，我们进行一次左旋转即可

2.6.3.3 向底部的2- 节点插入新键

用和二叉树相同的方式在红黑树中插入新键，会在树的底部新增一个节点

我们总是用红链接将新节点和它的父节点相连

• 如果父节点是2- 节点，那么上面的方法同样适用
• 如果是父节点的左链接指向新节点，那么即成为了一个3- 节点； 如果是父节点的右链接指向新节点，我们则需要进行左旋转

2.6.3.4 向一颗双键树（即一个3- 节点）插入新键

分为三个子情况

新键小大原树中的两个键：则连接到3- 节点的右链接，此时树是平衡的，我们再将两个红链接变为黑色，就得到了一个3个节点组成的树（相当于3.5.2.1的情况）

新键小于原树中的两个键：它会被链接到最左边的空连接，这是就产生了两个连续的红链接，此时我们需要将上层的红链接右旋转即得到第一种情况

新键介于两键之间：这又会产生两条连续的红链接（即插入到红节点的右链接），此时我们需要将下层的两个红链接左旋转，即得到了第二种情况，由第二种情况我们又可以得到第一种情况（精彩！）

2.6.3.5 颜色转换

我们用flipColors（）方法来转换一个节点的两个红色子节点的颜色，将其变为黑色，并将父节点的颜色变红

这项操作的重要性质在于：和旋转操作一样都是局部变换，不会影响整棵树的平衡性

void flipColors(Node h){ h.color = RED; h.left.color = BLACK; h.right.color = BLACK; }

2.6.3.6 根节点总是黑色

我们每次插入时，都会将根节点设为黑色

注意，每当根节点由红遍黑时，树的黑链接高度会+1

2.6.3.7 向树底部的3- 节点插入新键

现在假设我们需要在树的底部的一个3- 节点下加一个新节点，那么3.6.3.4的三种情况都会出现

• 三者最大，此时转换颜色即可
• 三者最小，上层右旋转后，转换颜色
• 介于中间，下层左旋转，再上层右旋转后，转换颜色

（颜色转换意味着中间的节点会变红，相当于将它送入了父节点，这意味着再父节点中继续插入一个新键，我们也会用相同的办法解决）

2.6.3.8 将红链接在树中向上传递

之前讲述的三种情况说明了红黑树实现2-3树的插入算法的关键步骤：

要在一个3- 节点 插入新键，先建立一个临时的4- 节点，然后分解将红链接由中间键传给父节点

2.6.4 实现

因为保持树的平衡性所需的操作时由下向上在每个所经过的节点中进行的，将它们植入我们已有的实现中非常简单：只要在递归调用之后完成即可

/** * if there exists a node.key that equals this new key, make node.val = val * otherwise, insert a new node into this tree */public void put(Key key, Valueval) {root = put(root, key, val);}private Node put(Node x, Key key, Valueval) {if(x == null)return new Node(key, val, 1, RED);int cmp = key.compareTo(x.key);if(cmp < 0)x.left = put(x.left, key, val);else if(cmp > 0)x.right = put(x.right, key, val);elsex.val = val;//after putting the node, we must keep tree's balance//let's think about three conditionsif(isRed(x.right) && !isRed(x.left))x = rotateLeft(x);if(isRed(x.left) && isRed(x.left.left))x = rotateRight(x);if(isRed(x.left) && isRed(x.right))flipColors(x);x.N = size(x.left) + size(x.right) + 1;return x;}

关键代码在于三个 if 语句

第一条if：会将任意含有红色右链接的3- 节点左旋转

第二条if：会将连续两个红链接中上层右旋转

第三条if：转换颜色

2.6.5 删除

（实现更为复杂，作为进阶阶段学习）

2.6.6 性质

首先，无论键的插入顺序如何，红黑树几乎都是完美平衡的

一颗大小为N的红黑树的高度不会超过2lgN

一颗大小为N的红黑树，根节点到任意节点的平均路径长度为~1.00lgN

由于get（）方法不会care节点的颜色，所以查找效率 > 插入效率

2.7 散列表

如果所有的数都是小整数，我们可以用数组来实现符号表

键——数组索引

值————索引对应的数组值

这样我们就可以快速访问任意键的值

使用散列的查找算法分为两步：

用散列函数将被查找的键转化为数组索引，因此我们可能会出现多个键散列到同一索引下

处理碰撞冲突的过程（拉链法、线性探测法）

散列表是算法在时间和空间上作出权衡的经典例子

2.7.1 散列函数

这个过程会将键转化为数组的索引

2.7.1.1 正整数

选择一个大小为M的素数，计算任意 K%M的结果

2.7.1.2 字符串

除余法也可以处理较长的键，例如字符串

我们只需要将字符串当成大整数即可

int hash = 0;for(int i=0; i<s.length(); i++){ hash = (R * hash + s.charAt(i)) % M;}

2.7.2 拉链法

当产生两个或多个键的散列值相同的情况，一种直接的方法就是将M个数组中的每个元素指向一条链表

这时的查找分为两步：

• 找到散列值对应的链表
• 按链表顺序查找

public class SeparateChainingHashST<Key, Value> {private int N;//aoumt of <key,value>private int M;//size of hash tableprivate SequentialSearchST<Key, Value>[] st;//hash arraypublic SeparateChainingHashST() {init(997);}public void init(int M) {this.M = M;st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];for(int i=0; i<M; i++) {st[i] = new SequentialSearchST();}}private int hash(Key key) {return (key.hashCode() & 0x7fffffff) % M;//屏蔽最高位，将整数转成一个 非负整数取余}public Value get(Key key) {return st[hash(key)].get(key);}public void put(Key key, Valueval) {st[hash(key)].put(key, val);}}

当能预先知道符号表的大小时，另一种更可靠的方案：动态调整数组大小

基于拉链法的散列表的实现简单，在键的顺序不重要的应用中，它可能时最快的（也是最广泛的）符号表实现

2.7.3 线性探测法

另一种方法就是用大小M的数组保存N个键值对，其中M>N

我们需要依靠数组中的空位解决碰撞冲突，基于这种策略的所有方法称为——开放地址散列表

其中一个最简单的方法叫做：线性探测法

当碰撞发生时，我们直接检查散列表中的下一个位置，这样可能产生三种情况：

命中，该位置的键和被查找的键相同

未命中，该位置没有键

继续查找，该位置键于被查找的键不同

public class LinearProbingHashST<Key, Value> {private int N;//键值总对数private int M = 16;private Key[] keys;private Value[] vals;public LinearProbingHashST() {keys = (Key[]) new Object[M];vals = (Value[]) new Object[M];}private int hash(Key key) {return (key.hashCode() & 0x7fffffff) % M;//屏蔽最高位，将整数转成一个 非负整数取余}public Value get(Key key) {for(int i=hash(key); keys[i] != null; i = (i+1)%M) {if(keys[i].equals(key))return vals[i];}return null;}private void resize(int cap) {LinearProbingHashST<Key, Value> t;t = new LinearProbingHashST<Key, Value>(n);for(int i=0; i<M; i++) {if(keys[i] != null) {t.put(keys[i], vals[i]);}}keys = t.keys;vals = t.vals;M = t.M;}public void put(Key key, Valueval) {if(N >= M/2)resize(2*M);int i;for(i = hash(key); keys[i] != null; i = (i+1)%M) {if(keys[i].equals(key)) {vals[i] = val;return;}}keys[i] = key;vals[i] = val;N++;}}

线性探测法的思路就是：

• 插入：

  如果散列值对应的索引已经不为null（发生了碰撞），就依次向后走，直到遇到一个空位置坐下

• 查找：

• 如果散列值对应的索引处的键和被查找的键相同，命中

• 如果对应索引的键位空，未命中

• 如果不相等，继续向后走，直到遇到空位置（查找失败）

2.7.3.1 删除操作

我们直接删除对应位置的键是不行的，因为之后的键可能因此无法查找

所以我们需要将当前键删了之后，将后面直到为空之前的所有键再重新插入

2.7.3.2 键簇

我们将一组连续的条目，叫做键簇

显然，当键簇越短时才能保证较高的效率，随着插入的键越来越多，这个要求很难满足，较长的键簇会越来越多

要去理解并内化知识的精髓，而不是单单去死记住这些概念性的东西，毕竟这些知识是别人的东西，别人的思想再怎么搬运还是别人的，要学会从别人那里领悟到本质，并转化为自己的东西，让自己也具备发现问题、解决问题的能力

3 图

图模型：

• 无向图
• 有向图
• 加权图
• 加权有向图

3.1 无向图

3.1.0 相关术语介绍

• **自环：**一条连接一个顶点和其自身的边
• **平行边：**链接同一对顶点的两条边
• **多重图：**含有平行边的图
• 简单图：没有平行边或环的图
• **路径：**由边顺序连接的一系列顶点
• **简单路径：**一条没有重复顶点的路径
• **简单环：**不含有重复顶点和边的环
• 路径或者环的的长度= 边数

如果从任意一个顶点都存在一条路径到达另一个任意顶点————称为连通图

树是无环连通图，互不相连的树组成的集合称为森林

连通图的生成树是它的一副子图

生成树森林是所有连通子图的生成树的集合

一个V个节点的图G满足五个条件，可以称为一棵树：

G由 V-1 条边，且无环

G由 V-1 条边，且连通的

G连通图，但删除任意一条边不再相通

G无环图，但添加任意一条边产生环

G的任意一对顶点之间仅存在一条简单路径

3.1.1 图的表示方式

邻接矩阵边的数组邻接表

使用一个V*V的布尔矩阵，当有相连的边时，对应单元为true（空间代价太高！）	存储边集	以一个顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表

3.1.2 邻接表

将每个顶点的所有相邻顶点都保存在该顶点对应的元素所指向的一张链表中

每条边都会出现两次

• 使用的空间和 V+E 成正比
• 添加 1条边的所需时间为常数
• 遍历顶点v的所有相邻顶点的时间与度数成正比

public class Graph {private final int V;//顶点数目private int E;//边数目private Bag<Integer>[] adj;//邻接表public Graph(int V) {this.V = V;adj = (Bag<Integer>[])new Bag[V];for(int v=0; v<V; v++) {adj[v] = new Bag<Integer>();}}/** * compute V's degree */public static int degree(Graph G, int v) {int degree = 0;for(int w:G.adj(v))degree++;return degree;}/** * cal max(degree(G,v)) */public static int maxDegree(Graph G) {int max = 0;for(int v=0; v<G.V(); v++) {if(degree(G, v) > max)max = degree(G, v);}return max;}/** * 所有节点平均度数 */public static double avgDegree(Graph G) {return 2*G.E()/G.V();}/** * 计算环的个数 */public static int numberOfSelfLoops(Graph G) {int cnt = 0;for(int v=0; v<G.V(); v++) {for(int w : G.adj(v)) {if(w == v)cnt++;}}return cnt/2;//每条边标记过2次}/** * return the num of vetexs */public int V() {return V;}/** * return the num of edges */public int E() {return E;}/** * add a edge bwteen v and w */public void addEdge(int v, int w) {adj[v].add(w);adj[w].add(v);E++;}/** * all vertexs(array) adjoin v */public Iterable<Integer> adj(int v){return adj[v];}}

3.1.3 深度优先搜索—DFS

public class DFS {private boolean[] marked;private int count;public DFS(Graph G, int s) {marked = new boolean[G.V()];dfs(G, s);}private void dfs(Graph G, int v) {marked[v] = true;count++;for(int w:G.adj(v)) {if(!marked[w])dfs(G, w);//若当前顶点没有走过，go ahead！}}public boolean marked(int w) {return marked[w];}public int count() {return count;}}

DFS只需要一个递归方法来遍历所有节点，在访问一个顶点时：

• 标记当前节点：已访问
• 递归的访问该节点所有没有被标记过的邻接点

通常，理解一个算法算好的方法就是跟踪它的行为

我们要注意两点：

算法遍历边和访问顶点的顺序和图的表示是有关的，因为DFS只会访问当前节点所有的相邻极点

每条边都会被访问两次。并且第二次访问时总发现当前节点已经标记过了

3.1.4 寻找路径

我们利用DFS来建立一个寻找路径的算法

public class DFSpaths {private boolean[] marked; // 顶点标记数组private int[] edgeTo;private final int s; // 起点【source】public DFSpaths(Graph G, int s) {// TODO Auto-generated constructor stubmarked = new boolean[G.V()];edgeTo = new int[G.V()];this.s = s;dfs(G, s);}private void dfs(Graph G, int v) {marked[v] = true;for (int w : G.adj(v)) {if (!marked[w]) { // if Vertex w isn't marked/** * 到达顶点w的是顶点v */edgeTo[w] = v;dfs(G, w);}}}public boolean hasPathTo(int v) {return marked[v];}public Iterable<Integer> pathTo(int v) {/** * 如果v没被标记，说明没有顶点能够到顶点v，返回 */if (!hasPathTo(v))return null;Stack<Integer> path = new Stack<Integer>();for (int x = v; x != s; x = edgeTo[x]) { // 从终点向起点走，利用栈保存path.push(x);}path.push(s);return path;}}

edgeTo[] 数组会记住每个顶点到起点的路径，从而形成一个以起点s 为根的含有所有与s相连的路径的树

【将DFS的轨迹想象成一个树的构成】

3.1.5 广度优先搜索—BFS

在BFS中，我们希望按照与起点的顺序来遍历所有顶点，看起来很容易实现————使用队列

广度优先搜索的真正目标：————为了找到最短路径

3.1.5.1 实现

算法流程简述：

先将起点 s 加入队列

反复执行下列行为，直至队列空：

取队列的下一个顶点，并标记它

将当前顶点的所有（未标记的）邻点都放入队列

BFS算法并不是递归的，它最终也能形成一棵树

public class BFS {private boolean[] marked;private int[] edgeTo;private final int s;//sourcepublic BFS(Graph G, int s) {marked = new boolean[G.V()];edgeTo = new int[G.V()];this.s = s;bfs(G, s);}private void bfs(Graph G, int v) {Queue<Integer> queue = new Queue<Integer>();//利用队列结构来实现bfsmarked[v] = true;queue.enqueue(v);while(!queue.isEmpty()) {int t = queue.dequeue();for(int w : G.adj(t)) {if(!marked[w]) {edgeTo[w] = t;//到达w的顶点为tmarked[w] = true;//标记已经访问过的顶点queue.enqueue(w);}}}}public boolean hasPathTo(int v) {return marked[v];}public Iterable<Integer> pathTo(int v) {/** * 如果v没被标记，说明没有顶点能够到顶点v，返回 */if (!hasPathTo(v))return null;Stack<Integer> path = new Stack<Integer>();for (int x = v; x != s; x = edgeTo[x]) { // 从终点向起点走，利用栈保存path.push(x);}path.push(s);return path;}}

同样的，使用BFS算法遍历时，每条边都会被访问两次，且第二次访问时这条边已经被标记过了

3.1.6 DFS和BFS

这两个算法的不同之处仅仅在于从数据结构中获取下一个顶点的规则

• 对于BFS来说，是最早加入的顶点
• 对于DFS来说，是最晚加入的顶点（递归的过程，最早加入的最后才会返回）

3.1.7 连通分量

过程

从0 号顶点开始dfs 遍历

如果遇到没有标记的顶点，重复进行遍历（遍历的路径上的所有顶点都是一个连通分量）

public class CC {private boolean[] marked;private int[] id;private int count;public CC(Graph G) {marked = new boolean[G.V()];id = new int[G.V()];for (int x = 0; x < G.V(); x++) {/** * 从第一个顶点开始，如果位被标记，则从该节点dfs遍历（一个新的连通分量） */if (!marked[x]) {dfs(G, x);}count++; // 下一个连通分量}}private void dfs(Graph G, int v) {marked[v] = true;id[v] = count;for (int w : G.adj(v)) {if (!marked[w]) {/** * 从起点v开始的所有遍历过的路径上的所有顶点都是一个连通分量 */id[w] = count;dfs(G, w);}}}public boolean connected(int v, int w) {return id[v] == id[w];}public int id(int v) {return id[v];}public int count() {return count;}}

3.1.8 使用DFS的应用

3.1.8.1 判断是否有环

public class Cycle {private boolean[] marked;private boolean hasCycle;public Cycle(Graph G) {marked = new boolean[G.V()];for(int s=0; s<G.V(); s++) {if(!marked[s]) {dfs(G, s, s);}}}private void dfs(Graph G, int v, int u) {marked[v] = true;for(int w:G.adj(v)) {if(!marked[w]) {dfs(G, w, v);}else if( v == u) {/** * dfs的参数为当前顶点和已经标记的相邻顶点，如果两个顶点相等，说明遇到了环 */hasCycle = true; break;}}}public boolean haCycle() {return hasCycle;}}

3.1.8.2 是否为二分图（双色问题）

public class TwoColor {private boolean[] marked;private boolean[] color;private boolean isTwocolor = true;public TwoColor(Graph G) {marked = new boolean[G.V()];color = new boolean[G.V()];;for (int s = 0; s < G.V(); s++) {if (!marked[s]) {dfs(G, s);}}}private void dfs(Graph G, int v) {marked[v] = true;for (int w : G.adj(v)) {if (!marked[v]) {color[w] = !color[v];//在遍历下一个顶点之前做动作dfs(G, w);} else if (color[v] == color[w]) // 如果两个相邻顶点颜色一样，则不是二分图isTwocolor = false;}}public boolean isTwoColor() {return isTwocolor;}}

3.2. 有向图

3.2.1 基本API实现

public class Digraph {private final int V;//顶点数目private int E;//边数目private Bag<Integer>[] adj;//邻接表public Digraph(int V) {this.V = V;adj = (Bag<Integer>[])new Bag[V];for(int v=0; v<V; v++) {adj[v] = new Bag<Integer>();}}/** * return the num of vetexs */public int V() {return V;}/** * return the num of edges */public int E() {return E;}/** * add an edge bwteen v and w * notice that in the Digraph, every edges have a direction */public void addEdge(int v, int w) {adj[v].add(w);//因为是有向的，所以只需要添加一条边E++;}/** * all vertexs(array) adjoin v */public Iterable<Integer> adj(int v){return adj[v];}/** * 构造有向图的反向图 */public Digraph reverse() {Digraph R = new Digraph(V);for(int v=0; v<V; v++) {for(int w:adj(v)) {R.addEdge(w, v);}}return R;}}

3.2.2 DFS、BFS

本质上和无向图的DFS、BFS实现是一样的（同样的思想）

3.2.3 多点可达性

给定一副有向图和顶点的集合，回答：

• 是否存在一条从集合中的任意顶点到达给定顶点v的有向路径

实际应用：内存管理系统(java垃圾回收机制)

3.2.4 调度问题

一种应用广泛的模型是给定一组任务并安排执行顺序

最重要的一种限制条件————优先级限制

3.2.5 拓扑排序

优先级限制下的调度问题等价于拓扑排序问题

【拓扑排序】：给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素

拓扑排序（或者说优先级限制问题）是针对有向无环图【DAG】的，因此是不允许有环的

拓扑排序就是dfs逆后序的顶点排序

3.2.6 有向图寻找环

寻找环的基本思想还是利用DFS算法，

但是我们增加了一个boolean类型的数组onStack[]来保存递归调用期间栈上的所有顶点

如果找到一条边v->w，并且w已在栈中（也就意味着之前已经标记过的顶点w在之后又被找到，也就是一条环路）

则找到了一个有向环

public void dfs(Digraph G, int s) {marked[s] = true;onStack[s] = true;for(int w:G.adj(s)) {if(hasCycle())return;else if(!marked[w]) {edgeTo[w] = s;dfs(G, w);}else if(onStack[w]) {//有环路，则记录环路路径cycle = new Stack<Integer>();cycle.push(w);for(int x=edgeTo[w]; x != w; x = edgeTo[x]) {cycle.push(x);}}onStack[s] = false; //若当前搜索路径没有找到环，需要将栈数组复原，以便下一条路径的搜索}}

3.2.7 强连通性

如果一副有向图中的任意两个顶点都是强连通的，则称这幅图是强连通的

（难以理解，跳过，后续深入）

3.2.8 顶点对的可达性

只需利用DFS进行可达性的判定，但无法使用于大型图网络（构造图的代价太高）

public class TransitiveClosure {private DirectedDFS[] all;public TransitiveClosure(Digraph G) {all = new DirectedDFS[G.V()];//有向图DFSfor(int v=0; v<G.V(); v++) {/** * 构造了一个二维数组，相当于矩阵表示图关系 * 每个节点DFS一次，若v和w相连，那么marked[w]一定为true */all[v] = new DirectedDFS(G, v);}}public boolean reachable(int v, int w) {return all[v].marked(w);}}

3.3. 最小生成树

给定一副加权无向图，找到它的一棵最小生成树

图的生成树是它的一棵含有其所有顶点的无环连通子图。

最小生成树【MST】是一棵权值之和最小（成本最小）的生成树。

3.3.1 一些约定

• 只考虑连通图
• 边的权重不一定表示距离
• 边的权重可能是0或者负数
• 所有边的权重各不相同

3.3.2 原理

反证法

3.3.3 切分定理下的贪心算法

切分定理是解决最小生成树问题的所有算法的基础

这些都是贪心算法的特殊情况：使用切分定理找到最小生成树的一条边，不断重复直到找到所有边

一棵树【tree】的特点：V个顶点有V-1条边

3.3.4 Prim算法

数据结构

• 顶点：marked[]数组
• 边：Edge对象
• 横切边：最小优先队列MinPQ

3.3.4.1 延时实现

每当我们向树中添加了一条边之后，也向树中添加了一个顶点

将连接这个顶点和其他不再树中顶点的边加入优先队列

两端顶点都在树中的边已经失效了（防止环的出现）

延时的实现会将失效的边留在优先队列里

在添加了V个顶点之后（V-1条边），最小生成树就完成了

（优先队列中余下的项都是无效的，不需要再检查它们）

public class LazyPrimMST {private boolean[] marked;//顶点private Queue<Edge> mst;//边private MinPQ<Edge> pq;//横切边（包括最小的边）public LazyPrimMST(EdgeWeightedGraph G) {marked = new boolean[G.V()];mst = new Queue<Edge>();pq = new MinPQ<Edge>();visit(G, 0);while(!pq.isEmpty()) {Edge e = pq.delMin();//找到最小横切边int v = e.either();int w = e.other(v);/** *忽略无效边（形成环的边） */if(marked[v] && marked[w])continue;mst.enqueue(e);//最小生成树加入边/** * 访问未标记的顶点，将边放入优先队列中 */if(!marked[v])visit(G, v);if(!marked[w])visit(G, w);}}/** * 将顶点v连接的边加入优先队列中 */private void visit(EdgeWeightedGraph G, int v) {marked[v] = true;for(Edge w:G.adj(v)) {if(!marked[w.other(v)]) {//如果当前边没有被添加过【两个顶点未被全部标记】pq.insert(w);}}}public Iterable<Edge> mst(){return mst;}/** * 延迟计算权重 */public double weight() {double w = 0;for(int i=0; i<marked.length-1; i++) {Edge e = mst.dequeue();w += e.weight();mst.enqueue(e);}return w;}}

3.3.4.2 即时实现

基本思路是：

• 从一个根节点出发，每一个找到一条与当前树相连（且不在树中）的权值最小的边**(也就是最短的横切边)**
• 将该边加入树中
• 反复执行该过程，直到N个顶点全部被标记完成

---

顶点索引的edgeTo[]和distTo[]数组

它们具有如下性质：

如果顶点v不在树中，但是至少一条边和树相连，那么edgeTo[v]是与v相连的最短的边，distTo[v]为该边的权重

所有的这类顶点v都保存在最小优先队列中

算法处理的过程：

• 首先从优先队列中取出权值最小的边
• 检查每条边v—w，如果w已经标记过了，则什么也不做
• 否则， 如果当前边已经存在与优先队列中并且小于当前队列中的数值，更新它的值**（说明到w点还有距离更短的边）**
• 如果不在优先队列中，添加它
  

  

【思考】

为什么每次都能找到与当前树相连的权重最小的边呢？————优先队列

public class PrimMST {private Edge[] edgeTo; // 距离当前树权重最小的边private double[] distTo;// weight[w] = edgeTo[w].weight()private boolean[] marked;// 如果v在树种则为trueprivate IndexMinPQ<Double> pq;// 有效边的横切边public PrimMST(EdgeWeightedGraph G) {edgeTo = new Edge[G.V()];distTo = new double[G.V()];marked = new boolean[G.V()];pq = new IndexMinPQ<Double>(G.V());for (int v = 0; v < G.V(); v++) {distTo[v] = Double.POSITIVE_INFINITY;}distTo[0] = 0.0;pq.insert(0, 0.0); // 初始化最小优先队列while (!pq.isEmpty()) { // 将与树相连的最小权重边加入树中visit(G, pq.delMin());}}/** * 将顶点加到树中，更新数据 */private void visit(EdgeWeightedGraph G, int v) {marked[v] = true;for (Edge e : G.adj(v)) {if (marked[e.other(v)])continue; // 一条边的两个顶点都被标记过，则什么也不做if (e.weight() < distTo[e.other(v)]) {//如果当前边小于优先队列中到这个点的距离edgeTo[e.other(v)] = e;distTo[e.other(v)] = e.weight();if (pq.contains(e.other(v))) {//若不再优先队列中，添加进去pq.changeKey(e.other(v), distTo[e.other(v)]);} else {//否则，更新它pq.insert(e.other(v), e.weight());}}}}}

3.3.5 Kruskal算法

将边按照权重排序

依次选择权重最小的边加入（前提：不形成环）

选择的边由森林逐渐形成树

Prim是由一条边一条边地构成一棵树，从一个根节点开始，每一步不断添加一条边

Kruskal是由不同的边，它的边会连接成森林，最终连成一棵树

public class KruskalMST {private Queue<Edge> mst;public KruskalMST(EdgeWeightedGraph G) {mst = new Queue<Edge>();MinPQ<Edge> pq = new MinPQ<Edge>((Comparator<Edge>) G.edges());UF uf = new UF(G.V());while (mst.size() < G.V() - 1 && !pq.isEmpty()) {Edge e = pq.delMin(); // 找到权重最小的边int v = e.either();int w = e.other(v);if (uf.connected(v, w))continue; // 如果在找到一条边的两个端点已经在一个连通分量上，说明这条边的连接必定会形成环uf.union(v, w);mst.enqueue(e);}}}

Kruskal算法比Prim算法要慢一些，两个算法都需要对每条边进行优先队列操作

Kruskal算法还需要进行依次union操作（连接两个点形成一个连通分量）

3.4. 最短路径

3.4.1 定义

从顶点s到顶点t的最短路径是所有从s到t的路径中权重最小的

3.4.2 性质

• 路径是有向的
• 并不是所有顶点都是可达的
• 负权重会使问题变复杂
• 最短路径一般都是简单图
• 最短路径不一定是唯一的
• 可能存在平行边和自环

3.4.3 最短路径树

最短路径问题，最后会给出一个根节点为起点s的最短路径树，它包含了s到所有可达顶点的最短路径

3.4.4 有向加权边API

public class DirectedEdge {private final int v; // 顶点之一private final int w; // 另一个顶点private final double weight; // 权重public DirectedEdge(int v, int w, double weight) {this.v = v;this.w = w;this.weight = weight;}public double weight() {return weight;}public int from() {return v;}public int to() {return w;}}

3.4.5 有向加权图API

public class EdgeWeightedDigraph {private final int V;// 顶点总数private int E;// 边总数private Bag<DirectedEdge>[] adj;// 邻接表public EdgeWeightedDigraph(int V) {this.V = V;adj = (Bag<DirectedEdge>[]) new Bag[V];for (int v = 0; v < V; v++) {adj[v] = new Bag<DirectedEdge>();}}public int V() {return V;}public int E() {return E;}public void addEdge(DirectedEdge e) {adj[e.from()].add(e);// 有向图，只需要加入一条边E++;}public Iterable<DirectedEdge> adj(int v) {return adj[v];}/** * 返回加权有向图的所有边 */public Iterable<DirectedEdge> edges() {Bag<DirectedEdge> b = new Bag<DirectedEdge>();for (int v = 0; v < V; v++) {for (DirectedEdge e : adj[v]) {b.add(e);}}return b;}}

不同于无向图，在加权有向图中，每条边在邻接表中仅出现一次

3.4.6 边的松弛【relax】

我们的最短路径算法的实现都是基于一个叫做松弛【relax】的操作进行的

在遇到新的边v——>w时，需要进行松弛操作：

• 如果dist[w] <= dist[v] + e.weight()：

  则说明到s到w的路径和不大于从s到v再从v到w的路径和，那么v——>w这条边就失效了（不选择这条边）

• 如果dist[w] > dist[v] + e.weight()：

  更新dist[w]的值

/*边的松弛*/public void relax(DirectedEdge e){ int v = e.from(); int w = e.to(); if(dist[v] + e.weight() < dist[w]){ dist[w] = dist[v] + e.weight();//更新成更小的权重和 edgeTo[w] = e;//更新到w的边，之前的边会被替换为新边e }}

放松一条边就类似于：

将橡皮筋转移到一条更短的路径上，从而放松了较长边的压力

3.4.7 顶点的松弛

对于每一个顶点，我们会遍历所有顶点的邻边，并对所有邻接边进行松弛操作

因为，在最短路径中，每一个顶点有且只有一条边连接到它（前提：从源点可达）

/*顶点的松弛*/public void relax(EdgeWeightedDigraph G, int v){ for(DirectedEdge e : G.adj[v]){ int w = e.to(); if(dist[w] > dist[v] + e.weight()){ dist[w] = dist[v] + e.weight();//更新成更小的权重和 edgeTo[w] = e;//更新到w的边，之前的边会被替换为新边e } }}

3.4.9 Dijkstra算法

回忆一下Prim算法：每一次向树中添加一条边

Dijkstra算法也是采用了类似的方法

• 首先将dist[s]初始化为0
• dist[]中其他的元素初始化为正无穷（即不可达）
• 然后将dist[]中最小的非树顶点进行松弛操作，并加入树中
• 如此这般直到所有顶点都在树中，或者非树顶点为正无穷（即完成算法，或者某些顶点不可达）

另外，dijkstra算法在对边的松弛时，需要处理两种情况：

如果边的to()不在优先队列中，添加进pq

如果已在优先队列中，需要降低优先级

3.4.9.1 实现

public class DijkstraSP {private DirectedEdge[] edgeTo;private double[] distTo;private IndexMinPQ<Double> pq;public DijkstraSP(EdgeWeightedDigraph G, int s) {edgeTo = new DirectedEdge[G.V()];distTo = new double[G.V()];pq = new IndexMinPQ<Double>(G.V());//将所有边到起点的距离初始化为正无穷for (int v = 0; v < G.V(); v++) {distTo[v] = Double.POSITIVE_INFINITY;}distTo[s] = 0.0;pq.insert(s, 0.0);while(!pq.isEmpty()) {relax(G, s);//对所有顶点进行松弛操作}}/** * 顶点的松弛操作 * 1. 如果边的to()不在优先队列中，添加进pq * 2. 如果已在优先队列中，需要降低优先级 */private void relax(EdgeWeightedDigraph G, int v) {for(DirectedEdge e : G.adj(v)){ int w = e.to(); if(distTo[w] > distTo[v] + e.weight()){ distTo[w] = distTo[v] + e.weight();//更新成更小的权重和 edgeTo[w] = e;//更新到w的边，之前的边会被替换为新边e if(pq.contains(w))pq.change(w, e.weight()); elsepq.insert(w, e.weight()); } }}}

dijkstra算法是每一次往树中添加一条边，该边是由树中的顶点指向非树中的顶点w，且是到s最近的点

该算法可以找到给定两点的最短路径

3.4.9.2 时间复杂度

在一副有V个顶点和E条边的加权有向图，时间与ElogV成正比（最坏情况下）

但是，对于有负权重的加权有向图中的最短路径问题，dijkstra算法无法完成这类问题

【问题】：（未答）

为什么dijkstra算法无法解决带负权重问题呢？

3.4.10 无环加权有向图的最短路径算法

特点：

• 能够在线性时间解决单点最短路径
• 能够处理负权重的边
• 能够解决相关的问题，例如找出最长的路径

只要将顶点的放松和拓扑排序结合起来，马上就能够得到一种解决无环加权有向图中的最短路径的算法

3.4.11 解决负权重的最短路径算法

Bellman-ford算法

时间复杂度 O ( V E ) O(VE) O(VE)

（后续跟进）

4 数据压缩

4.1 原因

主要是节省空间以及减少传输的时间

4.2 热身：基因组

一般而言，生物学家用字母A,C,G,T表示生物体DNA中的碱基。

但是上面这一串字符串一共有35个，每一个字符使用ASCII编码的话（8位），那么一共就是8*35 = 280位

4.2.1 压缩

不难看出，DNA碱基的字符串一共只有4个字符来组成，那么我们可以使用2位比特编码方式（ 2 2 = 4 2^2 = 4 22=4种）

4.3 游程编码【Run-Length Encoding】

比特流中最常见的就是一长串重复的比特

游程编码的一个应用就是位图：

4.4 哈夫曼压缩

主要思想：

放弃文本保存的普通方式，用更短的比特保存出现频率较高的字符，用较多的比特保存出现频率较低的字符

简而言之，利用频率信息压缩数据

4.4.1 寻找最优前缀码

在这里插入图片描述

能否找到使得比特流最小的单词查找树？

——————哈夫曼编码

使用前缀码进行数据压缩需要进行五个步骤：

构造一棵编码单词查找树

将该树以字节流的形式写入输出，以便展开时使用

使用该树，将字节流编码为比特流

在展开时需要：

读取单词查找树（保存在比特流的开头）

使用该树将比特流解码

下面将按照难度逐步考察

4.4.2 单词查找树的节点

其中还有两个新的变量：

• ch————表示叶子节点上的字符
• freq————叶子节点：当前字符在输入中出现频率；内部节点：两个子节点频率之和；根节点的频率 = 字符的数量

4.4.3 展开

展开的过程十分简单：从根节点开始移动，读到0——左移，1——右移

如果到达了叶子节点x，直接输出x.ch

4.4.4 单词查找树的构造

以下面的输入为例观察一棵单词查找树的构造过程：

it was the best of times it was the worst of times

首先，我们需要将需要编码的字符都放置于叶子节点，并记录每个字符在原文中出现的频率

在本例中，有8个t，5个e，11个空格等

【注】：

需要得到这些频率，需要扫描一遍输入流————哈夫曼编码是一个两轮算法，需要预先读取输入流后再压缩

接下来，将按照频率大小构造这个单词查找树

构造过程如下：

首先找到两个频率最小的节点，创建一个以两者作为子节点的新节点（新节点的频率 = 两子节点之和）

这个操作，会使森林中的树的数量-1

然后不断重复这个过程

问题来了，如何才能知道频率最小的节点呢？————优先队列

按照这样一个过程构造的单词查找树最终一定是：

• 频率较低的节点被安排在底层

• 频率较高的节点被安排在靠近根节点的位置

/**构造哈夫曼编码单词查找树**/private static Node buildTree(int[] freq){ //将要编码的字符插入优先队列 MinPQ<Node> pq = new MinPQ<Node>(); for(char = 0; c < R; c++){ if(freq[c] > 0) pq.insert(new Node(c, freq[c], null, null)); } //构造单词查找树 while(pq.size() > 1){ Node x = pq.delMin(); Node y = pq.delMin(); Node parent = new Node('\0', freq[x]+freq[y], x, y); pq.insert(parent); } //返回根节点 return pq.delMin(); }

4.4.5 构造编译表

使用递归方法构造编译表

private static String[] buildCode(Node root){ String[] st = new String[R]; buildCode(st, root, ""); }private static String[] buileCode(String[] st, Node x, String s){ if(x.isLeaf()){//如果是叶子节点，x.ch写入编译表 st[x.ch] = s; return; } buileCode(st, x.left, s+'0'); buileCode(st, x.right, s+'1'); }

4.5 LZW压缩算法

（后续跟进）