我们定义了无向图 API，并考虑了邻接矩阵和邻接表的表示。我们介绍了搜索图的两种经典算法--深度优先搜索和广度优先搜索。我们还考虑了计算连接成分的问题，最后介绍了相关问题和应用。

在本讲座中，我们将研究有向图。我们首先介绍有向图中的深度优先搜索和广度优先搜索，并描述从垃圾收集到网络爬行的各种应用。接下来，我们介绍一种基于深度优先搜索的算法，用于计算非循环数图的拓扑顺序。最后，我们实现了计算数图强成分的 Kosaraju-Sharir 算法。

在本讲座中，我们将研究最小生成树问题。首先，我们将考虑该问题的通用贪婪算法。接下来，我们考虑并实现该问题的两种经典算法--Kruskal 算法和 Prim 算法。最后，我们将讨论一些应用和未决问题。

在本讲座中，我们将研究最短路径问题。我们首先分析最短路径的一些基本性质和该问题的通用算法。我们将介绍并分析针对权重为非负的最短路径问题的 Dijkstra 算法。接下来，我们将考虑一种针对 DAG 的更快算法，即使权重为负也能奏效。最后，我们将介绍针对无负循环的边加权数字图的 Bellman-Ford-Moore 算法。我们还考虑了从内容感知填充到套利的各种应用。

在本讲座中，我们将介绍最大流量和最小切割问题。我们从 Ford-Fulkerson 算法开始。为了分析其正确性，我们建立了最大流-最小切定理。接下来，我们考虑使用最短增量路径规则高效实现 Ford-Fulkerson 算法。最后，我们考虑了一些应用，包括双网匹配和棒球消除。

在本讲座中，我们将讨论字符串和相关对象的专门排序算法。我们首先使用一个子程序对小范围内的整数进行排序。然后，我们将考虑两种经典的径向排序算法--LSD 和 MSD 径向排序。接下来，我们考虑一种特别高效的变体，它是 MSD 径向排序和 quicksort 的混合体，被称为 3-way radix quicksort。最后，我们将介绍后缀排序和相关应用。

在本讲座中，我们将考虑使用字符串键的符号表的专门算法。我们的目标是建立一种与哈希算法一样快、甚至比二叉搜索树更灵活的数据结构。我们从多路尝试开始，接下来考虑三元搜索尝试。最后，我们将考虑基于字符的操作，包括前缀匹配和最长前缀，以及相关应用。

在本讲座中，我们将讨论在一段文本中搜索子串的算法。我们从最坏情况下运行时间为二次方的暴力算法开始。接下来，我们考虑巧妙的 Knuth-Morris-Pratt 算法，它的运行时间在最坏情况下保证是线性的。然后，我们介绍 Boyer-Moore 算法，它的运行时间在典型输入情况下是亚线性的。最后，我们考虑 Rabin-Karp 指纹算法，该算法巧妙地利用散列来解决子串搜索和相关问题。

正则表达式是一种指定字符串集合的方法。本讲座的主题是著名的 grep 算法，它可以确定给定文本是否包含字符串集合中的任何子串。我们将研究利用第 1 周的数图可达性实现的高效实现。

我们研究并实现了几种经典的数据压缩方案，包括运行长度编码、哈夫曼压缩和 LZW 压缩。我们从第一原理出发，使用我们为此目的开发的二进制数据操作 Java 库，并以之前讲座中的优先级队列和符号表实现为基础，开发出高效的实现方法。

本周的讲座围绕最大流和最短路径等问题解决模型的思想展开，新问题可以表述为这些问题的一个实例，然后用经典高效的算法来解决。为了使课程更加完整，我们将介绍理论计算机科学中的经典未解问题，该问题以算法效率概念为中心，引导我们寻找困难问题的高效解决方案。

线性规划是解决问题的典型模型，而求解线性规划的单纯形法是应用最广泛的算法之一。在本讲座中，我们将概述运筹学中的这一核心主题，并介绍它与我们所考虑的算法之间的关系。

是否存在一种通用的问题解决模型，我们想要解决的所有问题都可以归结为这种模型，并且我们知道一种有效的算法？您可能会惊讶地发现，我们并不知道这个问题的答案。在本讲座中，我们将介绍复杂度类别 P、NP 和 NP-complete，提出著名的 P = NP 问题，并结合本课程所涉及的算法来探讨其含义。