图算法

在本文中，您将学习一些最常用的图算法的简要解释，它们在当今世界有着巨大的应用。图涵盖了实现它们时所遇到的大部分高级数据结构技术，而了解哪种图算法最适合当前时刻，将是您在这里学习的内容。首先，让我们从最基础的图的概念开始有了清晰的认识。

什么是图？

图是编程中一种独特的数据结构，它由有限的节点或顶点集以及连接这些顶点的边集组成。此时，相邻的顶点可以称为通过同一条边相互连接的顶点。简单来说，图是顶点和边共享某种连接或关系的视觉表示。尽管您可能熟悉许多图算法，但只有其中一些被投入使用。原因很简单，因为标准的图算法被设计成能够用几行逻辑编码的技术解决数百万个问题。在某种程度上，一个完美的算法是专门为实现如此高效的结果而优化的。

图的类型

在本文中，您将看到各种类型的图算法，但在那之前，让我们先看一些术语，以阐明它们之间的基本差异。

阶：阶定义了图中顶点的总数。

大小：大小定义了图中边的数量。

自环：连接从顶点到自身的边。

孤立顶点：图中未与其他任何顶点连接的顶点。

顶点度：定义为图中连接到顶点的边的数量。

加权图：顶点具有值或权重的图。

无权图：顶点没有值或权重的图。

有向图：具有方向指示器的图。

无向图：未定义方向的图。

现在，让我们继续主要讨论，学习不同类型的图算法。

广度优先搜索

遍历或搜索是处理图时最常用的操作之一。因此，在广度优先搜索（BFS）中，您从一个特定的顶点开始，算法会尝试在移动到下一个顶点遍历级别之前访问给定深度下的所有邻居。与树不同，图可能包含循环路径，其中第一个和最后一个顶点始终是相同的。因此，在 BFS 中，您需要跟踪您正在访问的所有顶点。为了实现这种顺序，您使用队列数据结构，该结构遵循先进先出（First-in, First-out）的方法。要理解这一点，请参见下图。

算法

1. 开始将图中的任何一个顶点放入队列的末尾。
2. 首先，移除队列的前一个元素，并将其添加到已访问节点列表中。
3. 接下来，创建该列表中邻接顶点的节点，并将它们添加到尚未访问过的节点中。
4. 重复步骤二和三，直到队列为空。

伪代码

复杂度：0(V+E)，其中 V 是顶点，E 是边。

应用

BFS 算法有各种应用。例如，它用于确定最短路径和最小生成树。它还用于网络爬虫创建网页索引。它还用于驱动社交媒体网络上的搜索引擎，并有助于查找 BitTorrent 中的点对点网络。

深度优先搜索

在深度优先搜索（DFS）中，您从特定顶点开始，然后沿着所有分支尽可能多地进行探索，然后再回溯。在 DFS 中，跟踪已访问节点非常重要，为此，您可以使用栈数据结构。

算法

1. 开始将图的一个顶点放在栈顶。
2. 将栈顶元素取出，并将其添加到已访问顶点列表中。
3. 创建该顶点所有邻接节点的列表，然后将这些节点添加到栈顶的未访问节点中。
4. 重复步骤 2 和 3，直到栈变空。

伪代码

应用

DFS 在寻找两个顶点之间的路径和检测环时发挥作用。此外，可以使用 DFS 算法轻松完成拓扑排序。DFS 也用于单解谜题。

Dijkstra 的最短路径算法

Dijkstra 的最短路径算法用于查找从一个顶点到另一个顶点的最小路径。顶点之和应使其所经过的权重之和输出最小。最短路径算法是一种高度精细的算法，其工作原理是尽可能地获得效率。考虑下图。

算法

1. 将所有顶点设置为无穷大，除了源顶点。
2. 将源顶点以（距离，顶点）的形式压入最小优先级队列。
3. 从优先级队列中弹出到源顶点的距离最小的顶点。
4. 弹出距离最小的顶点后更新距离，并使用（顶点距离 + 权重 < 下一个顶点距离）计算顶点距离。
5. 如果您发现已访问的顶点已被弹出，则直接跳过，继续前进。
6. 重复执行这些步骤，直到优先级队列为空。

伪代码

应用

Dijkstra 的最短路径算法用于查找从一个地点到另一个地点的旅行距离，例如 Google Maps 或 Apple Maps。此外，它在网络中广泛用于规划最小延迟路径问题，并在抽象机器中用于识别到达特定目标的选项，例如数字游戏或赢得比赛的步骤。

环检测

在图算法中，环定义为一条路径，其中第一个和最后一个顶点通常被认为是相同的。例如，如果您从一个顶点开始沿着随机路径行进，您可能会到达您最初开始的那个点。因此，这形成了一个链或循环算法，用于覆盖遍历过程中的所有节点。因此，环检测基于检测这种类型的环。考虑下图。

伪代码

应用

循环算法用于基于消息的分布式系统和大规模集群处理系统。它主要还用于检测并发系统中的死锁以及各种加密应用，其中密钥用于管理带有加密值的消息。

最小生成树

最小生成树定义为图的边子集，它没有环并且与所有顶点良好连接，使得通过边权重的总和最小。它仅取决于生成树的成本以及顶点覆盖的最小跨度或最小距离。根据边权重和各种其他因素，可能存在许多最小生成树。

伪代码

应用

最小生成树在网络设计中发挥作用，并在数据结构中的旅行商问题中得到广泛应用。它还可以用于查找最小成本加权完美匹配和多端点最小割问题。MST 还在图像和手写识别以及聚类分析领域找到应用。

拓扑排序

图的拓扑排序遵循对顶点进行线性排序的算法，以便每个有向图具有顶点排序，确保该顶点在其之前。用户可以通过查看下面的示例图像更准确地理解它。

在上例中，您可以可视化未排序图和拓扑排序图的顺序。拓扑排序图确保对路径中的顶点进行排序。

伪代码

应用

拓扑排序在 Kahn 算法和 DFS 算法中有应用。在现实生活应用中，拓扑排序用于调度指令和数据序列化。它还广泛用于确定要编译的任务以及解决链接器中的依赖关系。

图着色

图着色算法遵循在特定条件下为图中元素分配颜色的方法。条件基于技术或算法。因此，顶点着色是这里遵循的常用着色技术。首先，在此方法中，您尝试使用 k 种颜色为顶点着色，确保两个相邻顶点不具有相同的颜色。其他方法包括面着色和边着色。这两种方法也应确保任何边或面不具有不连续的颜色。图的着色通过知道色数来确定，色数也是所需的最小颜色数。考虑下图以了解其工作原理。

伪代码

应用

图着色在数据结构以及解决现实问题方面有广泛的应用。例如，它用于时间表安排和手机无线电频率分配。它还用于数独游戏，并检查给定图是否为二分图。图着色还可用于地理地图，用不同颜色标记国家和地区。

最大流

最大流算法通常被视为一种问题解决算法，其中图被建模为网络流基础设施。因此，最大流是通过找到具有最大流速的流路径来确定的。最大流速由增广路径确定，增广路径是来自源节点的总流等于汇节点处的流。下图是相同的说明。

应用

就像您一样，最大流问题涵盖了诸如 Ford-Fulkerson 算法、Edmonds-Karp 算法和 Dinic 算法等流行算法的应用，正如您在上面看到的伪代码中那样。在现实生活中，它在航班机组人员调度和图像分割（前景和背景）方面有应用。它也用于篮球等游戏中，其中分数设置为最大估计值，具有当前分区领导者。

匹配

图中的匹配算法或技术定义为没有共同顶点的边。如果匹配的边数量最多，并且尽可能多地匹配顶点，则可以将匹配称为最大匹配。它遵循一种特定的方法来确定完全匹配，如下面的图像所示。

应用

匹配用于 Hopcroft-Karp 算法和 Blossom 算法等算法中。它还可以用于使用涵盖匹配概念的匈牙利算法来解决问题。在现实生活示例中，匹配可用于资源分配和旅行优化，以及稳定婚姻和顶点覆盖问题等问题。

结论

在本文中，您遇到了许多图着色算法和技术，它们在现实生活的各个方面都有日常应用。您学会了如何根据情况实现它们，因此伪代码帮助您以战略性和高效的方式处理信息。图算法被认为是该领域的一个重要方面，不仅限于使用数据结构解决问题，还包括 Google Maps 和 Apple Maps 等通用任务。然而，初学者可能会发现实现图算法很困难，因为它们性质复杂。因此，强烈建议您仔细阅读本文，因为它涵盖了从零开始的所有内容。