# algorithm_data_structures **Repository Path**: veyne/algorithm_data_structures ## Basic Information - **Project Name**: algorithm_data_structures - **Description**: 《数据结构与算法分析》原书第2版。Mark Allen Weiss著，冯舜玺译。 第2-10章算法记录 - **Primary Language**: Unknown - **License**: Apache-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2024-12-01 - **Last Updated**: 2025-01-17 ## Categories & Tags **Categories**: Uncategorized **Tags**: Cpp, Data-structures, Algorithm ## README ### 概述 1.该仓库记录<数据结构与算法分析-C语言描述>书中描述算法. 2.第1章是数学知识,不作记录. 3.从第2章到第10章,以目录的形式记录算法,并保证算法能运行. 4.书籍<数据结构与算法分析-C语言描述>原书第二版 Mark Allen Weiss著,冯舜玺译 ### 笔记如下 # 递归法则 1 基准情形 (必须有某些基准的情形，它们不用递归就能求解) 2 不断推进 (递归调用必须朝着产生基准情形的方向推进) //避免使用mod操作 m%n = m- (m/n)*n 3 设计法则 假设所有的递归调用都能运行 4 合成效益法则 在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性工作 # 算法分析 1 对于存在正常数c和n0使得当N>=n0时，T(N)<=cf(N), 则记为T(N)=O(f(N)); 2 对于存在正常数c和n0使得当N>=n0时，T(N)>=cf(N), 则记为T(N)=Ω(f(N)); 3 当且仅当T(N)=O(h(N)) && T(N)=Ω(h(N)), T(N)=θ(h(N)); 4 如果T(N)=O(p(N)) && T(N)!=θ(p(N)), 则T(N)=o(p(N)); 5 如果T1(N)=O(f(N)) && T2(N)=O(g(N)), 那么 T1(N)+T2(N)=max(O(f(N)), O(g(N)) T1(N)*T2(N)=O(f(N)*g(N)) 6 如果T(N)是一个k次多项式，则T(N)=θ(N^k) 7 对任意常数k, (logN)^k=O(N). 它告诉我们对数增长非常缓慢 //程序可能提前结束，但绝不可以延后 # 一般法则 1 for循环: 一次for循环的运行时间至多是该for循环内语句(包括测试)的运行时间乘以迭代的次数 2 嵌套的for循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有for循环的大小的乘积 3 顺序语句：将各个语句的运行时间求和即可(其中的最大值，就是所得的运行时间) 4 if/else语句：一个if/else语句的运行时间不超过判断的时间加上if和else中运行时间较长者总的运行时间 //当递归使用得当时，将其转化为一个简单的循环结构是相当困难的 //计算任何事情不要超过一次 //然而，程序短并不总是意味着程序好 # 仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法 1 只对数据进行一次扫描，一旦完成读入和处理，就不需要记忆它了。在任何时刻，算法都能对它已经读入的数据给出问题的正确答案。 //如果一个算法用常数时间O(1)将问题的大小消减为其一部分(通常是1/2)，那么该算法就是O(logN)的。另一方面，如果使用常数时间只是把问题减少一个常数，那么这个算法就是O(N)的。 //对分查找可以看作我们的第一个数据结构实现方式，它提供了在O(logN)时间内的Find操作，但是所有其他操作(特别是Insert操作)均需要O(N)时间 //抽象数据类型是一些操作的集合 //声明指向一个结构的指针并不创建该结构，而只是给出足够的空间容纳结构可能会使用的地址 //这个程序称为尾递归，是使用递归极端不当的例子。尾递归指的是在最后一行的递归调用。尾递归可以通过将递归调用变成goto语句，并在其前加上对该函数每个参数的赋值语句而手工消除。 ### 抽象数据类型 # 表 1 因为插入和删除的运行时间非常慢，并且表的大小还必须事先已知。所以简单数组一般不用来实现表这种结构。 2 链表 3 我们将留出一个标志节点，有时候称之为表头或哑节点。除此之外，要不要使用表头则是属于个人兴趣的问题。 4 如果与运算的前半部分为假，那么结构就自动为假，而后半部分则不再执行 5 递归编写Find是一个非常糟糕的想法，我们要不惜一切代价避免它 6 我们的例程将删除第一次出现的X，如果X不在表中我们就什么也不做 7 这个Insert例程将一个元素插到由P所指示的位置之后 8 除find好喝findPrevious例程外(还有delete例程，它调用findPrevious），已经编码的所有操作均需要O(1)时间。这是因为在所有的情况下，不管表多大，都只执行固定数目的指令。 //常见的错误 1 无论何时只要确定一个指向，那么就必须保证该指针不是NULL 2 声明指向一个结构的指针并不创建该结构，而只是给出足够的空间容纳结构可能会使用的地址 3 free(P)的结果是：P正在指向的地址没变，但在该地址处的数据此时已无定义了 //双链表 它增加了空间的需求，同时也使得插入和删除的开销增加了一倍。另外，它简化了删除操作。 //循环链表 //使用链表的例子 1 一元多项式的简单方法 2 基数排序。基数排序有时也称为卡式排序，因为直到现代计算机出现之前，它一直用于对老式穿卡孔的排序。 3 如果我们有N个整数，范围从1到M(或者从0到M-1)，我们可以利用这个信息得到一种快速的排序，叫做桶式排序。我们留置一个数组，称之为Count,大小为M,并初始化为0； 于是,Count有M个单元(或桶),开始时它们都是空的。当Ai被读入时Count[Ai]增1，在读入所有的输入后，扫描数组Count,打印输出排好序的表。 该算法花费O(M+N)。如果M=θ(N)，则桶式排序为O(N)。基数排序是这种方法的推广。 前面各趟排序保证了当几个数进入一个桶时，它们是以排序的顺序进入的 4 多重表 5 链表的游标实现（如果需要链表，而又不能使用指针) # 栈 1 栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。 2 对空栈进行的pop或top一般被认为是栈ADT的错误。另一方面，当运行push时空间用尽是一个实现错误，但不是ADT错误。 3 一般的模型是，存在某个元素位于栈的顶，而该元素是栈唯一的可见元素 //栈的实现 1 栈的链表实现 实现栈要用到一个表头。测试空栈与测试空表的方式相同。 有的缺点通过使第二个栈可以避免。第二个栈初始时为空栈。当一个单元从第一个栈弹出时，它只是被放到了第二个栈中。此后，当第一个栈需要新的单元的时候，它首先去检查第二个栈。 2 栈的数组实现 这种策略的唯一潜在危害是我们需要提前声明一个数组的大小 栈很可能是计算机科学中仅次于数组的最基本的数据结构 如果把对这些条件的检测放到数组实现过程中，那就很可能要花费像实际栈操作那样多的时间。由于这个原因，除非在错误处理极其重要的场合(如在操作系统中),一般在栈例程中省去错误检测就成了惯用手法。 //栈的应用 1 平衡符号 2 后缀表达式。这种计法叫做后缀或逆波兰记法 3 中缀到后缀的转换。对于这种操作,"+"的优先级最低，而"("的优先级最高。 4 函数调用 当存在函数调用的时候，需要存储的所有重要信息，诸如寄存器的值(对应变量的名字)和返回地址(它可以从程序计数器得到，典型情况下计数器就是一个寄存器)等，都要以抽象的方式存在"一张纸上"并被置于 一个堆的顶部。然后控制转移到新函数，该函数自由地用它的一些值代替这些寄存器。如果它又进行其它的函数调用，那么它也遵循相同的过程。当该函数返回时，它查看堆顶部的那张"纸”，并复原所有的寄存器。 然后它进行返回转移。 在实际计算机中的栈常常是从内存分区的高端向下增长，而在许多的系统中是不检测溢出的。由于有太多同时在运行着的函数，用尽栈空间的情况总是可能发生的。显而易见，用尽栈空间通常是致命的错误。 在正常情况下不应该越出栈空间，发生这种情况通常是由失控递归(忘记基准情形)的指向引起的。 # 队列 1 像栈一样，队列也是表。然而，使用队列时插入在一端进行而删除则在另一端进行。 2 队列的基本操作时enqueue-它是在表的末端(叫做队尾rear)插入一个元素，还有dequeue-它是删除在表的开头(也叫做队头front)的元素。 3 队列的循环数组实现 4 检测队列是否为空是很重要的 ### 树 1 对于大量的输入数据，链表的线性访问时间太慢，不宜使用。 2 定义树的一种自然的方式是递归方法。一棵树是一些节点的集合。这个集合可以是空集；若非空，则一颗树由称作根(root)的节点r以及0个或多个非空的(子)树T1,T2,...,TK组成， 这些子树中每一颗的根都被来自根r的一条有向的边(edge)所连接。 每一颗子树的根叫做根r的儿子(child)，而r是每一颗子树的根的父亲(parent)。 3 从递归定义中我们发现，一颗树是由N个节点和N-1条边的集合，其中的一个节点叫做根。存在N-1条边的结论是由下面的事实得出的，每条边都将某个节点连接到它的父亲，而除去 根节点外每一个节点都有一个父亲。 4 没有儿子的节点称为树叶(leaf);具有相同父亲的节点为兄弟(sibling);用类似的方法可以定义祖父(grandparent)和孙子(grandchild)关系。 5 从节点n1到nk的路径(path)定义为节点n1,n2,...,nk的一个序列，使得对于1<=i构造一颗表达式树 1 一次一个符号地读入表达式。如果符号是操作树，我们就建立一个单节点树并将一个指向它的指针推入栈中。如果符号是操作符，那么我们从栈中弹出指向两棵树T1和T2的那两个指针(T1的先弹出)并形成一颗新的树， 该树的根就是操作符，它的左，右儿子分别指向T2和T1。然后将指向这颗新树的指针压入栈中。 2 为了方便起见，我们将让图中的栈从左到右增长。 3 栈的大小为节点数。 # 查找树ADT-二叉查找树 1 使二叉树成为二叉查找树的性质是，对于树中的每个节点X,它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有的关键字值大于X的关键字值。 这意味着，该树所有的元素可以用某种统一的方式排序 //MakeEmpty 1 我们的实现方法更紧密地遵循树的递归定义 //Find 1 这个操作一般需要返回指向树T中具有关键字X的节点的指针，如果这样的节点不存在则返回NULL 2 其余的测试应该使得最不可能的情况安排在最后进行 3 尾递归的使用在这里是合理的，因为算法表达式的简明性是以速度为代价的，而这里所使用的栈空间也只不过是O(logN)而已 //FindMin和FindMax 1 为执行FindMin，从根开始并且只要有左儿子就向左进行。终止点是最小的元素(没有左儿子) 2 虽然小心总是重要的，但在递归程序中它尤其重要 //Insert 1 为了将X插入到树T中，你可以像用Find那样沿着树查找。如果找到X，则什么也不做(或做一些“更新”)。否则，将X插入到遍历的路径上的最后一点上。 2 如果是空树，则create and return a one-node tree。否则，将Insert写成一个返回指向新树根的指针的函数 3 if X is in the tree already; we'll do nothing. //Delete 1 正如许多数据结构一样，最困难的操作就是删除。 2 如果节点是一片树叶，那么可以立刻删除 3 如果节点有一个儿子(肯定是左儿子)，则该节点可以在其父节点调整指针绕过该节点后删除。 4 处理两个儿子节点。一般的删除策略是用其右子树中最小的数据(很容易找到)代替该节点的数据并的递归地删除那个节点(现在它是空的)。因为右子树中最小的节点不可能有左儿子，所以第二次delete更容易。 5 如果删除的次数不多，则通常使用的策略是懒惰删除：当一个元素要被删除时，它仍留在树中，只是做了个被删除的记号。这种做法特别是在有重复关键字时很流行，因为此时记录出现频率树的域可以减1。 如果树中的实际节点树和“被删除”的节点数相同，那么树的深度预计只上升一个小的常数。因此，存在一个与懒惰删除相关的非常小的时间损耗。再有，如果被删除的关键字是重新插入的，那么分配一个 新单元的开销就避免了。 //平均情形分析 1 除MakeEmpty外，所有的操作都是O(d)的，其中d是包含所访问的关键字的节点的深度 2 假设所有的树出现的机会均等，则树的所有节点的平均深度为O(logN) 3 一颗树的所有节点的深度的和称为内部路径长。令D(N)是具有N个节点的某颗树T的内部路劲长。D(1)=0。0<=i线性探测法 1 在线性探测法中，函数F是i的线性函数，典型情形是F(i)=i。这相当于逐个探测每个单元（必要时可以绕回)以查找出一个空单元。 2 只要表足够大，总能够找到一个自由单元，但是如此花费的时间是相当多的。更糟的是，即使表相对较空，这样占据的单元也会开始形成一些区块，其结果称为一次聚集，于是，散列到区块中的任何关键字都需要多次试选单元才能解决冲突， 然后该单元被添加到相应的区块中。 3 从这些公式看到，如果超过一半的表被填满的话，那么线性探测就不是个好办法。 >平方探测法 1 平方探测是消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次函数的探测方法，流行的选择是F(i)=i^2。 2 对于线性探测，让元素几乎填满散列表并不是个好主意，因为此时表的性能会降低，对于平方探测情况甚至更糟：一旦表被填满超过一半，当表的大小不是素数时甚至在表被填满一半之前，就不能保证一次找到一个空单元了。 3 定理5.1: 如果使用平方探测，且表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。 4 哪怕表有比一半多一个的位置被填满，那么插入都有可能失败（虽然这是非常难以见到的）。把它记住很重要。另外，表的大小是素数也非常重要。 5 如果表的大小是形如4k+3的素数，且使用的平方冲突解决方法为F(i)=+-i^2。那么整个表均可被探测到。其代价则是例程要略微复杂。 6 在开放定址散列表中，标准的删除操作不能施行，因为相应的单元可能已经引起过冲突，元素绕过它存在了别处。因此，开放定址散列表需要懒惰删除，虽然在这种情况下并不存在真正意义上的懒惰。 7 这里，我们不用链表数组，而是使用散列表项单元的数组，与在分离链接散列中一样，这些单元也是动态分配地址的。 8 如同分离链接散列法一样，Find(Key,H)将返回Key在散列表中的位置，如果Key不出现，那么Find将返回最后的单元。该单元就是当需要时，Key将被插入的地方。 9 虽然平方探测排除了一次聚集，但是散列到同一位置上的那些元素将探测相同的备选单元。这叫做二次聚集。二次聚集是理论上的一个小缺憾。模拟结果指出，对每次查找，它一般要引起另外的少于一半的探测。 >双散列 1 对于双散列，一种流行的选择是F(i)=i.hash2(X)。这个公式是说，我们将第二个散列函数应用到X并在距离Hash2(X)，2hash2(X)等处探测。hash2(X)选择得不好将会是灾难性的。因此，函数一定不要算得0值。另外，保证所有的单元都 能被探测到(在下面的例子中这是不可能的,因为表的大小不是素数)也是很重要的。诸如hash2(X)=R-(X modR)这样的函数将起到良好的作用，其中R为小于TableSize的素数。 2 但是，有必要了解在使用双散列时为什么保证表的大小为素数是重要的。如果想要把23插入到表中，那么它就会与58发生冲突。由于hash2(23)=7-2=5,且该表大小不是素数，那么备选大院就有可能提前用完。 >再散列 1 对于使用平方探测的开放定址散列法，如果表的元素填的太满，那么操作的运行时间将开始消耗过长，且Insert操作可能失败。这可能发生在有太多的移动和插入混合的场合。此时，一种解决方法是建立另外一个大约两倍大的表(而且使用一个 相关的新散列函数), 扫描整个原始散列表，计算每个(未删除的)元素的新散列值并将其插入到新表中。 2 该表大小之所以是17，是因为17是原表大小两倍后的第一个素数。 3 整个操作就叫做再散列。显然这是一种非常昂贵的操作，其运行时间为O(N)，因为有N个元素要再散列而表的大小约为2N，不过，由于不是经常发生，因此实际效果根本没有这么差。 4 第三种方法是途中策略：当表达到某一个装填因子时进行再散列。由于随着装填因子的增加，表的性能的确有所下降，因此，以好的截至手段实现的第三种策略，可能是最好的策略。 5 再散列使程序员再也不用担心表的大小，这一点很重要，因为在复杂的程序中散列表不能够做得任意大。 //可扩散列 1 本章最后的论题处理数据量太大以至于装不进主存的情况。 2 一种聪明的选择叫做可扩散列，它允许用两次磁盘访问执行一次Find。插入操作也需要很少的磁盘访问。 3 B树具有深度O(logM/2 N)。随着M的增加，B树的深度降低。理论上我们可以选择使得B树的深度为1的M。此时，在第一次以后的任何Find都将花费一次磁盘访问，因为据推测根节点可能存在主存中。这种方法的问题在于分支系数太高， 以至于为了确定数据在哪边树叶上要进行大量的处理工作。如果运行这一步的时间可以缩减，那么我们就将有一个实际的方案。这正是可扩散列使用的策略。 4 “树”的根含有4个指针，它们由这些数据的前两位确定。每片树叶有最多M=4个元素。用D代表根所使用的位数，有时称其为"目录”。于是，目录中的项数为2^D。dL为树叶L所有元素共有的最高位的位数。dL将依赖于特定的树叶，因此dL<=D。 设欲插入关键字100100。它将进入第三片树叶，但是第三片树叶已经满了，没有空间存放它。因此我们将这片树叶分裂成两片树叶，它们由前三位确定。这需要将目录的大小增加到3. 5 注意，所有未被分裂的树叶现在各由两个相邻目录项所指。因此，虽然重写整个目录，但是其他树叶都没有被实际访问。 6 这个非常简单的方法提供了对大型数据库Insert操作和Find操作的快速存取时间。 7 首先，有可能当一片树叶的元素有多于D+1个前导位相同时需要多个目录分裂。其次，存在重复关键字的可能性；若存在多余M个重复关键字，则该算法根本无效。 8 这些可能性指出，这些位完全随机是相当重要的，这可以通过把关键字散列到合理长的整数(由此得名)来完成。 9 我们介绍可扩散列的某些性能，这些性能是经过非常困难的分析后得到的。这些结果基于合理的假设“位模式是均匀分布的。 10 树叶的期望个数位(N/M)log2e。因此，平均树叶满的程度位ln2=0.69。 11 更惊奇的结果是，目录的期望大小(换句话说即2^D)为O(N^(1+1/M)/M)。如果M很小，那么目录可能过大。在这种情况下，我们可以让树叶包含指向记录的指针而不是实际的记录。这样可以增大M的值。为了维持更小的目录，可以为每个 Find操作添加第二个磁盘访问。 ### 优先队列(堆) 1 优先队列是允许至少下列两种操作的数据结构：Insert,它的工作是显而易见的；以及DeleteMin,它的工作是找出，返回和删除优先队列中最小的元素。Insert操作等价于Enqueue(入队)，而DeleteMin则是队列中Dequeue(出列)在优先队列 中的等价操作。 2 有几种明显的方法实现优先队列。我们可以使用一个简单链表在表头以O(1)执行插入操作，并遍历该链表以删除最小元，这又需要O(N)时间。 3 还有一种实现优先队列的方法是使用二叉查找树，它对这两种操作的平均运行时间都是O(logN) 4 我们将要使用的这种工具叫做二叉堆(binary heap)，常用其实现优先队列，当不加修饰地使用堆(heap)这个词时一般都是指该数据结构的实现。同二叉查找树一样，堆也有两个性质，即结构性和堆序性。正如AVL树一样，对堆的一次操作 可能破坏这两个性质中的一个，因此，堆的操作必须要到堆的所有性质都被满足时才能终止。 5 堆是一颗被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树。 6 因为完全二叉树很有规律，所以它可以用一个数组表示而不需要指针。 对于数组中的任意位置i上的元素，其左儿子在位置2i上，右儿子在左儿子后的单元(2i+1)中，它的父亲则在位置[i/2]上。这种实现方法的唯一问题在于，最大的堆大小需要事先估计。 因此，一个堆数据结构将由一个数组（不管关键字是什么类型），一个代表最大值的整数以及当前的堆大小组成。 # 堆序性质 1 使操作快速执行的性质是堆序性。由于我们想要快速地找出最小元，因此最小元应该在根上。如果我们将任意子树也视为一个堆，那么任意节点就应该小于它的所有后裔。 在一个堆中，对于每一个节点X，X的父亲中的关键字小于(或等于)X中的关键字，根节点除外（它没有父亲）。 类似地，我们可以声明一个(max)堆，它使我们能够通过改变堆序性质有效地找出和删除最大元。因此，优先队列可以用来找出最大元或最小元，但这需要提前决定。 # 基本的堆操作 //Insert 1 为将一个元素X插入到堆中，我们在下一个空闲位置创建一个空穴，否则该堆将不是完全树。如果X可以放在该空穴中而并不破坏堆的序，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向上行一步。 继续该过程直到X能被放入空穴中为止。这种一般的策略叫做上滤；新元素在堆中上滤直到找出正确的位置。 2 如果要插入的元素是新的最小值，那么它将一直被推向顶端。这样在某一时刻，i将是1,我们就需要令程序跳出while循环。当然我们可以用明确的测试做到这一点。不过， 我们采用的是把一个很小的值放到位置0处以使得while循环得以终止。这个值必须保证小于(或等于)堆中的任何值，我们称之为标记。 //DeleteMin 1 找出最小元是容易的，困难的部分是删除它。当删除一个最小元时，在根节点处产生了一个空穴。由于现在堆少了一个元素，因此，堆中最后 。因此，我们的做法是将X置入沿着从根开始包含最小儿子的一条路径上的一个正确的位置。这种策略叫做下滤。 2 在堆的实现中经常发生的错误是当堆中存在偶数个元素的时候，此时将遇到一个节点只有一个儿子的情况。 //其他的堆操作 1 注意，虽然求最小值操作可以在常数时间完成，但是，按照求最小元设计的堆（也称作最小值(min)堆)在求最大元方面却无任何帮助。 *DecreaseKey(P,▲,H) 操作降低在位置P处的关键字的值，降低的幅度为正的量▲。由于这可能破坏堆的序，因此必须通过上滤对堆进行调整。该操作对系统管理程序是有用的：系统管理程序能够让它们的程序以最高的优先级运行。 *IncreaseKey(P,▲,H) 许多调度程序自动地降低正在过多地消耗CPU时间的进程的优先级。 *Delete(P,H) 操作删除堆中位置P上的节点。这通过首先执行DecreaseKey(P,∞,H),再执行DeleteMin(H)来完成。当一个进程被用户中止(而不是正常终止)时，它必须从优先队列中除去。 *BuildHeap(H) 操作把N个关键字作为输入并把它们放入空堆中。一般的算法是将N个关键字以任意顺序放入树中，保持结构特性。此时，如果percolateDown(i)从节点i下滤，那么执行图6-14中的该算法创建一棵具有堆序的树。 2 定理6.1 包含2^(h+1)-1个节点，高为h的理想二叉树的节点的高度的和为2^(h+1)-1-(h+1) 3 完全树不是理想二叉树，但是我们得到的结果却是一颗完全树的节点高度的和的上界。 # 优先队列的应用 //选择问题 1 当时的输入是N个元素以及一个整数k,这N个元素的集可以是全序的。该选择问题是要找出第k个最大的元素。 2 算法6A： 为了简单起见，假设我们只考虑找出第k个最小的元素。该算法很简单。我们将N个元素读入一个数组。然后对该数组应用BuildHeap算法。最后，执行k次DeleteMin操作。从该堆最后提取的元素就是我们的答案。显然，通过改变堆序性质， 我们就可以求解原始的问题——找出第k个最大的元素。 注意，如果我们对k=N运行该程序并在元素离开堆时记录它们的值，那么我们实际上已经对输入文件以时间O(NlogN)作了排序。在第7章，我们将细化该想法，得到一种快速的排序算法，叫做堆排序。 3 算法6B: 在任意时刻我们都将维护k个最大元素的集合S。在前k个元素读入后，当再读入一个新的元素时，该元素将与第k个最大元素进行比较，记这第k个最大的元素为Sk。注意，Sk是S中最小的元素。如果新的元素更大，那么用新元素代替S中的Sk. 此时，S将有一个新的最小元素，它可能是新添加的元素，也可能不是。在输入终了时，我们找到S中最小的元素，将其返回，它就是答案。 不过，这里我们使用一个堆来实现S。前k个元素通过调用一次BuildHeap以总时间O(k)被置入堆中。处理每个其余的元素的时间为O(1)(检测元素是否进入S)再加上时间O(logk)(在必要时三处Sk并插入新元素)。因此，总的时间为 O(k+(N-k)logk)=O(Nlogk)。该算法也给出找出中位数的时间界Θ(NlogN)。 //事件模拟 1 一位顾客平均必须要等多久或所排的队伍可能有多长这类统计问题。 # d-堆 1 d-堆是二叉堆的简单推广。它恰像一个二叉堆，只是所有的节点都有d个儿子(因此，二叉堆是2-堆)。 2 注意，d-堆要比二叉堆浅得多，它将Insert操作的运行时间改进为O(logdN)。然而，对于大的d，DeleteMin操作费时得多，因为虽然树浅了，但是d个儿子中的最小者是必须要找出的，如使用标准的算法，这会花费d-1次比较，于是 将此操作的用时提高到O(dlogdN)。 3 当优先队列太大不能完全装入主存的时候，d-堆也是很有用的。 4 除不能执行Find外，堆的实现最明显的缺点是：将两个堆合并成一个堆是困难的操作。这种附加的操作叫做Merge(合并)。存在许多实现堆的方法使得Merge操作的运行时间是O(logN)。 # 左式堆 1 因此，所有支持高效合并的高级数据结构都需要使用指针。处理指针一般比用2作乘法和触发更耗费时间。 2 像二叉堆那样，左式堆(leftist heap)也具有结构特性和有序性。事实上，和所有使用的堆一样，左式堆具有相同的堆序性质，该性质我们已经看到过。不仅如此，左式堆也是二叉树。左式堆和二叉树间唯一的区别是：左式堆不是理想平衡 的，而实际上是趋向于非常不平衡的。 //左式堆的性质 1 我们把任意节点X的零路径长(Null Path Length, NPL)Npl(X)定义为从X到一个没有两个儿子的节点的最短路径的长。 因此，具有0个或1个儿子的节点的Npl为0，而Npl(NULL)=-1. 2 注意，任意节点的零路径长比它的诸儿子节点的零路径长的最小值多1。这个结论也适用少于两个儿子的节点，因为NULL的零路径长是-1。 3 对于堆中的每一个节点X，左儿子的零路径长至少与右儿子的零路径长一样大。 4 在右路径上有r个节点的左氏树必然至少有2^r-1个节点。 5 唯一的棘手部分在于，对右路径的Insert和Merge可能会破坏左式堆性质。 //左式堆的操作 1 对左式堆的基本操作是合并。注意，插入只是合并的特殊情形，因为我们可以把插入看成单节点堆与一个大的堆的Merge。 2 我们的输入是两个左式堆H1和H2。如果这两个堆中有一个是空的，那么我们可以返回另外一个堆。否则，为了合并这两个堆，我们需要比较它们的根。首先，我们将具有大的根值的堆与具有笑得根值的堆的右子堆合并。 在本例中，我们递归地将H2与H1中根在8处地右子堆合并。现在，我们让这个新的堆成为H1的根的右儿子。 使整个树是左式的做法如下：只要交换根的左儿子和右儿子并更新零路径长，就完成了Merge，新的零路径长是新的右儿子的零路径长加1。注意，如果零路径长不更新，那么所有的零路径长都将是0，而堆将不是左式的，只是随机的。 在这种情况下，算法仍然成立，但是，我们宣称的时间界将不再有效。 3 当将一个元素插入到一颗空的二叉树时，需要改变指向根的指针。最容易的实现方法是让插入例程返回指向新树的指针。不幸的是，这将使得左式堆的Insert与二叉堆的Insert不兼容(后者什么也不返回)。 返回新树的左式堆插入例程将标记为Insert1，宏Insert将完成一次与二叉堆兼容的插入操作。 4 注意，原始的两个左式堆绝不要再使用，它们本身的变化将影响合并操作的结果。 5 执行合并的时间与右路径的长的和成正比，因为在递归调用期间对每一个被访问的节点执行的是常数工作量。因此，我们得到合并两个左式堆的时间界为O(logN) 6 为了执行DeleteMin,只要除掉根而得到两个堆，然后再将这两个堆合并。因此，执行一次DeleteMin的时间为O(logN)。 7 BuildHeap的效果可以通过递归地建立左右子树然后将根下滤而得到。 # 斜堆 1 斜堆(skew heap)是左式堆的自调节形式，实现起来极其简单。斜堆和左式堆间的关系类似于伸展树和AVL树间的关系。斜堆是具有堆序的二叉树，但是不存在对树的结构限制。不同于左式堆，关于任意节点的零路径长的任何信息都不保留。 斜堆的右路径再任意时刻都可以任意长，因此，所有操作的最坏运行时间为O(N)。 2 斜堆的基本操作也是合并操作。 3 但有一个例外，即对于左式堆，我们查看是否左儿子和右儿子满足左式堆堆序性质并交换那些不满足该性质者；但对于斜堆，除了这些右路径上所有节点的最大者不交换它们的左右儿子外，交换是无条件的。 4 我们也可以像左式堆那样非递归地进行所有的操作：合并右路径，除最后的节点外交换右路径上每个节点的左儿子和右儿子。经过几个例子之后，事情变得很清楚：由于除去右路径上最后的节点外的所有节点都将它们的儿子交换，因此 最终效果是它变成了新的左路径。这使得合并两个斜堆非常容易。 这与递归实现不完全一样(但服从相同的时间界)。如果一个堆的右路径用完而导致右路径合并终止，而我们只交换终止的那一点上面的右路径上的节点的儿子，那么将得到与递归做法相同的结果。 5 注意，因为右路径可能很长，所以递归实现可能由于缺乏栈空间而失败，虽然在其他方面性能是可以接受的。斜堆有一个优点，即不需要附加的空间来保留路径长以及不需要测试确定何时交换儿子。 # 二项队列 1 二项队列(binomial queue)不同于我们已经看到的所有优先队列的实现之处在于，一个二项队列不是一颗堆序的树，而是堆序树的集合，称为森林(forest)。堆序树中的每一颗都是有约束的形式，叫做二项树(binomial tree)。 每一个高度上至多存在一颗二项树。高度为0的二项树是一颗单节点树；高度为k的二项树Bk通过将一颗二项树Bk-1附接到另一颗二项树Bk-1的根上而构成。 2 二项树Bk由一个带有儿子B0,B1,...,Bk-1的根组成。高度为k的二项树恰好有2^k个节点，而在深度d处的节点数是二项系数{k d}。如果我们把堆序施加到二项树上并允许任意高度上最多有一颗二项树，那么我们能够用二项树的集合唯一 地表示任意大小的优先队列。 //二项队列操作 1 此时，最小元可以通过搜索所有的树的根来找出。由于最多有logN颗不同的树，因此最小元可以在O(logN)时间内找到。 2 合并操作基本上是通过将两个队列加到一起来完成的。 3 DeleteMin可以通过首先找出一颗具有最小根的二项树来完成。令该树为Bk,并令原始的优先队列为H。我们从H的树的森林中除去二项树Bk，形成新的二项树队列H'。再除去Bk的根，得到一些二项树B0,B1,...,Bk-1,它们共同形成优先队列H'', 合并H'和H''，操作结束。 //二项队列的实现 1 DeleteMin操作需要快速找出根的所有子树的能力，因此，需要一般树的标准表示方法-每个节点的儿子都存在一个链表中，而且每个节点都有一个指向它的第一个儿子(如果有的话)的指针。该操作还要求诸儿子按照它们的子树的大小排序。 我们也需要保证能够很容易地合并两棵树。当合并两棵树时，其中的一棵树作为儿子加到另一颗树上。由于这颗新树将是很大的子树，因此，以大小递减的方式保持这些子树是有意义的。只有这时，我们才能够有效地合并两颗二项树从而合并 两个二项队列。二项队列将是二项树的数组。 2 总之，二项树的每一个节点将包含数据，第一个儿子以及右兄弟。二项式中的诸儿子以递减次序排列。 3 为了合并两个二项队列，我们需要一个例程来合并两个同样大小的二项树。 4 现在我们介绍Merge例程的简单实现。该例程将H1和H2合并，把合并结果放入H1中，并清空H2。 5 当受到影响的元素的位置已知时，我们可以将二项队列扩展到支持二叉堆所允许的某些非标准的操作，诸如DecreaseKey和Delete。 ### 排序 1 为简单起见，假设在我们的例子中数组只包含整数，我们还假设整个排序工作能够在主存中完成，因此，元素的个数相对来说比较少(小于10^6)。当然，不能在主存中完成而必须在磁盘或磁带上完成的排序也相当重要。这种类型的排序叫做 外部排序。 2 按照C的约定，对于所有的排序，数据都将在位置0处开始 3 我们还假设"<"和">"运算符存在，它们可以用于对输入进行一致的排序。除赋值运算符外，这两种运算是仅有的允许对输入数据进行的操作。在这些条件下的排序叫做基于比较的排序。 # 插入排序 1 插入排序由N-1趟排序组成。对于P=1趟到P=N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。插入排序利用了这样的事实：位置0到位置P-1上的元素是已派过序的。 2 将位置P上的元素存于Tmp中，而(在位置P之前)所有更大的元素都向右移动一个位置。然后将Tmp置于正确的位置上。这种方法与实现二叉堆时所用到的技巧相同。 3 由于嵌套循环每趟花费N次迭代，因此插入排序为O(N^2)，而且这个界是精确的，因为以反序输入可以达到该界。另一方面，如果输入数据已预先排序，那么运行时间为O(N),因为内层for循环的检测总是立即判定不成立而终止。 # 一些简单排序算法的下界 1 数字数组的一个逆序是指数组中具有iA[j]的序偶(A[i],A[j])。 2 注意，这正好是需要由插入排序(非直接）执行的交换次数。 3 于是，若逆序数是O(N),则插入排序以线性时间运行。 4 我们可以通过计算排列中的平均逆序数而得出插入排序平均运行时间的精确的界。 5 定理7.1 N个互异树的数组的平均逆序数是N(N-1)/4。 6 定理7.2 通过交换相邻元素进行排序的任何算法平均需要Ω(N^2)时间 7 这个下界告诉我们，为了使一个排序算法以亚二次或o(N^2)时间运行，必须执行一些比较，特别要对相距较远的元素进行交换。 # 希尔排序 1 它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。由于这个原因，希尔排序有时也叫做缩小增量排序。 2 希尔排序使用一个序列h1,h2,...,ht,叫做增量序列。只要h1=1,任何增量序列都是可行的，不过，有些增量序列比另外一些增量序列更好(后面我们将讨论这个问题)。在使用增量hk的一趟排序之后，对于每一个i， 我们有A[i]<=A[i+hk](这里它是有意义的),所有相隔hk的元素都被排序。此时称文件是hk-排序的。 3 希尔排序的一个重要性质(我们只叙述不证明)是一个hk-排序的文件(此后将是hk-1排序的)保持它的hk-排序性。 4 hk-排序的一般做法是，对于hk,hk+1,...,N-1中的每一个位置i,把其上的元素放到i,i-hk,i-2hk...中间的正确位置上。一趟hk-排序的作用就是对hk个独立的子数组执行一次插入排序。 5 增量排序的一种流行(但是不好)的选择是使用Shell建议的序列：ht=[N/2]和hk=[hk+1/2]。 6 即使是一个小的改变都可能剧烈地影响算法的性能 //希尔排序的最坏情形分析 1 希尔排序的运行时间依赖于增量序列的选择，而证明可能相当复杂。 2 定理7.3 使用希尔增量时希尔排序的最坏情形运行时间为θ(N^2) 3 Hibbard提出一个稍微不同的增量序列，它在实践中(并且理论上)给出更好的结果。他的增量形如1，3，7，...,2^k-1。虽然这些增量几乎是相同的，但关键的区别是相邻的增量没有公因子。 4 定理7.4 使用Hibbard增量的希尔排序的最坏情形运行时间为θ(N^(3/2)) 5 Sedgewick提出了几种增量序列，经验研究指出，在实践中这些序列的运行要比Hibbard的好得多，其中最好的是序列{1,5,19,41,100,...},该序列中的项或者是9*4^4-9*2^i+1，或者是4^i-3*2^i+1。通过将这些值放到一个数组中 可以最容易地实现该算法。 6 希尔排序是算法非常简单又具有极其复杂的分析的一个好例子。 # 堆排序 1 优先队列可以用于花费O(NlogN)时间的排序。基于该想法的算法叫做堆排序，它给出我们至今所见到的最佳的大O运行时间。然而，在实践中它却慢于使用Sedgewick增量序列的希尔排序。 2 该算法的主要问题在于它使用了一个附加的数组。因此，存储需求增加一倍。避免使用第二个数组的聪明做法是利用这样的事实：在每次DeleteMin之后，堆缩小了1。因此，位于堆中最后的单元可以用来存放刚刚删去的元素。 3 使用这种策略，在最后一次DeleteMin后，该数组将以递减的顺序包含这些元素。 4 照通常的习惯，每一件事都是在数组中完成的。第一步以线性时间建立一个堆。然后通过将堆中的最后元素与第一个元素交换，缩减堆的大小并进行下滤，来执行N-1次DeleteMax操作。当算法终止时，数组则以所排的顺序包含这些元素。 //堆排序的分析 1 定理7.5 对N个互异项的随机排列进行堆排序，所用的平均比较次数为2NlogN-O(NloglogN). # 归并排序 1 归并排序以O(NlogN)最坏情形运行时间运行，而所使用的比较次数几乎是最优的。它是递归算法一个很好的实例。 2 这个算法中基本的操作是合并两个已排序的表。因为这两个表是已排序的，所以若将输出放到第三个表中，则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是取两个输入数组A和B，一个输出数组C，以及三个计数器Aptr, Bptr,Cptr,它们初始置于对应数组的开始端。A[Aptr]和B[Bptr]中的较小者被拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完的时候，则将另一个表中的剩余部分拷贝到C中。 3 因此，归并排序算法很容易描述。如果N=1，那么只有一个元素需要排序，答案是显然的。否则，递归地将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后使用上面描述的合并算法再将这两部分合并到一起。 该算法是经典的分治策略，它将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段解得的各个答案修补到一起。 4 如果对Merge的每个递归调用均局部声明一个临时数组，那么在任意时刻就可能有logN个临时数组处于活动期，这对于小内存的机器是致命的。另一方面，如果Merge例程动态分配并释放最小量临时内存，那么由malloc占用的时间会很多。 严密测试指出，由于Merge位于MSort的最后一行，因此在任意时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分。我们将使用与输入数组A相同的部分，这就达到本节末尾描述的改进。 //归并排序的分析 1 归并排序是用于分析递归例程方法的经典实例：必须给运行时间写出一个递归关系。 2 虽然归并排序的运行时间是O(NlogN)，但是它很难用于主存排序，主要问题在于合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加的工作，其结果是严重放慢了排序的速度。 这种拷贝可以通过再递归交替层次时审慎地转换A和TmpArray地角色来得到避免。 # 快速排序 1 像归并排序一样，快速排序也是一种分治的递归算法。将数组S排序的基本算法由下列简单的四步组成： > 如果S中元素的个数为0或1，则返回。 > 取S中任意元素v,称之为枢纽元(pivot)。 > 将S-{v}(S中其余元素)分成两个不相交的集合: S1={x∈S-{v} | x<=v}和S2={x∈S-{v} | x>=v}。 > 返回{quicksort(S1)后，继而v,继而quicksort(S2)}。 2 由于对那些等于枢纽元的元素的处理，第3步分割的描述不是唯一的，因此这就成了一个设计上的决策。直观地看，我们希望把等于枢纽元的大约一半的关键字分到S1中，而另一半分到S2中，很像我们希望二叉查找树保持平衡一样。 3 快速排序更快的原因在于，第3步的分割实际上是在适当的位置进行并且非常高效，它的高效太大弥补了大小不等的递归调用的缺憾。 4 实现第2步和第3步有许多方法，这里介绍的方法是大量分析和经验研究的结果，它代表实现快速排序的非常有效的方法，哪怕是对该方法最微小的偏差都可能引起意想不到的不良结果。 //选取枢纽元 1 一种安全的方针是随机选取枢纽元 2 三数中值分割法：一组N个数的中值是第[N/2]个最大的数。枢纽元的最好选择是数组的中值。不幸的是，这很难算出，且会明显减慢快速排序的速度。因此一般的做法是使用左端，右端，和中心位置上的三个元素的中值作为枢纽元。 //分割策略 1 该方法的第一步是通过将枢纽元与最后的元素交换使得枢纽元离开要被分割的数据段。i从第一个元素开始而j从倒数第二个元素开始。 2 在分割阶段要做的就是把所有小元素移到数组的左边而把所有大元素移到数组的右边。当然，"小"和"大"是相对于枢纽元而言的。 3 当i在j的左边时，我们将i右移，移过那些小于枢纽元的元素，并将j左移，移过那些大于枢纽元的元素。当i和j停止时，i指向一个大元素，而j指向一个小元素。如果i在j的左边，那么将这两个元素互换，其效果是把一个大元素移向右边 而把一个小元素移向左边。重复该过程直到i和j彼此交错为止。i和j已经交错，故不再交换。分割的最后一步是将枢纽元与i所指向的元素交换。 4 如果i和j遇到等于枢纽元的关键字，那么我们就让i和j都停止。 //小数组 1 对于很小的数组(N<=20)，快速排序不如插入排序好。 2 通常的解决办法是对于小的数组不是递归地使用快速排序，而是使用诸如插入排序这样对小数组有效的排序算法。一种好的截至范围是N=10。 //实际的快速排序例程 1 第8行的Swap为了速度上的考虑有时显式写出。为使算法速度块，需要迫使编译器以直接插入的方式编译这些代码。 //选择的线性期望时间算法 1 我们介绍的查找集合S中第k个最小元的算法几乎与快速排序相同。事实上，其前三步是一样的。我们将把这种算法叫做快速选择。令|Si|为Si中元素的个数。快速选择的步骤如下： > 如果|S|=1，那么k=1,并将S中的元素作为答案返回。如果使用小数组的截至方法且|S|<=CUTOFF,则将S排序并返回第k个最小元。 > 选取一个枢纽元v∈S > 将集合S-{v}分割成S1和S2,就像我们在快速排序中做的那样。 > 如果k<=|S1|,那么第k个最小元必然在S1中。在这种情况下，返回quickselect(S1,k)。如果k=1+|S1|,那么枢纽元就是第k个最小元，我们将它作为答案返回。否则，这第k个最小元就在S2中，它是S2中的第(k-|S1|-1)个最小元。我们进行 一次递归调用并返回quickselect(S2,k-|S1|-1)。 # 大型结构的排序 1 常常需要通过某个关键字对大型结构进行排序。 1 在这种情况下，实际的解法是让输入数组包含指向结构的指针。我们通过比较指针指向的关键字，并在必要时交换子帧来进行排序。这意味着，所有的数据运动基本上就像我们对整数排序那样进行，我们称之为间接排序。可以使用 这种方法处理我们已经描述过的大部分数据结构。 # 排序的一般下界 1 1 本书证明任何只用到比较的算法在最坏情形下需要Ω(NlogN)次比较(从而需要Ω(NlogN)时间)，因此归并排序和堆排序在一个常数因子范围内是最优的。可以进一步证明即使是在平均情形下，只用到比较地任意排序算法都需要进行 Ω(NlogN)次比较。这意味着，快速排序在相差一个常数因子的范围内平均是最优的。 2 只用到比较的任意排序算法在最坏情形下都需要[log(N!)]次比较并平均需要log(N!)次比较。我们将假设所有N个元素是互异的，因为任何排序算法都必须在这种情况下正常运行。 //决策树 1 决策树是用与证明下界的抽象概念。在这里，决策树是一颗二叉树。每个节点表示在元素之间一组可能的排序，它与已经进行的比较一致。比较的结果是树的边。 2 我们将互换地使用术语状态和节点。 3 只使用比较进行排序地每一种算法都可以用决策树表示。当然，只有输入数据非常少的情况下画决策树才是可行的。排序算法所使用的比较次数等于最深的树叶的深度。所使用的比较的的平均次数等于树叶的平均深度。 4 引理7.1 令T是深度为d的二叉树，则T最多有2^d片树叶 5 引理7.2 具有L片树叶的二叉树的深度至少是[logL] 6 定理7.6 只使用元素间比较的任何排序算法在最坏情形下至少需要[log(N!)]次比较 7 定理7.7 只使用元素间比较的任何排序算法需要进行Ω(NlogN)次比较。 8 当用于证明最坏情形结果时，这种类型的下界论断有时叫做信息-理论下界。 # 桶式排序 1 但我们要记住，在某些特殊情况下以线性时间进行排序仍然是可能的。 2 为使桶式排序嫩巩固正常工作，必须要有一些额外的信息。输入数据A1,A2,...,AN必须只由小于M的正整数组成。(显然还可以对其进行扩充)如果是这种情况，那么算法很简单：使用一个大小为M称为Count的数组，它被初始化为全0. 于是，Count有M个单元(或称桶)，这些桶初始化为空，当读Ai时，Count[Ai]增1。在所有的输入数据读入后，扫描数组Count,打印出排序后的表。该算法用时O(M+N)。如果M为O(N)，那么总量就是O(N) 3 很自然地，如果存在额外的可用信息，我们应该有望找到更为有效的算法，否则这些额外信息就浪费了。 # 外部排序 1 大部分内部排序都用到内存可直接寻址的事实。希尔排序用一个时间单位比较元素A[i]和A[i-hk]。堆排序用一个时间单位比较元素A[i]和A[i*2+1]。使用三数中值分割法的快速排序以常数个时间单位比较A[left],A[Center],A[Right]。 如果输入数据在磁盘，那么所有这些操作就失去了它们的效率。因为在磁带上的元素只能被顺序访问。 //外部排序模型 1 各种各样的海量存储装置使得外部排序比内部排序对设备的依赖性要严重得多。我们将考虑的一些算法在磁盘上工作，而磁带可能是最受限制的存储媒体。由于访问磁带上的一个元素需要把磁带转动到正确的位置，因此磁带必须要有(两个 方向上）连续的顺序才能够被有效地访问。 2 我们将假设至少有3个磁带驱动器进行排序工作。我们需要两个驱动器执行有效的排序，而第三个驱动器进行一些简化的工作。如果只有一个磁带驱动器可用，那么我们不得不说，任何算法都将需要Ω(N^2)次磁带访问。 //简单算法 1 基本的外部排序算法使用归并排序中的Merge例程。 //多路合并 1 如果有额外的磁带，那么我们可以减少将输入数据排序所需要的趟数，通过将基本的2-路合并扩充为k-路合并就能做到这一点。 2 两个顺串的合并操作通过将每一个输入磁带转到每个顺串的开头来完成。然后，找到较小的元素，把它放到输出磁带上，并将相应的输入磁带向前推进。如果有k盘输入磁带，那么这种方法以相同的方式工作，唯一的区别在于，它发现k个元素 中最小的元素的过程稍微有些复杂，我们可以通过使用优先队列找出这些元素中的最小元。为了得出下一个写到磁盘上的元素，我们进行一次DeleteMin操作。将相应的磁带向前推进，如果在输入磁带上的顺串尚未完成，那么我们将新元素 插入优先队列中。 //替换选择 1 读入尽可能多的记录并将它们排序，再把结果写到某个磁带上。这看起来像是最可能的最佳处理，直到实现只要第一个记录被写到输出磁带上，它所使用的内存就可以被另外的记录使用。如果输入磁带上的下一个记录比我们刚刚输出的记录大， 那么他就可以被放入这个顺串中。 2 利用这个想法，我们可以给出产生顺串的一个算法，该方法通常称为替换选择。开始，M个记录被读入内存并放到一个优先队列中。我们执行一次DeleteMin，把最小的记录写到输出磁带上，再从输入磁带读入下一个记录。如果它比刚刚 写出的记录大，那么可以把它放到优先队列中，否则，不能把它放入当前的顺串。由于优先队列缺少一个元素，因此，我们可以把这个新元素存入优先队列的死区，直到顺串完成构建，而该新元素用于下一个顺串。将一个元素存入死区的 做法类似于在堆排序中的做法。我们继续这样的步骤直到优先队列的大小为0，此时该顺串构建完毕。我们使用死区中的所有元素通过建立一个新的优先队列开始构建一个新的顺串。 ### 不相交集 ADT 1 解决等价问题的一种有效数据结构 2 每次操作只需要常数平均时间 3 因为它的分析极其困难，最坏情况下的函数形式不同于我们已经见过的任何形式 # 等价关系 1 若对于每一对元素(a,b),a,b∈S,aRb或者为true或者为false,则称在集合S上定义关系R。如果aRb是true,那么我们说a和b有关系. 等价关系是满足下列三个性质的关系R: 1 (自反性)对于所有的a∈S,aRa, 2 (对称性)aRb当且仅当bRa 3 (传递性)若aRb且bRc则aRc 2 电气连接是一个等价关系 # 动态等价性问题 1 给定一个等价关系"~",一个自然的问题是对任意的a和b,确定是否a~b。问题在于，这种关系的定义通常不明显而是相当隐秘的。 2 一个元素a∈S的等价类是S的一个子集，它包含所有与a有关系的元素。注意，等价类形成对S的一个划分：S的每一个成员恰好出现在一个等价类中。为确定是否a~b,我们只需验证a和b是否都在同一个等价类中。 3 输入数据最初是N个集合的类，每个集合含有一个元素。初始的描述是所有的关系均为false(自反的关系除外)。每个集合都有一个不同的元素，从而Si∩Sj=∅；这使得这些集合不相交。 4 该算法是动态的，因为在算法执行的过程中，集合可以通过Union运算发生改变。这个算法还必然是联机操作：当Find执行时，他必须给出答案算法才能继续进行。另一种可能是脱机算法：该算法需要观察全部的Union和Find序列。 5 注意，我们不进行任何比较元素相关的值的操作，而是只需要知道它们的位置。由于这个原因，我们假设所有的元素均已从1到N顺序编号并且编号方法容易由某个散列方案确定。于是，开始时我们有Si={i},i=1到N。 6 Find(a)=Find(b)当且仅当a和b在同一个集合中。 7 这些运算在许多图论问题中是重要的，在一些处理等价(或类型)声明的编译程序中也很重要。 8 解决动态等价问题的方案有两种。一种方案保证指令Find能够以常数最坏情形运行时间执行，而另一种方案则保证指令Union能够以常数最坏情形运行时间执行。 9 为使Find运算快，可以在一个数组中保存每个元素的等价类的名字。 10 一种想法是将所有在同一个等价类中的元素放到一个链表中。 # 基本数据结构 1 记住，我们的问题不要求Find操作返回任何特定的名字，而只是要求当且仅当两个元素属于相同的集合时，作用在这两个元素上的Find返回相同的名字。一种想法是可以使用树来表示每一个集合，因为树上的每一个元素都有相同的根。 这样，该根就可以用来命名所在的集合。我们将用树表示每一个集合。 2 数组的每个成员P[i]表示元素i的父亲。如果i是根，那么P[i]=0。 3 我们采纳了在Union(X,Y)后新的根是X的约定。 4 对元素X的一次Find(X)操作通过返回包含X的树的根而完成。 5 平均运行时间依赖于模型。 # 灵巧求并算法 1 使得总让较小的树成为较大的树的子树；我们把这种方法叫做按大小求并(union-by-size)。 2 我们可以证明，如果这些Union都是按照大小进行的，那么任何节点的深度均不会超过logN。 3 可以让每个根的数组元素包含它的树的大小的负值。这样一来，初始时树的数组表示就都是-1了。当执行一次Union时，要检查树的大小；新的大小是老的大小的和。 4 另一种实现方法为按高度求并，它同样保证所有的树的深度最多是O(logN)。我们跟踪每棵树的高度而不是大小并执行那些Union使得浅的树成为深的树的子树。这是一种平缓的算法，因为只有当两颗相等深度的树求并时树的高度才增加 (此时树的高度增1) # 路径压缩 1 而且应该清楚，对于Union算法恐怕没有更多改进的可能。这是基于这样的观察：执行Union操作的任何算法都将产生相同的最坏情形的树，因为它必然会随意打破树间均衡。 因此，无须对整个数据结构重新加工而使算法加速的唯一方法是对Find操作做些更聪明的工作。 2 这种聪明的操作叫做路径压缩。路径压缩在一次Find操作期间执行，而与用来执行Union的方法无关。设操作为Find(X)，此时路径压缩的效果是，从X到根的路径上的每一个节点都使它的父节点变成根。 3 路径压缩与按大小求并完全兼容，这就使得两个例程可以同时实现。不过后面我们将会看到，路径压缩与灵巧求并法则的结合在所有情况下都将产生非常有效的算法。 4 路径压缩并不完全与按高度求并兼容，因为路径压缩可以改变树的高度。我们根本不清楚如何有效地去重新计算它们。答案是不去计算！此时，对于每棵树所存储的高度是估计的高度(有时称为秩(rank))，但实际上按秩求并(演变至今） 理论上和按大小求并效率是一样的。不仅如此，高度的更新也不如大小的更新频繁。 # 按秩求并和路径压缩的最坏情形 ? ### 图论算法 1 这些算法不仅在实践中有用，而且因为在许多实际生活的应用中若不仔细注意数据结构的选择将导致速度过慢，所以这些算法还是非常有趣的。 # 若干定义 1 一个图(graph)G=(V,E)由顶点(vertex)的集V和边(edge)的集E组成。每一条边就是一幅点对(v,w)，其中v,w∈V。 2 有时也把边称作弧(arc) 3 如果点对是有序的，那么图就是有向(directed)的。 4 有向的图有时也叫做有向图(digraph)。 5 顶点v和w邻接(adjacent)当且仅当(v,w)∈E。 6 在一个具有边(v,w)从而具有边(w,v)的无向图中，w和v邻接且v也和w邻接。有时候边还具有第三种成分，称作权(weight)或值(cost)。 7 图中的一条路径(path)是一个顶点序列w1,w2,w3,...,wN使得(wi,wi+1)∈E,1<=i<=N. 8 这样一条路径的长(length)是该路径上的边数，它等于N-1。从一个顶点到它自身可以看作一条路径；如果路径不包含顶点，那么路径的长为0。这是定义特殊情形的一种方便的方法。 9 如果图含有一条从一个顶点到它自身的边(v,v)，那么路径v,v有时侯也叫做一个环(loop)。 10 一条简单路径是这样一条路径：其上的所有顶点都是互异的，但第一个顶点和最后一个顶点可能相同。 11 有向图中的圈(cycle)是满足w1=wN且长至少为1的一条路径；如果该路径是简单路径，那么这个圈就是简单圈。对于无向图，我们要求边是互异的。这些要求的根据在于无向图中的路径u,v,u不应该视为圈，因为(u,v)和(v,u)是同一条边。 但是在有向图中，它们是两条不同的边，因此称它们为圈是有意义的。如果一个有向图没有圈，则称其为无圈的(acyclic)。一个有向无圈图有时也简称为DAG。 12 如果在一个无向图中从每一个顶点到每个其他顶点都存在一条路径，则称该无向图是连通(connected)的。具有这样性质的有向图称为强连通的(strongly connected)。 13 如果一个有向图不是强连通的，但是它的基础图(underlying connected)，即其弧上去掉方向所形成的图，是连通的，那么该有向图称为弱连通的(weakly connnected)。 14 完全图(complete graph)是其每一对顶点间都存在一条边的图。 # 图的表示 1 表示图的一种简单的方法是使用一个二维数组，称为邻接矩阵(adjacent matrix)表示法。对于每条边(u,v)，我们置A[u][v]=1；否则，数组的元素就是0。如果边有一个权，那么我们可以置A[u][v]等于该权， 而使用一个很大或者很小的权作为标记表示不存在的边。 2 虽然这么表示的有点是非常简单，但是，它的空间需求则为θ(|V|^2)，如果图的边不是很多，那么这种表示的代价就太大了。若图是稠密的：|E|=θ(|V|^2)，则邻接矩阵是合适的表示方法。 如果图是稀疏的，则更好的解决办法是使用邻接表(adjacency list)表示。对每一个顶点，我们使用一个表存放所有邻接的顶点。此时的空间需求为O(|E|+|V|)。 3 邻接表是表示图的标准方法。无向图可以类似地表示：每条边(u,v)出现在两个表中，因此空间的使用基本上是双倍的。 # 拓扑排序 1 拓扑排序是对有向无圈图的顶点的一种排序，它使得如果存在一条从vi到vj的路径，那么在排序中vj出现在vi的后面。 2 此外，排序不必是唯一的；任何合理的排序都是可以的。 3 一个简单的求拓扑排序的算法是先找出任意一个没有"进入边"的顶点。然后我们显印出该顶点，并将它和它的边一起从图中删除。然后，我们对图的其余部分同样应用这样的方法处理。 4 我们把顶点v的入度(indegree)定义为边(u,v)的条数。我们计算图中所有顶点的入度。 5 我们可以通过将所有(未分配拓扑编号)的入度为0的顶点放在一个特殊的盒子中而消除这种无效的劳动。当我们降低这些邻接顶点的入度时，检查每一个顶点并在它的入度降为0时把它放入盒子中。 6 为实现这个盒子，我们可以使用一个栈或队列。首先，对每一个顶点计算它的入度。然后，将所有入度为0的顶点放入一个初始为空的队列中。当队列不空时，删除一个顶点v，并将与v邻接的所有的顶点的入度减1。只要一个顶点的入度降为0， 就把该顶点放入队列中。此时，拓扑排序就是顶点出队的顺序。 7 如果使用邻接表，那么执行这个算法所用的时间为O(|E|+|V|)。 # 最短路径算法 1 与每条边(vi,vj)相联系的是穿越该弧的代价(或称为值)ci,j。一条路径v1,v2,...,vN的值是ci,i+1，从i=1到i=N-1的和，叫做赋权路径长。而无权路径长只是路径上的边数，即N-1。 //单源最短路径问题 1 给定一个赋权图G=(V,E)和一个特定顶点s作为输入，找出从s到G中每一个其他顶点的最短赋权路径。 2 因为我们可以在循环中滞留任意长。这个循环叫做负值圈；当它出现在图中时，最短路径问题就是不确定的。有负值的边未必就是坏事，但是它们的出现似乎使问题增加了难度。为方便起见，在没有负值圈时，从s到s的最短路径为0. 3 当前，还不存在找出从s到一个顶点的路径比找出从s到所有顶点路径更快(快一个常数因子)的算法。 //无权最短路径 1 使用某个顶点s作为输入参数，我们想要找出从s到所有其他顶点的最短路径。 2 这种搜索一个图的方法称为广度优先搜索。该方法按层处理顶点：距开始点最近的那些顶点首先被赋值，而最远的那些顶点最后被赋值。这很像对树的层序遍历。 3 开始的时候，除s外所有的顶点都是不可达的，而s的路径长为0.pv栏中的项为簿记变量，它将使我们能够显印出实际的路径。Know中的项在顶点被处理以后置为1.起初，所有的顶点都不是Know，包括开始顶点。当一个顶点被标记为已知时， 我们就有了不会再找到更便宜的路径的保证，因此对该顶点的处理实质上已经完成。 4 通过追溯pv变量，可以显印出实际的路径。由于双层嵌套for循环，因此该算法的运行时间为O(|V|^2)。 5 在迭代开始的时候，队列只含有距离CurrDist的那些顶点。当我们添加距离CurrDist+1的那些邻接顶点时，由于它们自队尾入队，因此这就保证它们直到所有距离为CureDist的顶点都处理完之后才处理。在距离CurrDist处的最后一个 顶点出队并处理之后，队列只含有距离为CurrDist+1的顶点，因此该过程将不断进行下去。 6 再有，如果某些顶点从开始节点出发是不可达的，那么有可能队列会过早地变空。在这种情况下，将对这些节点报出Infinity(无穷)距离，这就完全合理了。最后,Know域没有使用；一个顶点一旦被处理它就从不再进入队列，因此它不需要 重新处理的事实就意味着被做了标记。这样一来，Know域可以去掉。 7 只要使用邻接表，则运行时间就是O(|E|+|V|) //Dijkstra算法 1 如果图是赋权图，那么问题(明显)就变得困难了，不过我们任然可以使用来自无权情形时的想法。 2 我们保留所有与前面相同的信息。因此，每个顶点或者标记为Know的，或者标记为unknow的。像以前一样，对每一个顶点保留一个临时距离dv。这个距离实际上是使用已知顶点作为中间顶点从s到v的最短路径的长。和以前一样，我们记录pv. 它是引起dv变化的最后的顶点。 3 解决单源最短路径问题的一般方法叫做Dijkstra算法。这个有30年历史的解法是贪婪算法(greedy algorithm)最好的例子。贪婪算法一般分阶段求解一个问题，在每个阶段他都把出现的当作是最好的去处理。 4 贪婪算法主要的问题在于该算法不总成功。为了找还15美分的零钱，如添加12美分一个的货币则可破坏这种找零钱算法，因为此时它给出的答案(一个12份币和3个1分币)不是最优的(一个角币和一个5分币）。 5 Dijkstra算法按阶段进行。在每个阶段，Dijkstra算法选择一个顶点v，它在所有未知顶点中具有最小的dv，同时算法声明从s到v的最短路径是已知的。阶段的其余部分由dw值的更新工作组成。 6 在无权的情形下，若dw=∞则置dw=dv+1。 7 使用通向w路径上的顶点v是不是一个好主意由算法决定。 8 v5是邻接的店但不做调整，因为经过v2的值为2+10=12而长为3的路径已经是已知的。 9 然后选取v3,对v6的距离下调到3+5=8。下一个选取的顶点是v7,v6下调到5+1=6。最后我们选择v6。 10 为了显印出从开始顶点到某个顶点v的实际路径，我们可以编写一个递归例程跟踪p数组留下的痕迹。 11 开始的顶点被传递到初始化例程中。这是代码中需要知道顶点的唯一位置。 12 只要没有边是负的值，该算法总能够顺利完成。如果任何一边出现负值，则算法可能得出错误的答案。 13 运行时间依赖于对表的处理方法，我们必须考虑。 14 如果图是稠密的，边数|E|=θ(|V|^2)，则该算法不仅简单而且基本上最优，因为它的运行时间与边数成线性关系。 15 如果图是稀疏的，边数|E|=θ(|V|)，那么这种算法就太慢了。在这种情况下，距离需要存储在优先队列中。 16 因为一旦未知的最小值顶点被找到，那么它就不再是未知的，必须从未来的考虑中除去。 17 一种方法是把更新处理成DecreaseKey操作。 18 由于优先队列不是有效地支持Find操作，因此di的每个值在优先队列的位置将需要保留并当di在优先队列中改变时更新。如果优先队列是用二叉堆实现的，那么这将很难办。如果使用配对堆，则程序不会太差。 19 另一种方法是在每次执行第9行时把w和新值dw插入优先队列。这样，在优先队列中的每个顶点就可能有多于一个的代表。 20 但是，队列的大小可能达到|E|这么大。 21 注意，对于一些诸如计算机邮件和大型公交传输的典型问题，它们的图一般是非常稀疏的，因为大多数顶点只有两条边。 22 不用说，这种问题没有平均情形的时间分析，因为连如何建立随机图的模型甚至都不是明显的。 //具有负边值的图 1 如果图具有负的边值，那么Dijkstra算法是行不通的。问题在于，一旦一个顶点u被声明是已知的，那就可能从某个另外的未知顶点v有一条回到u的负的路径。在这样的情形下，选取从s到v再回到u的路径要比从s到u但不过v更好。 2 把赋权的和无权的算法结合起来将会解决这个问题。开始，我们把s放到队列中。然后，在每一阶段让一个顶点v出队。找出所有与v邻接的顶点w，使得dw>dv+cv,w。然后更新dw和pw，并在w不在队列中的时候把它放到队列中。可以为每个 每个顶点设置一个位(bit)以指示它在队列中出现的情况。我们重复这个过程直到队列空为止。 3 每个顶点最多可以出队|V|次，因此，如果使用邻接表则运行时间是O(|E|*|V|)。 //无圈图 1 如果知道图是无圈的，那么我们可以通过改变声明顶点为已知的顺序(或者叫做顶点选取法则)来改进Dijkstra算法。新法则是以拓扑顺序选择顶点。由于选择和更新可以在拓扑排序执行的时候进行，因此算法能够一趟完成。 2 因为当一个顶点v被选取以后，按照拓扑排序的法则他没有从未知顶点发出的进入边，因此它的距离dv可以不再被降低，所以这种选择法则是行得通的。 3 使用这种选择法则不需要优先队列：由于选择花费常数时间，因此运行时间为O(|E|+|V|) 4 无圈图的一个更重要的用途是关键路径分析法。 5 每个节点表示一个必须执行的动作以及完成动作所花费的时间。因此，该图叫做动作节点图。图中的边代表优先关系：一条边(v,w)意味着动作v必须在动作w开始前完成。当然，这就意味着图必须是无圈的。我们假设任何(直接或间接) 互相不依赖的动作可以由不同的服务器并行地执行。 6 这种类型的图可以(并常常)用来模拟方案的构建。在这种情况下，有几个问题需要回答。首先，方案最早完成时间是何时？另一个重要的问题是确定哪些动作可以延迟，延迟多长，而不至影响最少完成时间。另一方面，动作B欠重要，可以被 延迟两个时间单位而不至于影响最后完成时间。 7 我们把动作节点图转化成事件节点图。每个事件对应一个动作和所有与它无关的动作的完成。从事件节点图中的节点v可达到的事件可以在事件v完成后开始。哑边和哑节点可能需要被插入到一个动作依赖于几个其他动作的地方。为了避免 引进假相关性(或相关性的假的短缺)，这么做是必要的。 8 为了找出方案的最早完成时间，我们只要找出从第一个事件到最后一个事件的最长路径的长。对于一般的图，最长路径问题通常没有意义。因为可能有正值的圈存在。这些正值圈等价于最短路问题中的负值圈。在这种情况下，容易采纳 最短路径算法计算图中所有节点最早完成时间。 9 对于每个顶点，通过保存一个所有邻接且在先的顶点的表，这些值就可以以线性时间算出，借助顶点的拓扑顺序计算它们的最早完成时间，而最晚完成时间则通过倒转它们的拓扑顺序来计算。 10 事件节点图中每条边的松弛时间代表对应动作可以延迟而不推迟整体的完成的时间量。 11 某些动作的松弛时间为0，这些动作是关键性的动作，它们必须按计划结束。至少存在一条完全由零松弛边组成的路径，这样的路径是关键路径。 # 网络流问题 1 有两个顶点，一个是s，称为发点，一个是t，称为收点。对于任意一条边(v,w)，最多有"流"的cv,w个单位可以通过。在既不是发点s又不是收点t的任意顶点v，总的进入的流必须等于总的发出的流。最大流问题就是确定从s到t可以通过 的最大流量。 2 正如问题叙述中所要求的，没有边负载超过它的容量的流。 3 一个顶点可以以它喜欢的任何方式结合和发送流，只要不违反边的容量以及保持流守恒(进入的必须是流出的)。 //一个简单的最大流算法 1 解决这种问题的首要想法是分阶段进行。 2 Gf表示在算法的任意阶段已经到达的流。开始时Gf的所有的边都没有流，我们希望当算法终止时Gf包含最大流。 3 我们还构造一个图Gr,称为残余图，它表示对于每条边还能再添加多少流。对于每一条边，我们可以从容量中减去当前的流而计算出残余的流。Gr的边叫做残余边。 4 在每个阶段，我们寻找图Gr中从s到t的一条路径，这条路径叫做增长通路。这条路径上的最小值边就是可以添加到路径上每一边上的流的量。我们通过调整Gf和重新计算Gr做到这一点。 5 当发现在Gr中没有从s到t的路径时算法终止。这个算法是不确定的，因为是随便选择的从s到t的任意的路径。 6 要记着这个算法有一个小缺陷。 7 我们将采取约定：一旦注满(使饱和)一条边，则这条边就要从残余图中除去。 8 由于t从s出发是不可达的，因此算法到此终止。 9 对于流图中具有流fv,w的每一条边(v,w)，我们将在残余图中添加一条容量为fv,w的边(w,v)。 10 通过从d到a导入2个单位的流算法从边(a,d)取走两个单位的流，因此本质上改变了它的意向。 11 奇怪的是，可以证明，如果边的容量都是有理数，那么该算法总以最大流终止。 12 避免这个问题的简单方法是总选择容许在流中最大增长的增长通路。而对Dijkstra算法的单线修改将会完成这项工作。如果capmax为最大边容量，那么可以证明，O(|E|log capmax)条增长通路将足以找到最大流。 13 另一种选择增长通路的方法是总选取具有最少边数的路径。 # 最小生成树 1 我们将要考虑的下一个问题是在一个无向图中找出一颗最小生成树的问题。这个问题对有向图也是有意义的，不过找起来更困难。 2 大体上，一个无向图G的最小生成树就是由该图的那些连接G的所有顶点的边构成的数，且其总价值最低。当且仅当G是连通的存在最小生成树。 3 虽然一个强壮的算法应该指出G不连通的情况，但是我们还是假设G是连通的，而把算法的健壮性作为练习留给读者。 4 注意，在最小生成树中边的条数为|V|-1。最小生成数是一颗数，因为它无圈；因为最小生成树包含每一个顶点，所以它是生成树；此外，它显然是包含图的所有顶点的最小的树。 5 如果我们需要用最少的电线给一所房子安装电路，那就需要解决最小生成树问题。 6 对于任意生成树T，如果将一条不属于T的边e添加进来，则产生一个圈。如果从该圈中除去任意一条边，则又恢复生成树的特性。如果边e的值比除去的边的值低，那么新的生成树的值就比原生成树的值低。如果在建立生成树时所添加的边 在所有避免成圈的边中值最小，那么最后得到的生成树的值不能再改进，因为任意一条替代的边都将与已经存在于该生成树中的一条边至少具有相同的值。它指出，对于最小生成树这种贪欲是成立的。我们介绍两种算法，它们的区别 在于最小(值的)边如何选取上。 //prim算法 1 计算最小生成树的一种方法是使其连续地一步步长成。在每一步，都要把一个节点当作根并往上加边，这样也就把相关联的顶点加到增长中的树上。 2 在算法的任意时刻，我们都可以看到一个已经添加到树上的顶点集，而其余顶点尚未加到这棵树中。此时，算法在每一阶段都可以通过选择边(u,v)使得(u,v)的值是所有u在树上但v不再树上的边的值中的最小者而找出一个新的顶点 并把它添加到这棵树中。开始时，v1在构建中的树上，它作为树的根但是没有边。每一步添加一条边和一个顶点到树上。 3 这里,dv是连接v到已知顶点的最短弧的权，而pv则是导致dv改变的最后一个顶点。 4 不过要注意，Prim算法是在无向图上运行的，因此当编写代码的时候要记住把每一条边都要放到两个邻接表中。不用堆时的运行时间为O(|V|^2)，它对于稠密的图来说是最优的。使用二叉堆的运行时间是O(|E|log|V|)，对于稀疏的图它 是一个好的界。 //Kruskal算法 1 第二种贪婪策略是连续地按照最小的权选择边，并且当所选的边不产生圈时就把它作为所选定的边。开始的时候，存在|V|颗单节点树，而添加一边则将两棵树合并成一棵树。当算法终止的时候，就只有一棵树了，这棵树就是最小生成树。 2 实际上，算法就是要决定边(u,v)应该添加还是应该舍弃。 3 在算法实施的任意时刻，两个顶点属于同一个集合当且仅当它们在当前的生成森林中连通。因此，每个顶点最初是在它自己的集合中。如果u和v在同一个集合中，那么连接它们的边就要舍弃，因为由于它们已经连通了，因此再添加边(u,v) 就会形成一个圈。如果这两个顶点不在同一个集合中，则将该边加入，并对包含顶点u和v的这两个集合实施一次Union。 # 深度优先搜索的应用 1 深度优先搜索是对先序遍历的一般化。我们从某个顶点v开始处理v，然后递归地遍历所有与v邻接的顶点。 2 如果我们对任意的图进行该过程，那么为了避免圈我们需要小心仔细。为此，当我们访问到一个顶点v的时候，由于当时已经到了该点处，因此可以标记该点是访问过的，并且对于那些尚未被标记的所有邻接顶点递归地调用深度优先搜索。 3 我们搜索一个未标记的节点，然后应用深度优先遍历，并继续这个过程知道不存在未标记的节点为止。 //无向图 1 当且仅当从任意节点开始的深度优先搜索访问到每一个节点，无向图是连通的。 2 我们以图形来描述深度优先生成树的步骤。该树的根是A,是第一个访问的顶点。图中的每一条边(v,w)都出现在树上。如果当我们处理(v,w)时发现w是未标记的，或当我们处理(w,v)时发现v是未标记的，那么我们就用树的一条边表示它。 如果当我们处理(v,w)时发现w已被标记，并且当我们处理(w,v)时发现v也已经被标记，那么我们就画一条虚线，并称之为背向边。表示这条"边"实际上不是树的一部分。 //双连通性 1 一个连通的无向图如果不存在被删除之后使得剩下的图不再连通的顶点，那么这样的无向连通图就称为双连通的。 2 如果一个图不是双连通的，那么，将其删除使图不再连通的那些顶点叫做割点。 3 深度优先搜索提供一种找出连通图中所有割点的线性时间算法。 //欧拉回路 1 我们必须在图中找出一条路径，使得该路径访问图的每条边恰好一次。如果我们要解决“附加的问题”，那么就必须找出一个圈，该圈经过每条边恰好一次。这种图论问题在1736年由欧拉解决，它标志着图论的诞生。 2 这种问题通常叫做欧拉路径(有时称欧拉环游）或欧拉回路问题。 3 其终点必须终止在起点上的欧拉回路只有当图是连通的并且每个顶点的度(即，边的条数)是偶数时才有可能存在。 4 这里，欧拉环游是必须访问图的每一边但最后不一定必须回到起点的路径。如果奇数度的顶点多于两个，那么欧拉环游也是不可能存在的。 5 所有顶点的度均为偶数的任何连通图必然有欧拉回路。 6 如果从起点出发的所有边均已用完，那么图中就会有部分遍历不到。最容易的补救方法是找出有尚未访问的边的路径上的第一个顶点，并执行另外一次深度优先搜索。这将给出另外一个问题，把它拼接到原来的回路上。继续该过程直到 所有的边都遍历到为止。 7 当所有的边都被遍历时，算法终止。 8 为使拼接简单，应该把路径作为一个链表保留。为避免重复扫描邻接表，对于每一个邻接表我们必须保留一个指向最后扫描到的边的指针。当拼接一个路径时，必须从拼接点开始搜索到顶点，从这个新顶点进行下一轮深度优先搜索。这将 保证整个算法期间对顶点搜索阶段所进行的全部工作量为O(|E|)。使用适当的数据结构，算法的运行时间为O(|E|+|V|) 9 一个非常相似的问题是在无向图中寻找一个简单的圈，该圈通过图的每一个顶点。这个问题称为哈密尔顿圈问题。虽然看起来这个问题似乎差不多和欧拉回路问题一样，但是，对它却没有已知的有效算法。 //有向图 1 也可以通过深度优先搜索以线性时间遍历有向图。如果图不是强连通的，那么从某个节点开始的深度优先搜索可能访问不了所有的节点。在这种情况下我们在某个未作标记的节点处开始，反复执行深度优先搜索，直到所有的节点都被访问 到。 2 深度优先搜索的一种用途是检测一个有向图是否是无圈图。法则如下：一个有向图是无圈图当且仅当它没有背向边。 3 进行拓扑排序的另一种方法是通过深度优先生成森林的后序遍历给顶点指定拓扑编号N,N-1,..,1。只要图是无圈的，这种排序就是一致的。 //查找强分支 1 通过执行两次深度优先搜索，我们可以检测一个有向图是否是强连通的，如果它不是强连通的，那么我们实际上可以得到顶点的一些子集，它们到其自身是强连通的。 # NP-完全性介绍 1 我们将看到，存在大量重要的问题，它们在复杂性上大体是等价的。这些问题形成一个类，叫做NP完全问题。这些NP完全问题精确的复杂度仍然需要确定并且在计算机理论科学方面仍然是最重要的开放性问题。或者所有这些问题有多项式时间 解法，或者它们都没有多项式时间解法。 2 这些“不可能”解出的问题叫做不可判定问题。 3 NP代表非确定型多项式时间(nondeterministic polynomial-time)。 4 检验一个问题是否属于NP的简单方法是将该问题用是/否问题的语言描述。如果我们能在多项式时间内证明一个问题的任意“是”的实例是正确的，那么该问题属于NP类。 5 还要注意，不是所有的可判定问题都属于NP。 //NP-完全问题 1 给定一完全图G=(V,E)，它的边的值以及整数K，是否存在一个访问所有顶点并且总值<=K的简单圈？ ### 算法设计技巧 1 我们看到，当一个算法给定时，实际的数据结构无须指定。为使运行时间尽可能地少，需要由编程人员来选择适当的数据结构 # 贪婪算法 1 实际上，所有的调度问题或者是NP-完全的(或类似的难度)，或者是贪婪算法可解的。 //一个简单的调度问题 1 我们将假设使用非预占调度：一旦开始一个作业，就必须把该作业运行完。 2 图10-3给出的调度是按照最短的作业最先进行来安排的。 3 剩下的只有那些其作业按照最小运行时间最先安排的调度是所有调度方案中最优的。 >多处理器的情况 1 我们将假设作业是有序的，最短的最先运行 2 解决多处理器情形的算法是按顺序开始作业，处理器之间轮换分配作业。 >将最后完成时间最小化 1 虽然这个调度没有最小平均完成时间，但是它有个优点，即整个序列的完成时间更早。 //Huffman编码 1 这种一般的策略就是对于不同字符让代码的长度是变化不等的，同时保证经常出现的字符其代码短。注意，如果所有的字符都以相同的频率出现，那么要节省空间是不可能的。 2 每个字符通过从根节点开始用0指示左分支用1指示右分支以记录路径的方法表示出来。这种数据结构有时叫作trie树。 3 只要没有字符代码是彼得字符代码的前缀即可。这样一种编码叫做前缀编码。 4 注意，存在许多最优的编码。 >Huffman算法 1 算法针对一个由树组成的森林。一棵树的权等于它的树叶的频率的和。任意选取有最小权的两棵树T1和T2，并任意形成以T1和T2为子树的新树，将这样的过程进行C-1次。在算法的开始，存在C颗单节点树——每个字符一颗。在算法结束时 得到一棵树，这棵树就是最优Huffman编码树。 2 我们将新的根命名为T1，这样可以确切无误地表述进一步的合并。 //近似装箱问题 >联机算法 >下项适合算法 1 当处理任何一件物品时，我们检查看它是否还能装进刚刚装进物品的同一个箱子中。如果能够装进去，那么就把它放入该箱中；否则，就开辟一个新的箱子。 >首次适合算法 1 依序扫描这些箱子但把新的一件物品放入足以盛下它的第一个箱子中。因此，只有当先前放置物品的箱子已经没有再容下当前物品余地的时候，我们才开辟一个新箱子。 2 首次适合算法保证其解最多包含最优装箱树的二倍。 >最佳适合算法 1 该算法不是把一件新物品放入所发现的第一个能够容纳它的箱子，而是放到所有箱子中能够容纳它的最满的箱子中。 >脱机算法 1 将各项排序，把最大的物品放在最先。 2 首次适合算法使用10M个而不是6M个箱子的坏情形在物品已排序的情况下不会再发生。 3 在实践中，首次适合递减算法的效果非常好。 # 分治算法 1 分治算法由两部分组成： 分：递归解决较小的问题(当然，基本情况除外) 治：然后，从子问题的解构建原问题的解。 2 传统上，在正文中至少含有两个递归调用的例程叫做分治算法，而正文中只含有一个递归调用的例程不是分治算法。我们一般坚持子问题是不相交的(即基本上不重叠) 3 给定平面上的N个点，我们将证明最近的一对点可以在O(NlogN)时间内找到。 //分治算法的运行时间 //最近点问题 1 有可能两个点处于相同的位置；在这种情形下这两个点就是最近的，它们的距离为0. 2 假设平面上这些点已经按照x的坐标排过序。 3 画一条想象的垂线，把点集分成两半。 4 设带中的点按照它们的y坐标排序。 //选择问题 1 选择问题要求我们找出含N个元素的表S中的第k个最小的元素。 2 为了得到一个线性算法，我们必须保证子问题只是原问题的一部分，而不仅仅只是比原问题少几个元素。 3 我们不是从随机元素的样本中找出中项，而是从中项的样本中找出中项。 4 五分化中项的中项 >降低比较的平均次数 1 分治算法还可以用来降低选择算法预计需要的比较次数 //一些运算问题的理论改进 1 该算法是将两个N位数相乘 # 动态规划 1 我们看到一个可以被数学上递归表示的问题也可以表示成一个递归算法 2 编译器常常不能正确对待递归算法，结果导致低效的算法。当我们怀疑很可能是这种情况时，我们必须再给编译器提供一些帮助，将递归算法重新写成非递归算法，让后者把那些子问题的答案系统地记录在一个表内。利用这种方法的 一种技巧叫做动态规划。 //用一个表代替递归 1 递归算法如此慢的原因在于算法模仿了递归。 //矩阵乘法的顺序安排 1 一般最好避免字幕l作为变量名 //最优二叉查找树 //所有点对最短路径 1 动态规划是强大的算法设计技巧，它给解提供一个起点。 2 因为反复求解子问题，所以重要的是将它们的解记录在一个表中而不是重新计算它们。 # 随机化算法 1 在算法期间，随机数至少有一次用于决策。该算法的运行时间不只依赖于特定的输入，而且依赖于所发生的随机数。 2 好的随机化算法没有不好的输入，而只有坏的随机数(相对于特定的输入) //随机数发生器 1 产生随机数的最简单的方法是线性同余发生器，它于1951年由Lehmer首先描述。数x1,x2,... ...的生成满足 x_(i+1)=Ax_i mod M 2 为了开始这个序列，必须给出x0的某个值。这个值叫做种子(seed)。如果x0=0，那么这个序列远不是随机的。如果M是素数，那么xi就绝不会是0 3 注意，在M-1=10个数以后，序列将重复。 4 Lehmer建议使用31位的素数M=2^31-1=2 147 483 647。对于这个素数，A=48271是推荐。 5 当调试一个使用随机数的程序的时候，大概最好是置x0=1，这使得总是出现相同的随机序列。当程序工作时，可以使用系统时钟，也可以要求用户输入一个值作为种子。 6 在本节的其余部分我们将使用随机代替伪随机 //跳跃表 1 跳跃表类似于散列表，它们都需要估计表中的元素个数(从而阶的个数可以确定)。 //素性测试 # 回溯算法 1 回溯算法的一个具体例子是在一套新房子内摆放家具的问题 2 在一步内删除一大组可能性的做法叫做裁剪(pruning) //收费公路重建问题 1 这就是为什么我们一定要将第一个点置于0处以及构建解的点集以非降顺序输出的原因 //博弈 >极大极小策略 1 使用一个赋值函数来给一个位置的“好坏”定值 2 如果一个位置不是终端位置，那么该位置的值通过递归地假设双方最优棋步而确定。这叫做极大极小策略。因为下棋的一方试图使这个位置的值极小化，而另一方却要使它的值极大。 3 在这种情况下，我们在达到递归的某个深度之后只能停止搜索。