php家谱逻辑技巧_一文带你熟习30个重要的数据结构和算法

数组是最大略也是最常见的数据构造。
它们的特点是可以通过索引（位置）轻松访问元素。

它们是做什么用的？

想象一下有一排剧院椅。
每把椅子都分配了一个位置（从左到右），因此每个不雅观众都会从他将要坐的椅子上分配一个号码。
这是一个数组。
将问题扩展到全体剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。

特性

链表是线性数据构造，就像数组一样。
链表和数组的紧张差异在于链表的元素不存储在连续的内存位置。
它由节点组成——实体存储当前元素的值和下一个元素的地址引用。
这样，元素通过指针链接。

它们是做什么用的？

链表的一个干系运用是浏览器的上一页和下一页的实现。
双链表是存储用户搜索显示的页面的完美数据构造。

特性

堆栈是一种抽象数据类型，它形式化了受限访问凑集的观点。
该限定遵照 LIFO（后进先出）规则。
因此，添加到堆栈中的末了一个元素是您从中删除的第一个元素。

堆栈可以利用数组或链表来实现。

它们是做什么用的？

现实生活中最常见的例子是在食堂中将盘子叠放在一起。
位于顶部的板首先被移除。
放置在最底部的盘子是在堆栈中保留韶光最长的盘子。

堆栈最有用的一种情形是您须要获取给定元素的相反顺序。
只需将它们全部推入堆栈，然后弹出它们。

另一个有趣的运用是有效括号问题。
给定一串括号，您可以利用堆栈检讨它们是否匹配。

特性

行列步队是受限访问凑集中的另一种数据类型，就像前面谈论的堆栈一样。
紧张差异在于行列步队是按照FIFO（前辈先出）模型组织的：行列步队中第一个插入的元素是第一个被移除的元素。
行列步队可以利用固定长度的数组、循环数组或链表来实现。

它们是做什么用的？

这种抽象数据类型 (ADT) 的最佳用场当然是仿照现实生活中的行列步队。
例如，在呼叫中央运用程序中，行列步队用于保存等待从顾问那里得到帮助的客户——这些客户该当按照他们呼叫的顺序得到帮助。

一种分外且非常主要的行列步队类型是优先级行列步队。
元素根据与它们关联的“优先级”被引入行列步队：具有最高优先级的元素首先被引入行列步队。
这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。
它是利用堆实现的。

另一种分外类型的行列步队是deque 行列步队（双关语它的发音是“deck”）。
可以从行列步队的两端插入/删除元素。

特性

Maps （dictionaries）是包含键凑集和值凑集的抽象数据类型。
每个键都有一个与之关联的值。

哈希表是一种分外类型的映射。
它利用散列函数天生一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。

最常见的散列函数（在浩瀚散列函数中）是模常数函数。
例如，如果常量是 6，则键 x 的值是x%6。

空想情形下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采取了不完善的函数，这可能会导致具有相同天生值的键之间发生冲突。
这种碰撞总是以某种办法适应的。

它们是做什么用的？

Maps 最著名的运用是措辞词典。
措辞中的每个词都为其指定了定义。
它是利用有序映射实现的（其键按字母顺序排列）。

通讯录也是一张Map。
每个名字都有一个分配给它的电话号码。

另一个有用的运用是值的标准化。
假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。
哈希函数将为h(x) = x.小时60+x.分钟。

特性

术语：

由于maps 是利用自平衡红黑树实现的（文章后面会阐明），以是所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。

图是表示一对两个凑集的非线性数据构造：G={V, E}，个中 V 是顶点（节点）的凑集，而 E 是边（箭头）的凑集。
节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与本钱/间隔干系联）的线。

图有两种紧张类型：有向图和无向图。
在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。
在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。

它们是做什么用的？

图是各种类型网络的根本：社交网络（如 weixin、csdn、weibo），乃至是城市街道网络。
社交媒体平台的每个用户都是一个包含他/她的所有个人数据的构造——它代表网络的一个节点。
weixin 上的好友关系是无向图中的边（由于它是互惠的），而在 CSDN 或 weibo上，帐户与其关注者/关注帐户之间的关系是有向图中的箭头（非互惠）。

特性

图论是一个广阔的领域，但我们将重点先容一些最有名的观点：

一棵树是一个无向图，在连通性方面最小（如果我们肃清一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。
以是任何无环连通无向图都是一棵树，但为了大略起见，我们将有根树称为树。

根是一个固定节点，它确定树中边的方向，以是这便是统统“开始”的地方。
叶子是树的终端节点——这便是统统“结束”的地方。

一个顶点的孩子是它下面的事宜顶点。
一个顶点可以有多个子节点。
一个顶点的父节点是它上面的事宜顶点——它是唯一的。

它们是做什么用的？

我们在任何必要描述层次构造的时候都利用树。
我们自己的家谱树便是一个完美的例子。
你最古老的先人是树的根。
最年轻的一代代表叶子的凑集。

树也可以代表你事情的公司中的高下级关系。
这样您就可以找出谁是您的上级以及您该当管理谁。

特性

二叉树是一种分外类型的树：每个顶点最多可以有两个子节点。
在严格二叉树中，除了叶子之外，每个节点都有两个孩子。
具有 n 层的完全二叉树具有所有2ⁿ-1 个可能的节点。

二叉搜索树是一棵二叉树，个中节点的值属于一个完备有序的凑集——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

它们是做什么用的？

BT 的一项主要运用是逻辑表达式的表示和评估。
每个表达式都可以分解为变量/常量和运算符。
这种表达式书写方法称为逆波兰表示法 (RPN)。
这样，它们就可以形成一个二叉树，个中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。

BST 常常利用，由于它们可以快速搜索键属性。
AVL 树、红黑树、有序集和映射是利用 BST 实现的。

特性

BST 有三种类型的 DFS 遍历：

所有这些类型的树都是自平衡二叉搜索树。
不同之处在于它们以对数韶光平衡高度的办法。

AVL 树在每次插入/删除后都是自平衡的，由于节点的左子树和右子树的高度之间的模块差异最大为 1。
AVL 以其发明者的名字命名：Adelson-Velsky 和 ​Landis。

在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。

在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销韶光繁芜度仍旧是 O(log n)。

它们是做什么用的？

AVL 彷佛是数据库理论中最好的数据构造。

RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。
在 Java 8 版本中，HashMap 是利用 RBT 实现的。
打算几何和函数式编程中的数据构造也是用 RBT 构建的。

在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾网络器、数据压缩、绳索（更换用于长文本字符串的字符串）。

特性

最小堆是一棵二叉树，个中每个节点的值都大于或即是其父节点的值：val[par[x]] <= val[x]，具有堆的 xa 节点，个中val[ x]是它的值，par[x] 是它的父级。

还有一个实现相反关系的最大堆。

二叉堆是一棵完全的二叉树（它的所有层都被添补，除了末了一层）。

它们是做什么用的？

正如我们几天前谈论过的，优先行列步队可以利用二叉堆有效地实现，由于它支持 O(log n) 韶光内的 insert()、delete()、extractMax() 和 reduceKey() 操作。
这样，堆在图算法中也是必不可少的（由于优先级行列步队）。

任何时候您须要快速访问最大/最小项目，堆都是最好的选择。

堆也是堆排序算法的根本。

特性

trie 是一种高效的信息检索数据构造。
也称为前缀树，它是一种搜索树，许可以 O(L) 韶光繁芜度插入和搜索，个中 L 是键的长度。

如果我们将密钥存储在一个平衡良好的 BST 中，它将须要与 L log n 成正比的韶光，个中 n 是树中的密钥数量。
这样，与 BST 比较，trie 是一种更快的数据构造（利用 O(L)），但代价是 trie 存储哀求。

它们是做什么用的？

树紧张用于存储字符串及其值。
它最酷的运用程序之一是在 Google 搜索栏中键入自动完成和自动建议。
特里是最好的选择，由于它是最快的选择：如果我们不该用特里，更快的搜索比节省的存储更有代价。

通过在字典中查找单词或在同一文本中查找该单词的其他实例，也可以利用 trie 来完成键入单词的正字法自动更正。

特性

空间繁芜度实际上是一个缺陷：O(ALPHABET_SIZELn)。

段树是一个完全的二叉树，可以有效地回答查询，同时仍旧可以轻松修正其元素。

给天命组中索引 i 上的每个元素代表一个用[i, i]间隔标记的叶子。
将其子节点分别标记为[x, y]或[y, z]的节点将具有[x, z]区间作为标签。
因此，给定 n 个元素（0-indexed），线段树的根将被标记为[0, n-1]。

它们是做什么用的？

它们在可以利用分而治之（我们将要谈论的第一个算法观点）办理的任务中非常有用，并且还可能须要更新其元素。
这样，在更新元素时​​，包含它的任何区间也会被修正，因此繁芜度是对数的。
例如，n 个给定元素的总和/最大值/最小值是线段树最常见的运用。
如果元素更新正在发生，二分搜索也可以利用段树。

特性

fenwick 树，也称为二叉索引树 (BIT)，是一种也用于高效更新和查询的数据构造。
与 Segment Trees 比较，BITs 须要更少的空间并且更随意马虎实现。

它们是做什么用的？

BIT 用于打算前缀和——第 i 个位置的元素的前缀和是从第一个位置到第 i 个元素的总和。
它们利用数组表示，个中每个索引都以二进制系统表示。
例如，索引 10 相称于十进制系统中的索引 2。

特性

6 = 12²+12¹+02⁰ => 1"1"0 (flip) => 100 = 12²+02¹+02⁰ = 4;复制代码末了，ANDing 元素，每个节点都该当包含一个可以添加到前缀和的间隔；更新的韶光繁芜度仍旧是 O(log n)，查询的韶光繁芜度仍旧是 O(1)，但空间繁芜度与线段树的 O(4n) 比较是一个更大的上风：O(n)。
14. 并查集（Disjoint Set Union）

我们有 n 个元素，每个元素代表一个单独的凑集。
并查集 (DSU) 许可我们做两个操作：

1.UNION — 组合任意两个凑集（或者统一两个不同元素的凑集，如果它们不是来自同一个凑集）； 2.FIND — 查找元向来自的凑集。

它们是做什么用的？

并查集（DSU） 在图论中非常主要。
您可以检讨两个顶点是否来自同一个连接组件，或者乃至可以统一两个连接组件。

让我们以城市和城镇为例。
由于人口和经济增长的临近城市正在扩展，它们可以轻松创建大都邑。
因此，两个城市合并在一起，他们的居民住在同一个大都邑。
我们还可以通过调用 FIND 函数来检讨一个人居住在哪个城市。

特性

给定一个连通图和无向图，该图的天生树是一个子图，它是一棵树并将所有节点连接在一起。
单个图可以有许多不同的天生树。
加权、连通和无向图的最小天生树 (MST) 是权重（本钱）小于或即是其他所有天生树权重的天生树。
天生树的权重是授予天生树每条边的权重之和。

它们是做什么用的？

最小天生树（MST ）问题是一个优化问题，一个最小本钱问题。
有了路线网，我们可以认为影响n个城市之间建立国道的成分之一是相邻两个城市之间的最小间隔。

国家路线便是这样，由道路网络图的 MST 表示。

特性

作为一棵树，具有 n 个顶点的图的 MST 具有 n-1 条边；可以利用以下方法办理：

分而治之（DAC）本身并不是一个特定的算法，而是在深入研究其他主题之前须要理解的主要算法种别。
它用于办理可以划分为与原始问题相似但规模较小的子问题的问题。
然后 DAC 递归地求解它们，末了合并结果以找到问题的办理方案。

它分为三个阶段：

它是干什么用的？

分治算法（DAC） 的一种实际运用是利用多个处理器进行并行编程，因此子问题在不同的机器上实行。

DAC 是许多算法的根本，例如快速排序、合并排序、二分搜索或快速乘法算法。

特性

排序算法用于根据元素上的比较运算符重新排列给定元素（来自数组或列表）。
当我们提到一个排序数组时，我们常日会想到升序（比较运算符是“<”）。
排序有多种类型，具有不同的韶光和空间繁芜度。
个中一些是基于比较的，有些则不是。
以下是最盛行/最有效的排序方法：

冒泡排序是最大略的排序算法之一。
它基于相邻元素之间的重复交流（如果它们的顺序缺点）。
它是稳定的，它的韶光繁芜度是 O(n²) 并且它须要 O(1) 赞助空间。

计数排序不是基于比较的排序。
它基本上是利用每个元素的频率（一种散列），确定最小值和最大值，然后在它们之间迭代以根据其频率放置每个元素。
它在 O(n) 中完成，空间与数据范围成正比。
如果输入范围不明显大于元素数量，则它是有效的。

快速排序是分而治之的一个运用。
它基于选择一个元素作为枢轴（第一个、末了一个或中间值），然后交流元素以将枢轴放置在所有小于它的元素和所有大于它的元素之间。
它没有额外的空间和 O(nlog n) 韶光繁芜度——基于比较的方法的最佳繁芜度。

归并排序也是一个分而治之的运用程序。
它将数组分成两半，对每一半进行排序，然后合并它们。
它的韶光繁芜度也是 O(nlog n)，以是它也像 Quick Sort 一样超快，但不幸的是它须要 O(n) 额外空间来同时存储两个子数组，末了合并它们。

基数排序利用计数排序作为子程序，因此它不是基于比较的算法。
我们怎么知道CS是不足的？假设我们必须对[1, n²] 中的元素进行排序。
利用 CS，我们须要 O(n²)。
我们须要一个线性算法——O(n+k)，个中元素在[1, k]范围内。
它从最不主要的一个（单位）开始，到最主要的（十、百等）对元素进行逐位排序。
额外空间（来自 CS）：O(n)。

搜索算法旨在检讨数据构造中元素的存在，乃至返回它。
有几种搜索方法，但这里是最受欢迎的两种：

该算法的方法非常大略：您从数据构造的第一个索引开始搜索您的值。
您将它们逐一比较，直到您的值和当前元素相等。
如果该特定值不在 DS 中，则返回 -1。

韶光繁芜度：O(n)

BS 是一种基于分而治之的高效搜索算法。
不幸的是，它只适用于排序的数据构造。
作为一种 DAC 方法，您连续将 DS 分成两半，并将搜索中的值与中间元素的值进行比较。
如果它们相等，则搜索结束。
无论哪种办法，如果您的值大于/小于它，搜索该当连续在右/左半部分。

韶光繁芜度：O(log n)

给定一个整数 n，打印所有小于或即是 n 的素数。

Eratosthenes 筛法是办理这个问题的最有效的算法之一，它完美地适用于小于10.000.000 的n 。

该方法利用频率列表/映射来标记[0, n]范围内每个数字的素数：如果 x 是素数，则ok[x]=0，否则ok[x]=1。

我们开始从列表中选择每个素数，并用 1 标记列表中的倍数——这样，我们选择未标记的 (0) 数。
末了，我们可以在 O(1) 中轻松回答任意数量的查询。

经典算法在许多运用中都是必不可少的，但我们可以进行一些优化。
首先，我们很随意马虎把稳到 2 是唯一的偶素数，因此我们可以单独检讨它的倍数，然后在范围内迭代以找到从 2 到 2 的素数。
其次，很明显，对付数字 x，我们之前在迭代 2、3 等时已经检讨了 2x、3x、4x 等。
这样，我们的乘数检讨 for 循环每次都可以从 x² 开始。
末了，纵然这些倍数中有一半是偶数，而且我们也在迭代奇素数，因此我们可以在倍数检讨循环中轻松地从 2x 迭代到 2x。

空间繁芜度：O(n)

韶光繁芜度：O(nlog(log n)) 用于经典算法，O(n) 用于优化算法。

给定长度为 n 的文本和长度为 m 的模式，找出文本中所有涌现的模式。

Knuth-Morris-Pratt 算法 (KMP) 是办理模式匹配问题的有效方法。

天真的办理方案基于利用“滑动窗口”，每次设置新的起始索引时，我们都会比较字符与字符，从文本的索引 0 开始到索引 nm。
这样，韶光繁芜度是 O(m(n-m+1))~O(nm)。

KMP 是对朴素办理方案的优化：它在 O(n) 中完成，并且当模式具有许多重复的子模式时效果最佳。
因此，它也利用滑动窗口，但不是将所有字符与子字符串进行比较，而是不断探求当前子模式的最长后缀，这也是它的前缀。
换句话说，每当我们在某些匹配后检测到不匹配时，我们就已经知道下一个窗口文本中的某些字符。
因此，再次匹配它们是没有用的，因此我们重新开始匹配文本中具有该前缀后的字符的相同字符。
我们怎么知道我们该当跳过多少个字符？好吧，我们该当构建一个预处理数组，见告我们该当跳过多少个字符。

Greedy 方法多用于须要优化且局部最优解导致全局最优解的问题。

也便是说，当利用 Greedy 时，每一步的最优解都会导致整体最优解。
然而，在大多数情形下，我们在一个步骤中做出的决定会影响下一步的决定列表。
在这种情形下，必须用数学方法证明算法。
Greedy 也会在一些数学问题上产生很好的办理方案，但不是全部（可能无法担保最佳办理方案）！

贪心算法常日有五个组成部分：

分数背包问题

给定n个物品的重量和代价，我们须要将这些物品放入容量为W的背包中，以得到背包中的最大总代价（许可取件物品：一件物品的代价与其重量成正比）。

贪心方法的基本思想是根据它们的代价/重量比对所有项目进行排序。
然后，我们可以添加尽可能多的全体项目。
当我们创造一件比背包中剩余重量 (w1) 重 (w2) 的物品时，我们将对其进行分割：仅取出w2-w1以最大化我们的利润。
担保这个贪心的办理方案是精确的。

动态方案 (DP) 是一种类似于分而治之的方法。
它还将问题分解为类似的子问题，但它们实际上是重叠和相互依赖的——它们不是独立办理的。

每个子问题的结果都可以在往后随时利用，它是利用影象（预先打算）构建的。
DP 紧张用于（韶光和空间）优化，它基于探求循环。

DP 运用包括斐波那契数列、河内塔、Roy-Floyd-Warshall、Dijkstra 等。
下面我们将谈论 0-1 背包问题的 DP 办理方案。

给定n个物品的重量和代价，我们须要将这些物品放入容量为W的背包中，以得到背包中的最大总值（不许可像贪婪办理方案中的那样分割物品）。
0-1 属性是由我们该当选择全体项目或根本不选择它的事实给出的。
我们构建了一个 DP 构做作为矩阵dp[i][cw]存储我们通过选择总权重为 cw 的 i 个工具可以得到的最大利润。
很随意马虎把稳到我们该当首先用v[i]初始化dp[1][w[i] ]，个中w[i]是第 i 个工具的权重，v[i] 是它的值。
复现如下：

dp[i][cw] = max(dp[i-1][cw], dp[i-1][cw-w[i]]+v[i])复制代码

我们轻微剖析一下。

dp[i-1][cw]描述了我们没有在背包中添加当前物品的情形。
dp[i-1][cw-w[i]]+v[i]便是我们添加item的情形。
话虽如此，dp[i-1][cw-w[i]]是采取 i-1 个元素的最大利润：以是它们的重量是当前重量，没有我们的物品重量。
末了，我们将项目的值添加到它。

答案存入dp[n][W]. 通过一个大略的不雅观察进行优化：在循环中，当前行仅受前一行的影响。
因此，将DP构造存储到矩阵中是不必要的，因此我们该当选择一个空间繁芜度更好的数组：O(n)。
韶光繁芜度：O(nW)。

给定两个序列，找出它们中存在的最宗子序列的长度。
子序列因此相同的相对顺序涌现的序列，但不一定是连续的。
例如，“bcd”、“abdg”、“c”都是“abcdefg”的子序列。

这是动态方案的另一个运用。
LCS 算法利用 DP 来办理上述问题。

实际的子问题是要分别从序列 A 中的索引 i 开始，分别从序列 B 中的索引 j 中找到最长公共子序列。

接下来，我们将构建 DP 构造lcs[ ][ ]（矩阵），个中lcs[i][j]是从 A 中的索引 i 开始，分别是 B 中的索引 j 的公共子序列的最大长度。
我们将以自顶向下的办法构建它。
显然，办理方案存储在lcs[n][m] 中，个中 n 是 A 的长度，m 是 B 的长度。

递推关系非常大略直不雅观。
为大略起见，我们将考虑两个序列都是 1 索引的。
首先，我们将初始化lcs[i][0] , 1<=i<=n和lcs[0][j] , 1<=j<=m , 0, 作为基本情形（没有从 0 开始的子序列）。
然后，我们将考虑两种紧张情形：如果A[i]即是B[j]，则lcs[i][j] = lcs[i-1][j-1]+1（比之前的 LCS 多一个相同的字符）。
否则，它将是lcs[i-1][j]（如果不考虑A[i]）和lcs[i][j-1]（如果不考虑B[j]）之间的最大值）。

韶光繁芜度：O(nm) 附加空间：O(nm)

给定一个包含 n 个元素的序列 A，找到最宗子序列的长度，使其所有元素按递增顺序排序。
子序列因此相同的相对顺序涌现的序列，但不一定是连续的。
例如，“bcd”、“abdg”、“c”是“abcdefg”的子序列。

LIS 是另一个可以利用动态方案办理的经典问题。

利用数组l[ ]作为 DP 构造来探求递增子序列的最大长度，个中l[i]是包含A[i]的递增子序列的最大长度，其元向来自[A[i] ], ..., A[n]] 子序列。
l[i]为 1，如果A[i]之后的所有元素比它小。
否则，在 A[i] 之后大于它的所有元素之间的最大值为 1+。
显然，l[n]=1，个中 n 是 A 的长度。
实现是自底向上的（从末端开始）。

在搜索当前元素之后的所有元素之间的最大值时涌现了一个优化问题。
我们能做的最好的事情是二分搜索最大元素。

为了找到现在已知的最大长度的子序列，我们只须要利用一个额外的数组ind[]，它存储每个最大值的索引。

韶光繁芜度：O(nlog n)

附加空间：O(n)

给定同一平面中的一组 n 个点，找到包含所有给定点（位于多边形内部或其边上）的最小面积凸多边形。
这种多边形称为凸包。
凸包问题是一个经典的几何，在现实生活中有很多运用。
例如，碰撞避免：如果汽车的凸包避免碰撞，那么汽车也能避免碰撞。
路径的打算是利用汽车的凸表示完成的。
形状剖析也是在凸包的帮助下完成的。
这样，图像处理很随意马虎通过匹配模型的凸毛病树来完成。

有一些算法用于探求凸包，如 Jarvis 算法、Graham 扫描等。
本日我们将谈论 Graham 扫描和一些有用的优化。

格雷厄姆扫描按极角对点进行排序——由某个点和其他选定点确定的线的斜率。
然后用一个栈来存储当前时候的凸包。
当一个点 x 被压入堆栈时，其他点会被弹出堆栈，直到 x 与末了两个点所确定的线形成小于 180° 的角度。
末了，引入堆栈的末了一个点关闭多边形。
由于排序，这种方法的韶光繁芜度为 O(nlog n)。
但是，这种方法在打算斜率时会产生精度偏差。

一种改进的办理方案具有相同的韶光繁芜度，但偏差较小，按坐标（x，然后是 y）对点进行排序。
然后我们考虑由最左边和最右边的点形成的线，并将问题分为两个子问题。
末了，我们在这条线的每一边找到了凸包。
所有给定点的凸包是两个包的重聚。

遍历图的问题是指以特定顺序访问所有节点，常日沿途打算其他有用信息。

广度优先搜索 (BFS) 算法是确定图是否连通的最常用方法之一——或者换句话说，查找 BFS 源节点的连通分量。

BFS 还用于打算源节点和所有其他节点之间的最短间隔。
BFS 的另一个版本是 Lee 算法，用于打算网格中两个单元格之间的最短路径。

该算法首先访问源节点，然后访问将被推入行列步队的邻居。
行列步队中的第一个元素被弹出。
我们将访问它的所有邻居，并将之前未访问的邻居推入行列步队。
重复该过程直到行列步队为空。
当行列步队为空时，表示所有可达顶点都已访问完毕，算法结束。

深度优先搜索 (DFS) 算法是另一种常见的遍历方法。
在检讨图形的连通性时，它实际上是最好的选择。

首先，我们访问根节点并将其压入堆栈。
虽然堆栈不为空，但我们检讨顶部的节点。
如果该节点有未访问的邻居，则选择个中一个并将其压入堆栈。
否则，如果它的所有邻居都被访问过，我们就会弹出这个节点。
当堆栈变空时，算法结束。

经由这样的遍历，就形成了一个DFS树。
DFS 树有很多运用；最常见的一种是存储每个节点的“开始”和“结束”韶光——它进入堆栈的时候，分别是它从堆栈中弹出的时候。

Floyd-Warshall / Roy-Floyd 算法办理了所有对最短路径问题：找到给定边加权有向图中每对顶点之间的最短间隔。

FW 是一个动态方案运用程序。
DP 构造（矩阵）dist[ ][ ]用输入图矩阵初始化。
然后我们将每个顶点视为其他两个节点之间的中间体。
最短路径在每两对节点之间更新，任何节点 k 作为中间顶点。
如果 k 是 i 和 j 之间排序路径中的中间值，则dist[i][j]成为dist[i][k]+dist[k][j]和dist[i][j]之间的最大值。

韶光繁芜度：O(n³) 空间繁芜度：O(n²)

给定一个图和图中的一个源顶点，找出从源到给定图中所有顶点的最短路径。

Dijkstra 算法用于在加权图中找到这样的路径，个中所有的权重都是正的。

Dijkstra 是一种贪心算法，它利用以源节点为根的最短路径树（SPT）。
SPT 是一种自平衡二叉树，但该算法可以利用堆（或优先级行列步队）来实现。
我们将谈论堆办理方案，由于它的韶光繁芜度是 O(|E|log |V|)。
这个想法是利用图形的毗邻列表表示。
这样，节点将利用 BFS （广度优先搜索）在 O(|V|+|E|) 韶光内遍历。

所有顶点都用 BFS 遍历，那些最短间隔尚未终极确定的顶点被存储到最小堆（优先行列步队）中。

创建最小堆并将每个节点连同它们的间隔值一起推入个中。
然后，源成为间隔为 0 的堆的根。
其他节点将无限分配为间隔。
当堆不为空时，我们提取最小间隔值节点 x。
对付与 x 相邻的每个顶点 y，我们检讨 y 是否在最小堆中。
在这种情形下，如果间隔值大于 (x, y) 的权重加上 x 的间隔值，那么我们更新 y 的间隔值。

正如我们之前所说，Dijkstra 仅适用于正加权图。
贝尔曼办理了这个问题。
给定一个加权图，我们可以检讨它是否包含负循环。
如果没有，那么我们还可以找到从我们的源到其他源的最小间隔（可能为负权重）。

Bellman-Ford 非常适宜分布式系统，只管它的韶光繁芜度是 O(|V| |E|)。

我们初始化一个 dist[] 就像在 Dijkstra 中一样。
对付 |V|-1次，对付每个(x, y)边，如果dist[y] > dist[x] + (x, y) 的权重，那么我们用它更新dist[y]。

我们重复末了一步以可能找到负循环。
这个想法是，如果没有负循环，末了一步担保最小间隔。
如果有任何节点在当前步骤中的间隔比上一步中的间隔短，则检测到负循环。

我们之前已经谈论过什么是最小天生树。

有两种算法可以找到图的 MST：Prim（适用于密集图）和 Kruskal（适用于大多数图）。
现在我们将谈论 Kruskal 算法。

Kruskal 开拓了一种贪心算法来探求 MST。
它在罕有图上很有效，由于它的韶光繁芜度是 O(|E|log |V|)。

该算法的方法如下：我们按权重的递增顺序对所有边进行排序。
然后，选取最小的边。
如果它不与当前 MST 形成循环，我们将其包括在内。
否则，丢弃它。
重复末了一步，直到 MST 中有 |V|-1 条边。

将边包含到 MST 中是利用 Disjoint-Set-Union 完成的，这也在前面谈论过。

有向无环图 (DAG) 只是一个不包含循环的有向图。

DAG 中的拓扑排序是顶点的线性排序，使得对付每个拱形(x, y)，节点 x 涌如今节点 y 之前。

显然，拓扑排序中的第一个顶点是一个入度为 0 的顶点（没有拱形指向它）。

另一个分外属性是 DAG 没有唯一的拓扑排序。

BFS （广度优先搜索）实现遵照此例程：找到一个入度为 0 的节点并将第一个推入排序。
该顶点已从图中删除。
由于新图也是一个 DAG，我们可以重复这个过程。

在 DFS 期间的任何时候，节点都可以属于以下三个种别之一：

如果在 DAG 中的 DFS 期间，节点 x 具有到节点 y 的输出边，则 y 属于第一类或第三类。
如果 y 在堆栈上，则(x, y)将结束一个循环，这与 DAG 定义相抵牾。

这个属性实际上见告我们一个顶点在它的所有传出邻居都被弹出后从堆栈中弹出。
因此，要对图进行拓扑排序，我们须要跟踪弹出顶点的逆序列表。