我的第一本算法书

•图例

•蓝色：应用

•红色：重点

•紫色：时间复杂度

•

•绿色：代码

•加粗：名词解释/重点

・序章算法的基本知识

•算法和程序有些相似，区别在于程序是以计算机能够理解的编程语言编写而成的，可以在计算机上

运行；而算法是以人类能够理解的方式描述的，用于编写程序之前.

・运行时间的计算方法

・一般来说我们最为重视的是算法的运行时间，即从输入数据到输出结果这个过程所花费的时间。

・使用"步数”来描述运行时间。"1步"就是计算的基本单位。通过测试"计算从开始到结束

总共执行了多少步"来求得算法的运行时间。

・0这个符号的意思是"忽略重要项以外的内容"，读音同Order。

•选择排序的时间复杂度为0（11人2）、快速排序的时间复杂度为O（nlogn）。

•第1章数据结构

・1-1数据结构

•决定了数据的顺序和位置关系

•将数据存储于内存时，根据使用目的选择合适的数据结构，可以提高内存的利用率。

»数据在内存中是呈线性排列的，但是我们也可以使用指针等道具，构造出类似"树形"的复杂

结构

・1-2链表（线性排列）

・在链表中，数据的添加和删除都较为方便，就是访问比较耗费时间。

•在链表中，数据一般都是分散存储于内存中的，无须存储在连续空间内。

•因为数据都是分散存储的，所以如果想要访问数据，只能从第1个数据开始，顺着指针的指向

——往下访问（顺序访问）。

•虽然删除的数据本身还存储在内存中，但是不管从哪里都无法访问这个数据，所以也就没有特

意去删除它的必要了。今后需要用到被删数据所在的存储空间时，只要用新数据覆盖掉就可以

了。

・链表操作的时间复杂度

・杳找（线性查找）

0（n）

・添加/删除数据

0（1）

•循环链表，也叫'‘环形链表"

•没有头和尾的概念

•想要保存数量固定的最新数据时通常会使用这种链表。

•双向链表

•存在两个缺点

・指针数的增加会导致存储空间需求增加；

・添加和删除数据时需要改变更多指针的指向.

・1-3数组（线性排列）

・在数组中，访问数据十分简单，而添加和删除数据比较耗工夫。

・数据按顺序存储在内存的连续空间内。因此每个数据的内存地址（在内存上的位置）都可以通

过数组下标算出，可以借此直接访问目标数据（随机访问）。

・数组操作的时间复杂度

・查找（线性查找）

。⑴

•添加/删除数据

0（n）

・1-4栈Stack（线性排列）

・在栈中，添加和删除数据的操作只能在一端进行，访问数据也只能访问到顶端的数据。想要访

问中间的数据时，就必须通过出栈操作将目标数据移到栈顶才行。

•最后添加的数据最先被取出，即"后进先出”的结构，称为LastInFirstOut,简称LIFOo

•栈只能访问最新添加的数据。在只需要访问最新数据时，使用它比较方便。

•括号配对

•深度优先搜索算法，通常会选择最新的数据作为候补顶点。在候补顶点的管理上可以使用

栈。

・1-5队列Queue（线性排列）

•队列中添加和删除数据的操作分别是在两端进行的。

•队列也不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。

•最先进去的数据最先被取来，即"先进先出"的结构，我们称为FirstlnFirstOut,简称FIFO。

•"先来的数据先处理"是一种很常见的思路，所以队列的应用范围非常广泛。

•广度优先搜索算法，通常就会从搜索候补中选择最早的数据作为下一个顶点。在候补顶点

的管理上就可以使用队列。

・1-6哈希表

・哈希表存储的是由键（key）和值（value）组成的数据。

・在哈希表中，准备好数组，可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲

突，就使用链表进行存储。

・给数组设定合适的空间非常重要。

・如果数组的空间太小，容易发生冲突，线性查找的使用频率也会更高；

•如果数组的空间太大，会出现很多空位，造成内存的浪费。

・几种解决冲突的方法

•链地址法

在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决

冲突。

•开放地址法

当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有

冲突，便继续计算下一个候补地址，直到有空地址为止。

•计算候补地址

•多次使用哈希函数

•线性探测法

•在把哈希表应用于密码等安全方面时需要留意的条件：无法根据哈希值推算出原值

•哈希表在数据存储上的灵活性和数据查询上的高效性

・关联数组

一种具有特殊索引方式的数组。不仅可以通过整数来索引它，还可以使用字符串或者其他

类型的值（除了NULL）来索引它。它包含标量数据，可用索引值来单独选择这些数据，

和数组不同的是，关联数组的索引值不是非负的整数而是任意的标量。这些标量称为Keys,

可以在以后用于检索数组中的数值。关联数组的元素没有特定的顺序，可以把它们想象为

一组卡片。每张卡片上半部分是索引而下半部分是数值。

・1-7堆（图的树形结构）

•堆是一种图的树形结构，被用于实现“优先队列"（priorityqueues）

•优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按III页序取出。

・和队列的不同，队列是先进先出；堆虽然也是最顶部的先出，但是由于它插入数据的时候

有排序过，所以是最小的先出。

•堆中的每个结点最多有两个子结点。树的形状取决于数据的个数。

•结点的排列顺序为从上到下，同一行里则为从左到右。@opalli:填满一行再填下一行

・在堆中存储数据时必须遵守这样一条规则：子结点必定大于父结点。@opalli:只在纵向有大

小顺序，横向节点间没有大小关系。

•最小值被存储在顶端的根结点中。

•往堆中添加数据时，

•T殳会把新数据放在最下面一行靠左的位置。当最下面一行里没有多余空间时，就再往

下另起一行，把数据加在这一行的最左端。

•如果父结点大于子结点，交换父子结点的位置。

•从堆中取出数据时，

•取出的是最上面的数据。这样就能始终保持最上面的数据最小。

・最上面的数据被取出，堆的结构也需要重新调整。

•将最后的数据移动到最顶端。@opalli:为了保持堆是平衡的，塞满一行再塞下一

行的属性。同时注意最后的数据是最后一行最右边的数据，而不是（倒数第二行）

最右边的数据！如果用数组来存储堆，那就是最后一个数据。

・如果子结点的数字小于父结点的，就将父结点与其左右两个子结点中较小的一个进

行交换。@opalli:和较小的那个交换，和较大的交换，则换上去的那个是比另一

个大的！

・堆操作的时间复杂度

•取出最小值

。⑴

・重构树（删除）（树的高度为Iog2n）

O（logn）

・添加数据（与树的高度成正比）

O（logn）

•如果需要频繁地从管理的数据中取出最小值，那么使用堆来操作会非常方便。

•狄克斯特拉算法，每一步都需要从候补顶点中选择距离起点最近的那个顶点。在顶点的选

择上就可以用堆。

・1-8二叉查找树/二叉搜索树/二叉排序树(图的树形结构)

•二叉查找树的两个性质@opalli:纵横方向皆有大小关系

二叉查找树的最小结点要从顶端开始，往其左下的末端寻找；二叉查找树的最大结点要从顶端

开始，往其右下的末端寻找。

・每个结点的值均大于其左子树上任意一个结点的值。

・每个结点的值均小于其右子树上任意一个结点的值。

・往二叉杳找树中删除数据

・如果需要删除的结点没有子结点，直接删掉该结点即可。

・如果需要删除的结点只有一个子结点，那么先删掉目标结点，然后把子结点移到被删除结

点的位置上即可。

・如果需要删除的结点有两个子结点，那么先删掉目标结点，然后在被删除结点的左子树中

寻找最大结点，最后将最大结点移到被删除结点的位置上。如果需要移动的结点也还有子

结点，就递归执行前面的操作。@opalli:需要移动的节点是左子树中最大的结点，所以它

只可能有左子树，将它移上去以后，直接用左子树的结点来填充即可。

・删除的时候，将"左子树中的最大结点"移动到了删除结点的位置上，但是根据二叉查找

树的性质可知，移动"右子树中的最小结点”也没有问题。

•二叉查找树是二分查找算法思想的树形结构体现

•二叉查找树操作的时间复杂度

•查找数据/寻找适合添加数据的位置(取决于树的高度)

•树的形状较为均衡

O(logn)

•树的形状朝单侧纵向延伸

0(n)

・@opalli:这里和堆也不一样，因为堆的数据是塞满一行才会塞下面一行，所以时间复

杂度是O(logn),而不会有不平衡达到0(n)的情况。

•平衡二叉查找树AVLTree

・平衡二叉树(AVL树)在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最

大差为lo

•a,b是AVL树，c,d不是

，no■>・IIBF3nwiv6aw

TN»t«avalidAVLtrMsnceforwchnod*mthe

treetheh*ghtofth・andnjhtsubtreesdffm

tr««mheightoftrwleftsndrightsubtrew

t>ya<most1(NoticethatforeachNULL60d.Vw

WmoM1.

height<rfthatcfiWssutxr««is-1.)

•1.1.1.1TT&®

•1.1>1・1

(a)(b)

ThrttreeeNOTavakdAVttreesincemeheightTh«tree«NOTavahdAVLVMuncatheh*9M

ofMnodm«ub(reMdonotd<rr«fbyatmost1ofaKnodessubtreesdonddifferbyalnx»t1.

Speo®C8«y.therootsleftindrtgNsubtfees'Bothnode20andnode5violMethisproperty

heightsdifferby2.

//

■<

©O

•1.1・1«1

（d）

・失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右

左）.

Lx^s^入（

-士

IM-，UW-IB4T

・AVL树通过"旋转操作（rotations）来保持树的平衡。这种数据结构可以修正形状不均衡

的树，让其始终保持均衡形态，1•烦高查找效率。

・LL的旋转：LL失去平衡的情况下可以通过一次旋转让AVL树恢复平衡。步骤如下：

——插入6r—-1右单旋转__

10匕_[_2

1

□

•将根节点的左孩子作为新根节点。

•将新根节点的右孩不乍为原根节点的左孩子。

•将原根节点作为新根节点的右孩子。

•RR的旋转：RR失去平衡的情况下，旋转方法与LL旋转对称，步骤如下：

•将根节点的右孩布乍为新根节点。

•将新根节点的左孩子作为原根节点的右孩子。

・将原根节点作为新根节点的左孩子。

・LR的旋转：LR失去平衡的情况下，需要进行两次旋转，步骤如下：

•围绕根节点的左孩子进行RR旋转。

・围绕根节点进行LL旋转。

・RL的旋转：RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转对称，步

骤如下：

・围绕根节点的右孩子进行LL旋转。

・围绕根节点进行RR旋转。

•B树

•把二叉查找树的子结点数扩展为m（m为预先设定好的常数）。像这种子结点数可以自由

设定，并且形状均衡的树便是B树。

•其他自平衡BST:红黑树(Red-BlackTree)、2-3树、2-3-4树、伸展树(SplayTree)、

B树

•第2章排序

・2-1什么是排序

排序算法平均时间复勘发最好情K最坏情况.空间要杀发排序方式.稳定＜1

胃泡排序。(向O(n)0(向0(1)In-place稳定

选挣排序0(向0M2)o(e0(1)In-place不稳定

插入排序O2)0(n)。(向0(1)In-place稳定

韦尔排寿O(nlogn)0(nlog2n)O(nlog2n)0(1)In-place不稳定

归并排寿0(nlogn)0(nlogn)O(nlogn)O(n)Out-place稳定

快速排方0(nlogn)0(nlogn)。(向O(logn)In-place不赛定

培排序0(nlogn)O(nlogn)O(nlogn)0(1)In-place不栽定

计数排寿0(n+k)0(n+k)0(n+k)O(h)Out-place稳定

精加声O(n+k)0(n+k)0(n2)O(n+k)Out-place想定

皋敕排方0(nxk)0(nxk)0(nxk)0(n+k)Out—place稳定

・2-2冒泡排序

•从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置，重复同样的操作

直到序列中最小的数字移动到最左边。然后重复之前的操作，将第二小的数字移动到左二……继

续重复知道所有数字都排完序。

.冒泡排序的时间复杂度

0(nA2)

・比较

0(nA2)(和数据排列顺序无关，恒定。)

•交换

(和输入数据的排列顺序有关。)如输入数据正好以从小到大的顺序排列，便不需要任何

交换操作；输入数据以从大到小的II质序排列，每次比较都要交换。

・2-3选择排序

・从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换。重复同样的操作直到所有

数字都归位为止。

・冒泡排序的时间复杂度

0(nA2)

・比较

0(nA2)

•交换

每轮中交换数字的次数最多为1次。

・2-4插入排序

・插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续

归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出

一个数据,然后将它插入到已排序区域内合适的位置上。

・插入排序的时间复杂度

0(nA2)

•输入数据按从大到小的顺序排列时就是最糟糕的情况。

・2-5堆排序

・堆排序的特点是利用了数据结构中的堆。首先，在堆中存储所有的数据，并按降序来构建堆。

从降序排列的堆中取出数据时会从最大的数据开始取，所以将取出的数据反序输出，排序就完

成了。

•@opalli:既然要反序输出，为神马不T始就用升序堆呢？

・堆排序的时间复杂度

O(nlogn)

•将数据存进堆里

O(nlogn)(插入1个数据所需要的时间为O(logn)。)

・重构排序整体来看堆排序的时间复杂度为

O(nlogn)(每轮取出最大的数据并重构堆所需时间为O(logn)o)

・堆排序的运行时间比冒泡排序、选择排序、插入排序的时间0(n^2)都要短，但由于要使

用堆这个相对复杂的数据结构，所以实现起来也较为困难。

•T殳来说，需要排序的数据都存储在数组中。实际上，这也相当于将堆嵌入到包含了序

列的数组中，然后在数组中通过交换数据来进行排序。可以说是强行在数组中使用了堆

结构。

•@opalli:数据结构，归根到底只有两种，链表和数组，其余的结构都是基于这两种最

基本的来构建和存储的.

•树

・用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指

针，操作也比较简单；

•假如A、B.C…节点对应数组的索引位置0、1、2,那么如果一个节点的索引

位置如果是i,那么它的左子节点的索引位置为2*i+l,右子节点的索引位置

为2*i+2,父节点的索弓I位置为ceil[(i-1)/2],ceil表示向下取整。

@opalli:只有堆可以这样计算，因为堆的数据是插满的。

・用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数

组存储。

・在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、

AVL树、红黑树、区间树、B树等等，以应对不同的问题。

・在一棵树中，边的数量比节点的数量少1.如果一棵树有N个节点，则这棵树有

N-1条边。LeetCode【684】冗余连接题中的图在树的基础上多了一条附加的边,

因此边的数量也是N。树是一个连通且无环的无向图，在树中多了一条附加的边之

后就会出现环。

・2-6归并排序

•归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时(也就是每个子序列

中只有一个数据时)，就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有

序序列。

.归并排序的时间复杂度

O(nlogn)

・分割

不算在运行时间内（可以当作序列本来就是分割好的）。

•归并

O（nlogn）（每行花费和两个子序列的长度相应的运行时间，有Iog2n行。）

・2-7快速排序

•快速排序算法首先会在序列中随机选择一个基准值（pivot）,然后将除了基准值以外的数分为

"比基准值小的数"和"比基准值大的数"这两个类别，再将其排列成以下形式。

•[比基准值小的数]基准值[比基准值大的数]

•接着，对两个"[]"中的数据进行排序之后，整体的排序便完成了。对"[]"里面的数据进行

排序时同样也会使用快速排序，直到子问题里只剩一个数字为止。

•快速排序是一种“分治法"。它将原本的问题分成两个子问题（比基准值小的数和比基准值大

的数），然后再分别解决这两个问题。

•分治和递归是不是总是结伴出现呢？

•汉诺塔

•快速排序的时间复杂度

•如果每次选择的基准值都能使得两个子序列的长度为原本的一半

O（nlogn）

•如果每次都选择最小值作为基准值

0（nA2）

•如果数据中的每个数字被选为基准值的概率都相等，则平均运行时间

O（nlogn）

•实现参考

hups:〃www.sohu.eom/a/246785807684445

・同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序

的目的。

・比冒泡排序快的地方：冒泡的轮数会比较多。冒泡排序在每一轮只把一个元素冒泡到数列

的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，

比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

・@算法图解：

・在大0表示法0（。）中,“实际上指的是这样的。

c次h

国定的

时间量

•C是算法所需的固定时间量，被称为常量。

・通常不考虑这个常量，因为如果两种算法的大0运行时间不同，这种常量将无关紧要。

•但当使用大O表示法表示时两个算法的速度相同，常量的影响可能很大，实际上会有速度

的区别。这就是快速排序比合用E序快的原因所在.@opalli:为撒固定时间量不一样？快

排交换次数少？

・平均情况下(随机地选择一个数组元素作为基准值)快速排序比合并排序快。

•快速排序在最糟情况下,栈长为0(/7),算法的运行时间为0(〃八2);而在最佳情况下，

栈长为O(log/7),整个算法需要的时间为0(/7logn)0

•合并排序的运行时间总是O(〃log〃)。

•第3章数组的查找

.3-1线性查找

・线性查找的时间复杂度

0(n)

・3-2二分查找

・二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是

右边.因此，比较一次就可以把查找范围缩小一半。重复执行该操作就可以找到目标数据，或

得出目标数据不存在的结论。

•二分查找只能查找已经排好序的数据。

•二分查找的时间复杂度

O(logn)

•二分查找必须建立在数据已经排好序的基础上才能使用，因此添加数据时必须加到合适的

位置，这就需要额外耗费维护数组的时间。

•第4章图的搜索

•4-1什么是图

•计算机科学或离散数学中说的"图"

・顶点/结点

•边

•图

由顶点和连接每对顶点的边所构成的图形

・图可以表现各种关系

•社会中的各种关系

•地铁的路线

•网络的连接关系

・加权图

・可以给边加上一个值，这个值叫作边的"权重"或者"权"，加了权的图被称为"加权

图"。

•没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的“连接程

度"。

•计算最短路径时，边的权重代表的通常都是时间、距离或者路费等，因此基本都是非负数。

•在一些情况下顶点也可以有权重。

•有向图

»给边加上箭头，而这样的图就叫作"有向图"。

•边上没有箭头的图便是“无向图"。

•使用有向图还可以设置非对称的权重。

・无向图意味着两个节点彼此指向对方，其实就是环！在无向图中，每条边都是一个环。

・图的基本问题——最短路径问题

・最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重

总和最小的那条路径。

•解决办法：图的最短路径问题算法（4-4、4-5、4-6）

•算法的应用场景

•寻找计算机网络中通信时间最短的路径

•寻找路线图中耗时最短的路径

・寻找路线图中最省乘车费的路径

・图的搜索（4-2、4-3）

・图的搜索指的就是从图的某一顶点开始，通过边到达不同的顶点，最终找到目标顶点的过

程。

•根据搜索的顺序不同，图的搜索算法可分为

•广度优先搜索

・深度优先搜索

•@opalli:但是图的搜索算法和最短路径问题算法并不完全一样，图的搜索有T目标,

但目标不一直是最短路径？

•BFS相对DFS的最主要的区别是：BFS找到的路径一定是最短的，但代价就是空间复

杂度比DFS大很多。

・BFS借助队列做到一次一步“齐头并进"，即BFS的depth每增加一次，队列中

的所有节点都向前迈一步，保证了第一次到达终点的时候，走的步数是最少的，可

以在不遍历完整棵树的条件下找到最短距离的。

•DFS其实也可以找最短路径，但是时间复杂度相对高很多。DFS实际上是靠递归的

堆栈记录走过的路径，要找到最短路径，得把二叉树中所有树杈都探索完才能对比

出最短的路径有多长。

・形象点说，DFS是线，BFS是面；DFS是单打独斗，BFS是集体行动。

•BFS可以找到最短距离，但空间复杂度高；而DFS的空间复杂度较低。节点数为

N的满二叉树

:空间复杂度就是递归堆栈，最坏情况下是树的高度，也就是（）

・DFSOlogNo

・BFS:队列中每次都会储存着二叉树一层的节点，最坏情况下空间复杂度是树

的最底层节点的数量，也就是N/2，用Big。表示的话也就是0（N）。

・BFS还是有代价的，一般来说在找最短路径的时候使用BFS,其他时候还是DFS

使用得多一些（递归代码好写）。

•图的搜索的应用

・遍历（DFS）

•找出（非加权图的）最短路径（BFS）

・4-2广度优先搜索BFS

・广度优先搜索会优先从离起点近的顶点开始搜索。因此，目标顶点离起点越近，搜索结束得就

越快。

•@opalli:所以广度优先搜索可以用来寻找（非加权图的）最短路径

・候补顶点是用"先入先出"（FIFO）的方式来管理的，因此可以使用"队列"这个数据结构.

•@opalli:同一层（深度）的顶点，或者说距离起点相同远近的顶点，是同时成为候补顶点的。

•@opalli:搜索某个顶点，就是判断其是不是目标节点，不是的话，将其子结点添加到候补顶

点队列中。

•如果图中有闭环，其搜索步骤也是一样的。@opalli:不限于树状图，只要起点确定了，就可

以有远近的区分。

・没有闭环的图叫作"树"。

•@算法图解：广度优先搜索的运行时间为O(V+E),其中V为顶点(vertice)数，E为边数。

・4-3深度优先搜索DFS

・深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一

条候补路径。@opalli:广度优先搜索没有折返。

•候补顶点是用"后入先出"(LIFO)的方式来管理的，因此可以使用"栈"这个数据结构。

•虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，但是在操作步骤上却只有一点

不同，那就是选择哪一个候补顶点作为下一个顶点的基准不同。

・广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以

会从离起点近的地方开始按顺序搜索；@opalli:近即深度小。

・而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不

断深入搜索。

・@opalli:进行过”是否目标判断，且子节点加入了候选”的节点(对应在算法中，就是pop

过的node),被认为是搜索过的节点,不会再入队/栈。

・@opalli:BFS&DFS总结

・广度优先搜索BFS

1/••

2*Returnthelengthoftheshortestpathbetweenrootandtargetnode.

3*/

4intBFS(Noderoot,Nodetarget){

Queue<Node>queue;//storeallnodeswhicharewaitingtobeprocessed

Set<Node>used;//storealltheusednodes

intstep=0;//numberofstepsneeededfromroottocurrentnode

8//initialize

addroottoqueue;

addroottoused;

11//BFS

12while(queueisnotempty){

13step=step+1;

14//iteratethenodeswhicharealreadyinthequeue

intsize=queue.size())

16for(inti=0;i<size;++i){

17Nodecur=thefirstnodeinqueue)

returnstepifcuristarget;

for(Nodenext:theneighborsofcur){

if(nextisnotinused){

addnexttoqueue;

addnexttoused;

23}

24}

removethefirstnodefromqueue)

26)

)

28return-11//thereisnopathfromroottotarget

29)

•深度优先搜索DFS

・递归

1/♦

2*Returntruei£thereisapathfromcurtotarget.

3*/

4booleanDFS(Nodecur.Nodetarget,Set<Node>visited){

returntruei£curistarget;

for(next：eachneighboro£cur){

i£(nextisnotinvisited){

addnexttovisted;

returntruei£DFS(next,target,visited)=true：

}

11}

12returnfalse;

13}

•迭代(使用Stack,和BFS的模板几乎一样，只是将Queue改成Stack)

1/♦

2*Returntruei£thereisapathfromcurtotarget.

3*/

4booleanDFS(introot,inttarget){

Set<Node>visited;

Staclc<Node>s;

addroottos;

while(sisnotempty){

Nodecur=thetopelementins;

returntruei£curistarget;

for(Nodenext：theneighborso£cur){

i£(nextisnotinvisited){

addnexttos;

addnexttovisited;

15}

)

removecurfroms;

18}

19returnfalse;

20}

•递归解决方案的优点是它更容易实现。但存在一个很大的缺点：如果递归的深度太高，

将遭受堆栈溢出。

•回溯

.4-4贝尔曼-福特(Bellman-Ford)算法

•贝尔曼-福特算法是一种在图中求解最短路径问题的算法。

・贝尔曼-福特算法的执行步骤

•首先设置各个顶点的初始权重：起点为0,其他顶点为无穷大(8)。这个权重表示的是从

A到该顶点的最短路径的暂定距离。随着计算往下进行，这个值会变得越来越小，最终收

敛到正确的数值。

・计算这条边从一端到另一端的权重

•计算方法是"顶点原本的权重+边的权重"。

•只要按顺序分别计算两个方向的权重即可，从哪一端开始都没有问题。选择按顶点权重

从小到大的方向开始计算。

・如果计算结果小于顶点的值，就更新这个值。（从权重较大的顶点到较小的顶点时，只

要边的权重不为负，就不会更新权重。）

•更新时需要记录计算的是从哪个顶点到该顶点的路径。

•对所有的边都执行同样的操作。在执行顺序上没有特定要求。

・更新完所有的边后，第1轮更新就结束了。

•接着，重复对所有边的更新操作，直到权重不能被更新为止。

・算法的搜索流程结束，找到了从起点到其余各个顶点的最短路径。

・选出一条边并计算顶点的权重时，无向图中的计算两个方向都要计算；在有向图中只按照

边所指向的那个方向来计算就可以了。

・即便权重为负，贝尔曼-福特算法也可以正常运行。

•贝尔曼-福特算法的时间复杂度

O（nm）

・将图的顶点数设为n、边数设为m,该算法经过n轮更新操作后就会停止。

•@opalli:为什么？因为每轮至少更新一个顶点？最多更新n轮？但是一个顶点可以被更新

多次吧？

•最后确定下来的最短路径中,必然会有点是从起点开始的第一个顶点，该顶点在第一轮

中就会被更新成正确的值；而在第二轮结束后，最短路径中的第二步的顶点也必然会被

更新成正确的最小值（也可能是在第一轮中就被更新对了）；……；n轮后可以遍历所

有的点，路径必然生成,所以路径的长度必然小于n,且为最短路径。

•或者可以说，从起点到每个顶点都会有一条最短路径，这条路径的长度不会超过n个

点，每一步至少能更新成功一个点。

•如果在一个闭环中边的权重总和是负数，那么只要不断遍历这个闭环，路径的权重就能

不断减小，根本不存在最短路径。遇到这种对顶点进行n次更新操作后仍能继续更新

的情况，就可以直接认定它“不存在最短路径”。

・动态规划是贝尔曼-福特算法的一个分类

・4-5狄克斯特拉（Dijkstra）算法

•狄克斯特拉算法也是求解最短路径问题的算法，从离起点近的顶点开始，按顺序求出起点到各

个顶点的最短路径。

・@opalli:如果需要求出起点到各个顶点的最短路径，那需要算n轮；如果只需要计算到目

标顶点的最短路径，则计算到目标顶点后，就可以停止计算了（会有顶点没有算出最短路

径）；而贝尔曼-福特算法不能中途停止，必须算到不再有更新了（当然，最多也就是n

轮）。

・假设起点到达目标顶点X的最短路径中，X的深度是d的话，则只求目标顶点X的最

短路径的话：

・狄克斯特拉算法更新到第d轮即可结束；

・而贝尔曼-福特算法则可能需要到第n轮才会结束（即使从第d轮以后，目标顶点

X的路径值不会再更新了，但是其余顶点还在被更新，所以不确定算法是否可以停

止）

・狄克斯特拉算法的执行步骤

•从起点出发寻找可以从目前所在的顶点直达且尚未被搜索过的顶点，将它们设为下一步的

候补顶点。@opalli:是尚未被搜索过（没有成为过权重最小的点，其可直达的点也没有成

为候补顶点），而不是尚未被经过或计算过或更新过。

•计算各个候补顶点的权重。

•计算方法是“目前所在顶点的权重+目前所在顶点到候补顶点的权重"。

・如果计算结果小于候补顶点的值，就更新这个值。

•从候补顶点中选出权重最小的顶点，如果两个候I卜顶点权重相等，选择哪一个都可以

（@opalli:因为另一个马上就被搜索了，两个顶点的直达顶点最终会有一个被选中）。即

确定了从起点到该顶点的最短路径,移动到该顶点，并将可以从该顶点直达的顶点设为新

的候补顶点。

・@opalli:到某顶点的最短路径是通过逐步从候补顶点中选择权重最小的顶点来得到的,

其余所有未被搜索过的顶点的权重都大于此顶点，所以如果经过其他（未被搜索的）顶

点到达此处，最终其权重必定会大于这条路径。

•狄克斯特拉算法一边逐一确定起点到各个顶点的最短路径，一边对图进行搜索。

・重复执行同样的操作直到达终点为止。@opalli:此时并不一定已经遍历了所有的结点。

•比起需要对所有的边都重复计算权重和更新权重的贝尔曼-福特算法，狄克斯特拉算法多了一步

选择顶点的操作，这使得它在求最短路径上更为高效。

•如果图中含有负数权重，狄克斯特拉算法可能会无法得出正确答案。

•@opalli:有负数权重时，即使某个顶点成为了当时权重最小的节点，经过其他（未被搜

索的、权重更大的）顶点到达此顶点时，其权重仍可能更小。

・闭环中有负数权重，在狄克斯特拉算法中，即便不存在最短路径，它也会算出一个错误的

最短路径出来。

•不存在负数权重时，更适合使用效率较高的狄克斯特拉算法；而存在负数权重时，即便较为耗

时，也应该使用可以得到正确答案的贝尔曼-福特算法。

・狄克斯特拉算法的时间复杂度

・（将图的顶点数设为n、边数设为m）

•不进行任］可处理

0(nA2)

・@opalli:每一个顶点至少要和一个顶点相连，所以边数m不会小于顶点数n,狄克斯

特拉算法的时间复杂度不会高于贝尔曼-福特算法的O(mn)。

•对数据结构进行优化

0(m+nlogn)

•@opalli:数据结构优化是怎么优化的？时间复杂度是如何算出来的？

•@opalli:Why?n个点逐次成为候选点，每个点最多被更新n-l次？

•@算法图解

・计算非加权图中的最短路径，可使用广度优先搜索。要计算加权图中的最短路径，可使

用狄克斯特拉算法。

•狄克斯特拉算法只适用于有向无环图(directedacyclicgraph,DAG)。环增加了权

重。如果愿意甚至可绕环两次。

•@opalli:觉得有环图也是可以用啊？因为狄克斯特拉算法会忽略走过的节点，就

不会走回原来的节点，即不会形成环(可以说有环图狄克斯特拉算法也是当做无环

图来算的),所以有环也可以找到最短路径呀(而且绕环也不可能是最短路径)