普林斯顿算法讲义（二）（4）

普林斯顿算法讲义（二）（3）https://developer.aliyun.com/article/1484175

网络练习

1. 假设我们希望重复搜索一个长度为 N 的链表，每个元素都包含一个非常长的字符串键。在搜索具有给定键的元素时，我们如何利用哈希值？ 解决方案：预先计算列表中每个字符串的哈希值。在搜索键 t 时，将其哈希值与字符串 s 的哈希值进行比较。只有在它们的哈希值相等时才比较字符串 s 和 t。
   
2. 为以下数据类型实现hashCode()和equals()。要小心，因为很可能许多点的 x、y 和 z 都是小整数。

public class Point2D {
    private final int x, y;
    ...
}

1. 答案：一个解决方案是使哈希码的前 16 位是 x 的前 16 位和 y 的后 16 位的异或，将哈希码的后 16 位是 x 的后 16 位和 y 的前 16 位的异或。因此，如果 x 和 y 只有 16 位或更少，那么不同点的 hashCode 值将不同。
2. 以下点的equals()实现有什么问题？

public boolean equals(Point q) {
    return x == q.x && y == q.y;
}

1. equals()的错误签名。这是equals()的重载版本，但它没有覆盖从Object继承的版本。这将破坏任何使用Point与HashSet的代码。这是更常见的错误之一（与在覆盖equals()时忽略覆盖hashCode()一样）。
2. 以下代码片段将打印什么？

import java.util.HashMap;
import java.util.GregorianCalendar;
HashMap st = new HashMap<gregoriancalendar string="">();
GregorianCalendar x = new GregorianCalendar(1969, 21, 7);
GregorianCalendar y = new GregorianCalendar(1969, 4, 12);
GregorianCalendar z = new GregorianCalendar(1969, 21, 7);
st.put(x, "human in space");
x.set(1961, 4, 12);
System.out.println(st.get(x));
System.out.println(st.get(y));
System.out.println(st.get(z));</gregoriancalendar> 

1. 它将打印 false，false，false。日期 7/21/1969 被插入到哈希表中，但在哈希表中的值被更改为 4/12/1961。因此，尽管日期 4/12/1961 在哈希表中，但在搜索 x 或 y 时，我们将在错误的桶中查找，找不到它。我们也找不到 z，因为日期 7/21/1969 不再是哈希表中的键。
   这说明在哈希表的键中只使用不可变类型是一个好习惯。Java 设计者可能应该使GregorianCalendar成为一个不可变对象，以避免出现这样的问题。
2. 密码检查器。 编写一个程序，从命令行读取一个字符串和从标准输入读取一个单词字典，并检查它是否是一个“好”密码。在这里，假设“好”意味着它（i）至少有 8 个字符长，（ii）不是字典中的一个单词，（iii）不是字典中的一个单词后跟一个数字 0-9（例如，hello5），（iv）不是由一个数字分隔的两个单词（例如，hello2world）。
   
3. 反向密码检查器。 修改前一个问题，使得（ii）-（v）也适用于字典中单词的反向（例如，olleh 和 olleh2world）。巧妙的解决方案：将每个单词及其反向插入符号表。
   
4. 镜像网站。 使用哈希来确定哪些文件需要更新以镜像网站。
   
5. 生日悖论。 假设您的音乐点播播放器随机播放您的 4000 首歌曲（带替换）。您期望等待多久才能听到一首歌曲第二次播放？
   
6. 布隆过滤器。 支持插入、存在。通过允许一些误报来使用更少的空间。应用：ISP 缓存网页（特别是大图像、视频）；客户端请求 URL；服务器需要快速确定页面是否在缓存中。解决方案：维护一个大小为 N = 8M（M = 要插入的元素数）的位数组。从 0 到 N-1 选择 k 个独立的哈希函数。
   
7. CRC-32。 哈希的另一个应用是计算校验和以验证某个数据文件的完整性。要计算字符串 s 的校验和，

import java.util.zip.CRC32;
...
CRC32 checksum = new CRC32();
checksum.update(s.getBytes());
System.out.println(checksum.getValue());

1. 完美哈希。 另请参见 GNU 实用程序 gperf。
   
2. 密码学安全哈希函数。 SHA-1 和 MD5。可以通过将字符串转换为字节或每次读取一个字节时计算它。程序 OneWay.java 演示了如何使用 java.security.MessageDigest 对象。
   
3. 指纹。 哈希函数（例如，MD5 和 SHA-1）也可用于验证文件的完整性。将文件哈希为一个短字符串，将字符串与文件一起传输，如果传输文件的哈希与哈希值不同，则数据已损坏。
   
4. 布谷鸟哈希。 在均匀哈希的最大负载下为 log n / log log n。通过选择两者中负载最小的来改进为 log log n。（如果选择 d 中负载最小的，则仅改进为 log log n / log d。）布谷鸟哈希 实现了常数平均插入时间和常数最坏情况搜索：每个项目有两个可能的插槽。如果空，则放入两个可用插槽中的任一个；如果不是，则将另一个插槽中的另一个项目弹出并移动到其另一个插槽中（并递归）。"这个名字来源于一些布谷鸟物种的行为，母鸟将蛋推出另一只鸟的巢来产卵。"如果进入重新定位循环，则重新散列所有内容。
   
5. 协变等于。 CovariantPhoneNumber.java 实现了一个协变的 equals() 方法。
   
6. 后来者先服务线性探测。 修改 LinearProbingHashST.java，使得每个项目都插入到它到达的位置；如果单元格已经被占用，则该项目向右移动一个条目（规则重复）。
   
7. 罗宾汉线性探测。 修改 LinearProbingHashST.java，使得当一个项目探测到已经被占用的单元格时，当前位移较大的项目（两者中的一个）获得单元格，另一个项目向右移动一个条目（规则重复）。
   
8. 冷漠图。 给定实线上的 V 个点，其冷漠图是通过为每个点添加一个顶点并在两个顶点之间添加一条边形成的图，当且仅当两个对应点之间的距离严格小于一时。设计一个算法（在均匀哈希假设下），以时间比��于 V + E 计算一组 V 点的冷漠图。
   解决方案. 将每个实数向下取整到最近的整数，并使用哈希表来识别所有向同一整数取整的点。现在，对于每个点 p，使用哈希表找到所有向 p 的取整值内的整数取整的点，并为距离小于一的每对点添加一条边(p, q)。参见此参考链接以了解为什么这需要线性时间。
   

3.5 搜索应用

原文：algs4.cs.princeton.edu/35applications

译者：飞龙

协议：CC BY-NC-SA 4.0

本节正在大规模施工中。

从计算机的早期时代，当符号表允许程序员从在机器语言中使用数值地址进展到在汇编语言中使用符号名称，到新千年的现代应用，当符号名称在全球计算机网络中具有意义时，快速搜索算法在计算中发挥了并将继续发挥重要作用。符号表的现代应用包括组织科学数据，从在基因组数据中搜索标记或模式到绘制宇宙；在网络上组织知识，从在线商务搜索到将图书馆放在线；以及实现互联网基础设施，从在网络上的机器之间路由数据包到共享文件系统和视频流。

集合 API。

一些符号表客户端不需要值，只需要将键插入表中并测试键是否在表中。由于我们不允许重复键，这些操作对应于以下 API，我们只对表中的键集感兴趣。

为了说明 SET.java 的用途，我们考虑过滤客户端，从标准输入读取一系列键，并将其中一些写入标准输出。

• *去重。*程序 DeDup.java 从输入流中删除重复项。
  
• 白名单和黑名单过滤。另一个经典示例，使用单独的文件中的键来决定哪些来自输入流的键传递到输出流。程序 AllowFilter.java 实现了白名单，其中文件中的任何键都会传递到输出，而文件中没有的键将被忽略。程序 BlockFilter.java 实现了黑名单，其中文件中的任何键都将被忽略，而文件中没有的键将传递到输出。
  

字典客户端。

最基本的符号表客户端通过连续的put操作构建符号表，以支持get请求。下面列举的熟悉示例说明了这种方法的实用性。

作为一个具体的例子，我们考虑一个符号表客户端，您可以使用它查找使用逗号分隔值（.csv）文件格式保存的信息。LookupCSV.java 从命令行指定的逗号分隔值文件中构建一组键值对，然后打印出与从标准输入读取的键对应的值。命令行参数是文件名和两个整数，一个指定用作键的字段，另一个指定用作值的字段。

索引客户端。

这个应用是符号表客户端的另一个典型示例。我们有大量数据，想知道感兴趣的字符串出现在哪里。这似乎是将多个值与每个键关联起来，但实际上我们只关联一个SET。FileIndex.java 将一系列文件名作为命令行参数，并构建一个符号表，将每个关键字与可以找到该关键字的文件名的SET关联起来。然后，它从标准输入接受关键字查询。

MovieIndex.java 读取一个包含表演者和电影的数据文件。

稀疏向量和矩阵。

程序 SparseVector.java 使用索引-值对的符号表实现了一个稀疏向量。内存与非零数目成比例。set和get操作在最坏情况下需要 log n 时间；计算两个向量的点积所需的时间与两个向量中的非零条目数成比例。

系统符号表。

Java 有几个用于集合和符号表的库函数。API 类似，但你可以将null值插入符号表。

• TreeMap 库使用红黑树。保证每次插入/搜索/删除的性能为 log N。他们的实现为每个节点维护三个指针（两个子节点和父节点），而我们的实现只存储两个。
  
• Sun 在 Java 1.5 中的HashMap实现使用具有分离链接的哈希表。表大小为 2 的幂（而不是素数）。这用 AND 替换了相对昂贵的% M 操作。默认负载因子= 0.75。为防止一些编写不佳的哈希函数，他们对hashCode应用以下混淆例程。

static int hash(Object x) {
   int h = x.hashCode();
   h += ~(h <<   9);
   h ^=  (h >>> 14);
   h +=  (h <<   4);
   h ^=  (h >>> 10);
   return h;
}

Q + A

Q. 运行性能基准测试时，插入、搜索和删除操作的合理比例是多少？

A. 这取决于应用程序。Java 集合框架针对大约 85%的搜索/遍历，14%的插入/更新和 1%的删除进行了优化。

练习

创意练习

1. 词汇表。 编写一个 ST 客户端 Concordance.java，在标准输出中输出标准输入流中字符串的词汇表。
   
2. 稀疏矩阵。 为稀疏 2D 矩阵开发一个 API 和一个实现。支持矩阵加法和矩阵乘法。包括行和列向量的构造函数。
   解决方案：SparseVector.java 和 SparseMatrix.java。
   

网页练习

1. 修改FrequencyCount以读取一个文本文件（由 UNICODE 字符组成），并打印出字母表大小（不同字符的数量）和一个按频率降序排序的字符及其频率表。
   
2. 集合的交集和并集。 给定两组字符串，编写一个代码片段，计算一个包含这两组中出现的字符串的第三组（或任一组）。
   
3. 双向符号表。 支持 put(key, value)和 getByKey(key)或 getByValue(value)。在幕后使用两个符号表。例如：DNS 和反向 DNS。
   
4. 突出显示浏览器超链接。 每次访问网站时，保留上次访问网站的时间，这样你只会突出显示那些在过去一个月内访问过的网站。
   
5. 频率符号表。 编写一个支持以下操作的抽象数据类型 FrequencyTable.java：hit(Key)和count(Key)。hit操作将字符串出现的次数增加一。count操作返回给定字符串出现的次数，可能为 0。应用：网页计数器，网页日志分析器，音乐点播机统计每首歌曲播放次数等。
   
6. 非重叠区间搜索。 给定一个非重叠整数（或日期）区间列表，编写一个函数，接受一个整数参数，并确定该值位于哪个（如果有）区间中，例如，如果区间为 1643-2033、5532-7643、8999-10332、5666653-5669321，则查询点 9122 位于第三个区间，8122 不在任何区间中。
   
7. 注册调度。 一所东北部知名大学的注册处最近安排一名教师在完全相同的时间上教授两门不同的课程。通过描述一种检查此类冲突的方法来帮助注册处避免未来的错误。为简单起见，假设所有课程从 9 点开始，每门课程持续 50 分钟，时间分别为 9、10、11、1、2 或 3。
   
8. 列表。 实现以下列表操作：size()、addFront(item)、addBack(item)、delFront(item)、delBack(item)、contains(item)、delete(item)、add(i, item)、delete(i)、iterator()。所有操作应高效（对数时间）。提示：使用两个符号表，一个用于高效查找列表中的第 i 个元素，另一个用于按项目高效搜索。Java 的 List 接口包含这些方法，但没有提供支持所有操作高效的实现。
   
9. 间接 PQ。 编写一个实现间接 PQ 的程序 IndirectPQ.java。
   
10. LRU 缓存。 创建一个支持以下操作的数据结构：access和remove。访问操作将项目插入到数据结构中（如果尚未存在）。删除操作删除并返回最近访问的项目。提示：在双向链表中按访问顺序维护项目，并在符号表中使用键=项目，值=链表中的位置。当访问一个元素时，从链表中删除它并重新插入到开头。当删除一个元素时，从末尾删除它并从符号表中删除它。
    
11. UniQueue. 创建一个数据类型，它是一个队列，但是一个元素只能被插入队列一次。使用存在性符号表来跟踪所有曾经被插入的元素，并忽略重新插入这些项目的请求。
    
12. 带随机访问的符号表。 创建一个支持插入键值对、搜索键并返回关联值、删除并返回随机值的数据类型。提示：结合符号表和随机队列。
    
13. 纠正拼写错误。 编写一个程序，从标准输入中读取文本，并用建议的替换替换任何常见拼写错误的单词，并将结果打印到标准输出。使用这个常见拼写错误列表（改编自Wikipedia）。
    
14. 移至前端。 编码：需要排名查询、删除和插入。解码：需要查找第 i 个、删除和插入。
    
15. 可变字符串。 创建一个支持字符串上述操作的数据类型：get(int i)、insert(int i, char c)和delete(int i)，其中get返回字符串的第 i 个字符，insert插入字符 c 并使其成为第 i 个字符，delete删除第 i 个字符。使用二叉搜索树。
    提示：使用 BST（键=0 到 1 之间的实数，值=字符）使得树的中序遍历产生适当顺序的字符。使用select()找到第 i 个元素。在位置 i 插入字符时，选择实数为当前位置 i-1 和 i 的键的平均值。
    
16. 幂法和最大特征值。要计算具有最大幅度的特征值（及相应的特征向量），请使用幂法。在技术条件下（最大两个特征值之间的差距），它会迅速收敛到正确答案。

• 进行初始猜测 x[1]
  
• y[n] = x[n] / ||x[n]||
  
• x[n+1] = A y[n]
  
• λ = x[n+1]^T y[n]
  
• n = n + 1 如果 A 是稀疏的，那么这个算法会利用稀疏性。例如：Google PageRank。
  

17. 外积。 向Vector添加一个方法outer，使得a.outer(b)返回两个长度为 N 的向量 a 和 b 的外积。结果是一个 N×N 矩阵。
    
18. 网络链接的幂律分布。（Michael Mitzenmacher）全球网络的入度和出度遵循幂律分布。可以通过优先附加过程来建模。假设每个网页只有一个外链。每个页面逐一创建，从指向自身的单个页面开始。以概率 p < 1，它将链接到现有页面之一，随机选择。以概率 1-p，它将链接到现有页面，概率与该页面的入链数成比例。这一规则反映了新网页倾向于指向热门页面的普遍趋势。编写一个程序来模拟这个过程，并绘制入链数的直方图。
    
19. VMAs. Unix 内核中用于管理一组虚拟内存区域（VMAs）的 BST。每个 VMA 代表 Unix 进程中的一部分内存。VMAs 的大小从 4KB 到 1GB 不等。还希望支持范围查询，以确定哪些 VMAs 与给定范围重叠。参考资料
    
20. **互联网对等缓存。**由互联网主机发送的每个 IP 数据包都带有一个必须对于该源-目的地对是唯一的 16 位 ID。Linux 内核使用以 IP 地址为索引的 AVL 树。哈希会更快，但希望避免攻击者发送具有最坏情况输入的 IP 数据包。参考资料
    
21. 文件索引变体。

• 移除停用词，例如，a，the，on，of。使用另一个集合来实现。
  
• 支持多词查询。这需要进行集合交集操作。如果总是先与最小集合进行交集，那么这将花费与最小集合大小成正比的时间。
  
• 实现 OR 或其他布尔逻辑。
  
• 记录文档中单词的位置或单词出现的次数。
  

22. **算术表达式解释器。**编写一个程序 Interpreter.java 来解析和评估以下形式的表达式。

>> x := 34
x := 34.0
>> y := 23 * x    
y := 782.0
>> z := x ^ y
z := Infinity
>> z := y ^ 2
z := 611524.0
>> x
x := 34.0
>> x := sqrt 2
x := 1.4142135623730951

1. 变体。

• 添加更复杂的表达式，例如，z = 7 * (x + y * y)，使用传统的运算符优先级。
  
• 添加更多的错误检查和恢复。
  

4. 图

原文：algs4.cs.princeton.edu/40graphs

译者：飞龙

协议：CC BY-NC-SA 4.0

概述。

项目之间的成对连接在大量计算应用程序中起着至关重要的作用。这些连接所暗示的关系引发了一系列自然问题：是否有一种方法可以通过遵循这些连接将一个项目连接到另一个项目？有多少其他项目连接到给定项目？这个项目和另一个项目之间的连接的最短链是什么？下表展示了涉及图处理的各种应用程序的多样性。

我们逐步介绍了四种最重要的图模型：无向图（具有简单连接），有向图（其中每个连接的方向很重要），带权重的图（其中每个连接都有一个相关联的权重），以及带权重的有向图（其中每个连接都有方向和权重）。

• 4.1 无向图介绍了图数据类型，包括深度优先搜索和广度优先搜索。
  
• 4.2 有向图介绍了有向图数据类型，包括拓扑排序和强连通分量。
  
• 4.3 最小生成树描述了最小生成树问题以及解决它的两种经典算法：Prim 算法和 Kruskal 算法。
  
• 4.4 最短路径介绍了最短路径问题以及解决它的两种经典算法：Dijkstra 算法和 Bellman-Ford 算法。
  

本章中的 Java 程序。

下面是本章中的 Java 程序列表。单击程序名称以访问 Java 代码；单击参考号以获取简要描述；阅读教科书以获取详细讨论。

4.1 无向图

原文：algs4.cs.princeton.edu/41graph

译者：飞龙

协议：CC BY-NC-SA 4.0

图。

图是一组顶点和连接一对顶点的边的集合。我们在 V-1 个顶点的图中使用 0 到 V-1 的名称表示顶点。

术语表。

这里是我们使用的一些定义。

• 自环是连接顶点与自身的边。
  
• 如果它们连接相同的一对顶点，则两条边是平行的。
  
• 当一条边连接两个顶点时，我们说这两个顶点相邻，并且该边关联这两个顶点。
  
• 一个顶点的度是与其关联的边的数量。
  
• 子图是构成图的边（和相关顶点）的子集，构成一个图。
  
• 图中的路径是由边连接的顶点序列，没有重复的边。
  
• 一个简单路径是一个没有重复顶点的路径。
  
• 循环是一条路径（至少有一条边），其第一个和最后一个顶点相同。
  
• 简单循环是一个没有重复顶点（除了第一个和最后一个顶点必须重复）的循环。
  
• 一条路径或循环的长度是其边的数量。
  
• 如果存在包含它们两者的路径，则我们说一个顶点连接到另一个顶点。
  
• 如果从每个顶点到每个其他顶点都存在路径，则图是连通的。
  
• 一个非连通的图由一组连通分量组成，这些连通分量是最大连通子图。
  
• 无环图是一个没有循环的图。
  
• 树是一个无环连通图。
  
• 森林是一组不相交的树。
  
• 连通图的生成树是包含该图所有顶点且为单棵树的子图。图的生成森林是其连通分量的生成树的并集。
  
• 二分图是一个我们可以将其顶点分为两组的图，使得所有边连接一组中的顶点与另一组中的顶点。
  

无向图数据类型。

我们实现以下无向图 API。

关键方法adj()允许客户端代码迭代给定顶点相邻的顶点。值得注意的是，我们可以在adj()所体现的基本抽象上构建本节中考虑的所有算法。

我们准备了测试数据 tinyG.txt、mediumG.txt 和 largeG.txt，使用以下输入文件格式。

图客户端.java 包含典型的图处理代码。

图表示。

我们使用邻接表表示法，其中我们维护一个以顶点索引的数组，数组中的每个元素是与每个顶点通过边连接的顶点的列表。

图.java 使用邻接表表示法实现了图 API。邻接矩阵图.java 使用邻接矩阵表示法实现了相同的 API。

深度优先搜索。

深度优先搜索是一种经典的递归方法，用于系统地检查图中的每个顶点和边。要访问一个顶点

• 将其标记为已访问。
  
• 访问（递归地）所有与其相邻且尚未标记的���点。
  

深度优先搜索.java 实现了这种方法和以下 API：

寻找路径。

修改深度优先搜索以确定两个给定顶点之间是否存在路径以及找到这样的路径（如果存在）。我们试图实现以下 API：

为了实现这一点，我们通过将edgeTo[w]设置为v来记住将我们带到每个顶点w的边缘v-w，这是第一次。换句话说，v-w是从源到w的已知路径上的最后一条边。搜索的结果是以源为根的树；edgeTo[]是该树的父链接表示。深度优先路径.java 实现了这种方法。

广度优先搜索。

深度优先搜索找到从源顶点 s 到目标顶点 v 的一条路径。我们经常有兴趣找到最短这样的路径（具有最小数量的边）。广度优先搜索是基于这个目标的经典方法。要从s到v找到最短路径，我们从s开始，并在我们可以通过一条边到达的所有顶点中检查v，然后我们在我们可以通过两条边从s到达的所有顶点中检查v，依此类推。

要实现这种策略，我们维护一个队列，其中包含所有已标记但其邻接列表尚未被检查的顶点。我们将源顶点放入队列，然后执行以下步骤，直到队列为空：

• 从队列中移除下一个顶点v。
  
• 将所有未标记的与v相邻的顶点放入队列并标记它们。
  

广度优先路径.java 是实现Paths API 的一个实现，用于找到最短路径。它依赖于 FIFO 队列.java。

连通分量。

我们下一个直接应用深度优先搜索的是找到图的连通分量。回想一下第 1.5 节，“连接到”是将顶点划分为等价类（连通分量）的等价关系。对于这个任务，我们定义以下 API：

CC.java 使用 DFS 实现此 API。

命题。 DFS 在时间上标记与给定源连接的所有顶点，其时间与其度数之和成正比，并为客户提供从给定源到任何标记顶点的路径，其时间与其长度成正比。

**命题。**对于从s可达的任何顶点v，BFS 计算从s到v的最短路径（从s到v没有更少的边的路径）。在最坏情况下，BFS 花费时间与 V + E 成正比。

命题。 DFS 使用预处理时间和空间与 V + E 成正比，以支持图中的常数时间连接查询。

更多深度优先搜索应用。

我们用 DFS 解决的问题是基础的。深度优先搜索还可以用于解决以下问题：

• *循环检测：*给定图是否无环？循环.java 使用深度优先搜索来确定图是否有循环，如果有，则返回一个。在最坏情况下，它花费时间与 V + E 成正比。
  
• *双色性：*给定图的顶点是否可以被分配为两种颜色，以便没有边连接相同颜色的顶点？二分图.java 使用深度优先搜索来确定图是否具有二��图；如果是，则返回一个；如果不是，则返回一个奇数长度的循环。在最坏情况下，它花费时间与 V + E 成正比。
  
• 桥： 桥（或割边）是一条删除后会增加连接组件数量的边。等价地，仅当边不包含在任何循环中时，边才是桥。桥.java 使用深度优先搜索在图中找到桥。在最坏情况下，它花费时间与 V + E 成正比。
  
• 双连通性：一个关节点（或割点）是一个移除后会增加连接组件数量的顶点。如果没有关节点，则图形是双连通的。Biconnected.java 使用深度优先搜索来查找桥梁和关节点。在最坏情况下，它的时间复杂度为 V + E。
  
• 平面性：如果可以在平面上绘制图形，使得没有边相互交叉，则图形是平面的。 Hopcroft-Tarjan 算法是深度优先搜索的高级应用，它可以在线性时间内确定图形是否是平面的。
  

符号图。

典型应用涉及使用字符串而不是整数索引来处理图形，以定义和引用顶点。为了适应这些应用程序，我们定义了具有以下属性的输入格式：

• 顶点名称是字符串。
  
• 指定的分隔符分隔顶点名称（以允许名称中包含空格的可能性）。
  
• 每行表示一组边，将该行上的第一个顶点名称连接到该行上命名的每个其他顶点。
  

输入文件 routes.txt 是一个小例子。

输入文件 movies.txt 是来自互联网电影数据库的一个更大的示例。该文件包含列出电影名称后跟电影中表演者列表的行。

• API。 以下 API 允许我们为这种输入文件使用我们的图处理例程。

• *实现。*SymbolGraph.java 实现了 API。它构建了三种数据结构：

• 一个符号表st，具有String键（顶点名称）和int值（索引）
  
• 一个作为反向索引的数组keys[]，给出与每个整数索引关联的顶点名称
  
• 使用索引构建的Graph G，以引用顶点
  

• *分离度。*DegreesOfSeparation.java 使用广度优先搜索来查找社交网络中两个个体之间的分离度。对于演员-电影图，它玩的是凯文·贝肯游戏。
  

练习

1. 为 Graph.java 创建一个复制构造函数，该构造函数以图G作为输入，并创建并初始化图的新副本。客户端对G所做的任何更改都不应影响新创建的图。
   
2. 向 BreadthFirstPaths.java 添加一个distTo()方法，该方法返回从源到给定顶点的最短路径上的边数。distTo()查询应在常数时间内运行。
   
3. 编写一个程序 BaconHistogram.java，打印凯文·贝肯号的直方图，指示 movies.txt 中有多少表演者的贝肯号为 0、1、2、3 等。包括那些具有无限号码的类别（与凯文·贝肯没有联系）。
   
4. 编写一个SymbolGraph客户端 DegreesOfSeparationDFS.java，该客户端使用深度优先而不是广度优先搜索来查找连接两个表演者的路径。
   
5. 使用第 1.4 节的内存成本模型确定Graph表示具有V个顶点和E条边的图所使用的内存量。
   解决方案。 56 + 40V + 128E。MemoryOfGraph.java 根据经验计算，假设没有缓��Integer值—Java 通常会缓存-128 到 127 之间的整数。
   

创意问题

1. **并行边检测。**设计一个线性时间算法来计算图中的平行边数。
   提示：维护一个顶点的邻居的布尔数组，并通过仅在需要时重新初始化条目来重复使用此数组。
   
2. 双边连通性。 在图中，桥是一条边，如果移除，则会将一个连通图分隔成两个不相交的子图。没有桥的图被称为双边连通。开发一个基于 DFS 的数据类型 Bridge.java，用于确定给定图是否是边连通的。
   

网页练习

1. 找一些有趣的图。它们是有向的还是无向的？稀疏的还是密集的？
   
2. 度。 顶点的度是与之关联的边的数量。向Graph添加一个方法int degree(int v)，返回顶点 v 的度数。
   
3. 假设在运行广度优先搜索时使用堆栈而不是队列。它仍然计算最短路径吗？
   
4. 使用显式堆栈的 DFS。 给出 DFS 可能出现堆栈溢出的示例，例如，线图。修改 DepthFirstPaths.java，使其使用显式堆栈而不是函数调用堆栈。
   
5. 完美迷宫。生成一个完美迷宫像这样的

1. 编写一个程序 Maze.java，它接受一个命令行参数 n，并生成一个随机的 n×n 完美迷宫。如果迷宫完美，则每对迷宫中的点之间都有一条路径，即没有无法访问的位置，没有循环，也没有开放空间。这里有一个生成这样的迷宫的好算法。考虑一个 n×n 的单元格网格，每个单元格最初与其四个相邻单元格之间都有一堵墙。对于每个单元格（x, y），维护一个变量north[x][y]，如果存在将（x, y）和（x, y + 1）分隔的墙，则为true。我们有类似的变量east[x][y]，south[x][y]和west[x][y]用于相应的墙壁。请注意，如果（x, y）的北面有一堵墙，则north[x][y] = south[x][y+1] = true。通过以下方式拆除一些墙壁来构建迷宫：

1. 从较低级别单元格（1, 1）开始。
   
2. 随机找到一个您尚未到达的邻居。
   
3. 如果找到一个，就移动到那里，拆除墙壁。如果找不到，则返回上一个单元格。
   
4. 重复步骤 ii.和 iii.，直到您访问了网格中的每个单元格。
   

2. 提示：维护一个(n+2)×(n+2)的单元格网格，以避免繁琐的特殊情况。
   这是由卡尔·埃克洛夫使用此算法创建的一个 Mincecraft 迷宫。

1. 走出迷宫。 给定一个 n×n 的迷宫（就像在前一个练习中创建的那样），编写一个程序，如果存在路径，则从起始单元格（1, 1）到终点单元格（n, n）找到一条路径。要找到迷宫的解决方案，请运行以下算法，从（1, 1）开始，并在到达单元格（n, n）时停止。

explore(x, y)
-------------
  - Mark the current cell (x, y) as "visited."
  - If no wall to north and unvisited, then explore(x, y+1).
  - If no wall to east and  unvisited, then explore(x+1, y).
  - If no wall to south and unvisited, then explore(x, y-1).
  - If no wall to west and  unvisited, then explore(x-1, y).

1. 迷宫游戏。 开发一个迷宫游戏，就像来自gamesolo.com的这个，您在其中穿过迷宫，收集奖品。
   
2. 演员图。 计算凯文·贝肯数的另一种（也许更自然）方法是构建一个图，其中每个节点都是一个演员。如果两个演员一起出现在一部电影中，则它们之间通过一条边连接。通过在演员图上运行 BFS 来计算凯文·贝肯数。比较与文本中描述的算法的运行时间。解释为什么文本中的方法更可取。答案：它避免了多个平行边。因此，它更快，使用的内存更少。此外，它更方便，因为您不必使用电影名称标记边缘-所有名称都存储在顶点中。
   
3. 好莱坞宇宙的中心。 我们可以通过计算他们的好莱坞数来衡量凯文·贝肯是一个多好的中心。凯文·贝肯的好莱坞数是所有演员的平均贝肯数。另一位演员的好莱坞数计算方式相同，但我们让他们成为源，而不是凯文·贝肯。计算凯文·贝肯的好莱坞数，并找到一个演员和一个女演员，他们的好莱坞数更好。
   
4. 好莱坞宇宙的边缘。 找到（与凯文·贝肯相连的）具有最高好莱坞数的演员。
   
5. 单词梯子。 编写一个程序 WordLadder.java，从命令行中获取两个 5 个字母的字符串，并从标准输入中读取一个 5 个字母的单词列表，然后打印出连接这两个字符串的最短单词梯子（如果存在）。如果两个单词在一个字母上不同，那么它们可以在一个单词梯子链中连接起来。例如，以下单词梯子连接了 green 和 brown。

green greet great groat groan grown brown

1. 你也可以尝试在这个 6 个字母单词列表上运行你的程序。
2. 更快的单词梯子。 为了加快速度（如果单词列表非常大），不要编写嵌套循环来尝试所有成对的单词是否相邻。对于 5 个字母的单词，首先对单词列表进行排序。只有最后一个字母不同的单词将在排序后的列表中连续出现。再排序 4 次，但将字母向右循环移动一个位置，以便在一个排序列表中连续出现在第 i 个字母上不同的单词。
   尝试使用一个更大的单词列表来测试这种方法，其中包含不同长度的单词。如果两个长度不同的单词���有最后一个字母不同，则它们是相邻的。
   
3. 假设你删除无向图中的所有桥梁。结果图的连通分量是否是双连通分量？答案：不是，两个双连通分量可以通过一个关节点连接。
   桥梁和关节点。
   桥梁（或割边）是一条移除后会断开图的边。关节点（或割点）是一个移除后（以及移除所有关联边后）会断开剩余图的顶点。桥梁和关节点很重要，因为它们代表网络中的单点故障。蛮力方法：删除边（或顶点）并检查连通性。分别需要 O(E(V + E))和 O(V(V + E))的时间。可以通过巧妙地扩展 DFS 将两者都改进为 O(E + V)。
   
4. 双连通分量。 一个无向图是双连通的，如果对于每一对顶点 v 和 w，v 和 w 之间有两条顶点不重叠的路径。（或者等价地，通过任意两个顶点的简单循环。）我们在边上定义一个共圆等价关系：如果 e1 = e2 或者存在包含 e1 和 e2 的循环，则 e1 和 e2 在同一个双连通分量中。两个双连通分量最多共享一个公共顶点。一个顶点是关节点，当且仅当它是多于一个双连通分量的公共部分时。程序 Biconnected.java 标识出桥梁和关节点。
   
5. 双连通分量。 修改Biconnected以打印构成每个双连通分量的边。提示：每个桥梁都是自己的双连通分量；要计算其他双连通分量，将每个关节点标记为已访问，然后运行 DFS，跟踪从每个 DFS 起点发现的边。
   
6. 对随机无向图的连通分量数量进行数值实验。在 1/2 V ln V 附近发生相变。（参见 Algs Java 中的属性 18.13。）
   
7. 流氓。（安德鲁·阿普尔。）在一个无向图中，一个怪物和一个玩家分别位于不同的顶点。在角色扮演游戏 Rogue 中，玩家和怪物轮流行动。每轮中，玩家可以移动到相邻的顶点或原地不动。确定玩家在怪物之前可以到达的所有顶点。假设玩家先行动。
   
8. 流氓。（安德鲁·阿普尔。）在一个无向图中，一个怪物和一个玩家分别位于不同的顶点。怪物的目标是落在与玩家相同的顶点上。为怪物设计一个最佳策略。
   
9. 关节点。 设 G 是一个连通的无向图。考虑 G 的 DFS 树。证明顶点 v 是 G 的关节点当且仅当（i）v 是 DFS 树的根并且有多于一个子节点，或者（ii）v 不是 DFS 树的根并且对于 v 的某个子节点 w，w 的任何后代（包括 w）和 v 的某个祖先之间没有反向边。换句话说，v 是关节点当且仅当（i）v 是根并且有多于一个子节点，或者（ii）v 有一个子节点 w，使得 low[w] >= pre[v]。
   
10. 谢尔宾斯基垫。 一个优美的欧拉图的例子。
    
11. 优先连接图。 如下创建一个具有 V 个顶点和 E 条边的随机图：以任意顺序开始具有 V 个顶点 v1，…，vn。均匀随机选择序列的一个元素并添加到序列的末尾。重复 2E 次（使用不断增长的顶点列表）。将最后的 2E 个顶点配对以形成图。
    大致来说，等价于按照两个端点的度数的乘积成比例的概率逐个添加每条边。参考。
    
12. 维纳指数。 一个顶点的维纳指数是该顶点与所有其他顶点之间的最短路径距离之和。图 G 的维纳指数是所有顶点对之间的最短路径距离之和。被数学化学家使用（顶点=原子，边=键）。
    
13. 随机游走。 从迷宫中走出（或图中的 st 连通性）的简单算法：每一步，朝一个随机方向迈出一步。对于完全图，需要 V log V 时间（收集优惠券）；对于线图或环，需要 V² 时间（赌徒的失败）。一般来说，覆盖时间最多为 2E(V-1)，这是 Aleliunas、Karp、Lipton、Lovasz 和 Rackoff 的经典结果。
    
14. 删除顺序。 给定一个连通图，确定一个顺序来删除顶点，使得每次删除后图仍然连通。你的算法在最坏情况下应该花费与 V + E 成比例的时间。
    
15. 树的中心。 给定一个树（连通且无环）的图，找到一个顶点，使得它与任何其他顶点的最大距离最小化。
    提示：找到树的直径（两个顶点之间的最长路径）并返回中间的一个顶点。
    
16. 树的直径。 给定一个树（连通且无环）的图，找到最长的路径，即一对顶点 v 和 w，它们之间的距离最远。你的算法应该在线性时间内运行。
    提示。 选择任意顶点 v。计算从 v 到每个其他顶点的最短路径。设 w 是最大最短路径距离的顶点。计算从 w 到每个其他顶点的最短路径。设 x 是最大最短路径距离的顶点。从 w 到 x 的路径给出直径。
    
17. 使用并查集查找桥梁。 设 T 是一个连通图 G 的生成树。图 G 中的每条非树边 e 形成一个由边 e 和树中连接其端点的唯一路径组成的基本环。证明一条边是桥梁当且仅当它不在某个基本环上。因此，所有桥梁都是生成树的边。设计一个算法，使用 E + V 时间加上 E + V 并查集操作，找到所有桥梁（和桥梁组件）。
    
18. 非递归深度优先搜索。 编写一个程序 NonrecursiveDFS.java，使用显式堆栈而不是递归来实现深度优先搜索。
    这是 Bin Jiang 在 1990 年代初提出的另一种实现。唯一额外的内存是用于顶点堆栈，但该堆栈必须支持任意删除（或至少将任意项移动到堆栈顶部）。

private void dfs(Graph G, int s) {
    SuperStack<Integer> stack = new SuperStack<Integer>();
    stack.push(s);
    while (!stack.isEmpty()) {
        int v = stack.peek();
        if (!marked[v]) {
            marked[v] = true;
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    if (stack.contains(w)) stack.delete(w);
                    stack.push(w);
                }
            }
        }
        else {
            // v's adjacency list is exhausted
            stack.pop();
        }
    }
}

1. 这里是另一种实现。这可能是最简单的非递归实现，但在最坏情况下使用的空间与 E + V 成比例（因为一个顶点的多个副本可能在堆栈上），并且以标准递归 DFS 的相反顺序探索与 v 相邻的顶点。此外，edgeTo[v] 条目可能被更新多次，因此可能不适用于回溯应用。

private void dfs(Graph G, int s) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(s);
    while (!stack.isEmpty()) {
        int v = stack.pop();
        if (!marked[v]) {
            marked[v] = true;
            for (int w : G.adj(v)) {
                if (!marked[w]) {
                    edgeTo[w] = v;
                    stack.push(w);
                 }
            }
        }
    }
}

1. 非递归深度优先搜索。 解释为什么以下非递归方法（类似于 BFS，但使用堆栈而不是队列）不实现深度优先搜索。

private void dfs(Graph G, int s) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(s);
    marked[s] = true;
    while (!stack.isEmpty()) {
       int v = stack.pop();
       for (int w : G.adj(v)) {
           if (!marked[w]) {
               stack.push(w);
               marked[w] = true;
               edgeTo[w] = v;
           }
       }
    }
}

1. *解决方案：*考虑由边 0-1、0-2、1-2 和 2-1 组成的图，其中顶点 0 为源。
2. Matlab 连通分量。 在 Matlab 中，bwlabel() 或 bwlabeln() 用于标记 2D 或 kD 二进制图像中的连通分量。bwconncomp() 是更新版本。
   
3. 互补图中的最短路径。 给定一个图 G，设计一个算法来找到从 s 到互补图 G’ 中每个其他顶点的最短路径（边的数量）。互补图包含与 G 相同的顶点，但只有当边 v-w 不在 G 中时才包含边 v-w。你能否比明确计算互补图 G’ 并在 G’ 中运行 BFS 做得更好？
   
4. 删除一个顶点而不断开图。 给定一个连通图，设计一个线性时间算法来找到一个顶点，其移除（删除顶点和所有关联边）不会断开图。
   提示 1（使用 DFS）：从某个顶点 s 运行 DFS，并考虑 DFS 中完成的第一个顶点。
   提示 2（使用 BFS）：从某个顶点 s 运行 BFS，并考虑具有最大距离的任何顶点。
   
5. 生成树。 设计一个算法，以时间复杂度为 V + E 计算一个连通图的生成树。提示：使用 BFS 或 DFS。
   
6. 图中的所有路径。 编写一个程序 AllPaths.java，枚举图中两个指定顶点之间的所有简单路径。提示：使用 DFS 和回溯。警告：图中可能存在指数多个简单路径，因此对于大型图，没有算法可以高效运行。