第1章 基础

1.3 背包、队列和栈

• 这个翻译真别扭，不能叫强制转换吗

  自动将一个原始数据类型转换为一个封装类型被称为自动装箱，自动将一个封装类型转换为一个原始数据类型被称为自动拆箱。

1.5 案例研究：union-find算法

• 这里，当且仅当两个对象相连时它们才属于同一个等价类
• 我们会在本节以下内容中使用网络方面的术语，将对象称为触点，将整数对称为连接，将等价类称为连通分量或是简称分量。
• 如果两个触点在不同的分量中，union()操作会将两个分量归并。find()操作会返回给定触点所在的连通分量的标识符。connected()操作能够判断两个触点是否存在于同一个分量之中。count()方法会返回所有连通分量的数量。一开始我们有N个分量，将两个分量归并的每次union()操作都会使分量总数减一。
• 一开始，我们有N个分量，每个触点都构成了一个只含有它自己的分量，因此我们将id[i]的值初始化为i，其中i在0到N-1之间。对于每个触点i，我们将find()方法用来判定它所在的分量所需的信息保存在id[i]之中。connected()方法的实现只用一条语句find(p) == find(q)，它返回一个布尔值，我们在所有方法的实现中都会用到connected()方法。
• find()操作的速度显然是很快的，因为它只需要访问id[]数组一次。但quick-find算法一般无法处理大型问题，因为对于每一对输入union()都需要扫描整个id[]数组。
• 与其在union()中随意将一棵树连接到另一棵树，我们现在会记录每一棵树的大小并总是将较小的树连接到较大的树上

第2章 排序

2.1 初级排序算法

• 用我们的StdDraw库画出一张可视轨迹图并不比追踪一次算法的运行轨迹难多少。将Double值排序，并在适当的时候指示算法调用show()方法（和追踪算法的轨迹时一样），然后开发一个使用StdDraw来绘制棒状图而不是打印结果的show()方法。
• 用我们的StdDraw库画出一张可视轨迹图并不比追踪一次算法的运行轨迹难多少。将Double值排序，并在适当的时候指示算法调用show()方法（和追踪算法的轨迹时一样），然后开发一个使用StdDraw来绘制棒状图而不是打印结果的show()方法。最复杂的部分是设置y轴的比例以使轨迹的线条符合预期的顺序。请通过练习2.1.18来更好地理解可视轨迹图的价值和使用

第4章 图

4.1 无向图

• 数学家常常将含有平行边的图称为多重图，而将没有平行边或自环的图称为简单图。
• 某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。
• 如果从任意一个顶点都存在一条路径到达另一个任意顶点，我们称这幅图是连通图。一幅非连通的图由若干连通的部分组成，它们都是其极大连通子图。
• 这些要求比较模糊，但它们仍然能够帮助我们在三种图的表示方法中进行选择。❏邻接矩阵。我们可以使用一个V乘V的布尔矩阵。当顶点v和顶点w之间有相连接的边时，定义v行w列的元素值为true，否则为false。这种表示方法不符合第一个条件——含有上百万个顶点的图是很常见的，V2个布尔值所需的空间是不能满足的。❏边的数组。我们可以使用一个Edge类，它含有两个int实例变量。这种表示方法很简洁但不满足第二个条件——要实现adj()需要检查图中的所有边。❏邻接表数组。我们可以使用一个以顶点为索引的列表数组，其中的每个元素都是和该顶点相邻的顶点列表，参见图4.1.9。这种数据结构能够同时满足典型应用所需的以上两个条件，我们会在本章中一直使用它。
• 如前文所述，深度优先搜索中每条边都会被访问两次，且在第二次时总会发现这个顶点已经被标记过。这意味着深度优先搜索的轨迹可能会比你想象的长一倍！示例图仅含有8条边，但需要追踪算法在邻接表的16个元素上的操作。
• 这种简单的递归模式只是一个开始——深度优先搜索能够有效处理许多和图有关的任务。例如，本节中，我们已经可以用深度优先搜索来解决在第1章首次提到的一个问题。连通性。给定一幅图，回答“两个给定的顶点是否连通？”或者“图中有多少个连通子图？”等类似问题。
• 单点路径。给定一幅图和一个起点s，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出这条路径。”等类似问题。

4.3 最小生成树

• 我们会学习计算最小生成树的两种经典算法：Prim算法和Kruskal算法。这些算法理解容易，实现简单。它们是本书中最古老和最知名的算法之一，但它们也根据现代数据结构得到了改进。因为最小生成树的重要应用领域太多，对解决这个问题的算法的研究至少从20世纪20年代在设计电力分配网络时就开始了。现在，最小生成树算法在设计各种类型的网络（通信、电子、水利、计算机、公路、铁路、航空等）以及自然界中的生物、化学和物理网络等各个领域的研究中都起到了重要的作用
• 用一条边连接树中的任意两个顶点都会产生一个新的环；❏从树中删去一条边将会得到两棵独立的树。这两条性质是证明最小生成树的另一条基本性质的基础，而由这条基本性质就能够得到本节中的最小生成树算法
• 在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树
• 这些算法都是一种贪心算法的特殊情况：使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。这些算法相互之间的不同之处在于保存切分和判定权重最小的横切边的方式，但它们都是以下性质的特殊情况。
• 第一种计算最小生成树的方法叫做Prim算法，它的每一步都会为一棵生长中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边（黑色表示）加入树中（即由树中的顶点所定义的切分中的一条横切边）
• 我们要仔细学习的第二种最小生成树算法的主要思想是按照边的权重顺序（从小到大）处理它们，将边加入最小生成树中（图中的黑色边），加入的边不会与已经加入的边构成环，直到树中含有V-1条边为止。这些黑色的边逐渐由一片森林合并为一棵树，也就是图的最小生成树。这种计算方法被称为Kruska算法。
• Prim算法是一条边一条边地来构造最小生成树，每一步都为一棵树添加一条边。Kruskal算法构造最小生成树的时候也是一条边一条边地构造，但不同的是它寻找的边会连接一片森林中的两棵树。我们从一片由V棵单顶点的树构成的森林开始并不断将两棵树合并（用可以找到的最短边）直到只剩下一棵树，它就是最小生成树

4.4 最短路径

• 在实现这个约定时，将distTo[]中的所有元素都初始化为Double.POSITIVE_INFINITY, distTo[s]则为0。最短路径算法会将从起点可达的顶点v的distTo[v]设为一个有限值，这样就不必再用marked[]数组来在图的搜索中标记可达的顶点，而是通过检测distTo[v]是否为Double.POSITIVE_INFINITY来实现hasPathTo(v)。