一种解释10个对分析和应用非常有用的基本图形算法

图表已成为在现实世界场景中建模和捕获数据的强大手段，例如社交媒体网络、网页和链接，以及 GPS 中的位置和路线。如果您有一组相互关联的对象，那么您可以使用图表来表示它们。

在本文中，我将简要介绍 10 种对分析和应用非常有用的基本图算法。

首先，我们来介绍一下图表。

什么是图片？

图由一组有限的顶点或节点以及一组连接这些顶点的边组成。如果两个顶点通过同一条边相互连接，则称它们是相邻的。

下面给出了与图表相关的一些基本定义。您可以参考图 1 中的示例。

Order：图中的顶点数 Size：图中的边数 Vertex degree：与某个顶点相关联的边数Isolated vertex：图中不与其他顶点相连的顶点 Self-loop ：从顶点到自身的一条线 边有向图：所有边都有一个方向来表示起点和终点的图 无向图：有边没有方向的图 加权图：图的边有权重 p>

广度优先搜索

遍历或搜索是可以在图上执行的基本操作之一。在广度优先搜索（BFS）中，我们从一个特定的顶点开始，并在其当前深度探索其所有邻居，然后再移动到下一层的顶点。与树不同，图可以包含循环（第一个和最后一个顶点是相同的路径）。因此，我们必须跟踪访问的顶点。在实现 BFS 时，我们使用队列数据结构。

图 2 显示了 BFS 遍历示例图的动画。注意顶点是如何被发现（黄色）和访问（红色）的。

申请

深度优先搜索

在深度优先搜索（DFS）中，我们从一个特定的顶点开始，在回溯之前尽可能沿着每个分支搜索。在 DFS 中，我们还需要跟踪访问过的顶点。在实现 DFS 时，我们使用堆栈数据结构来支持回溯。

图 3 显示了 DFS 遍历图 2 中使用的相同示例图的动画。注意它如何遍历深度和回溯。

申请

最短路径

从一个顶点到另一个顶点的最短路径是图中应该移动的边的权重之和最小的路径。

图 4 显示了一个动画，其中确定了图中从顶点 1 到顶点 6​​ 的最短路径。

算法

Dijkstra 的最短路径算法，贝尔曼算法

申请

用于在地图软件（例如 Google 地图或 Apple 地图）中查找从一个地方到另一个地方的路线。

用于解决网络中的最小延迟路径问题。

在抽象机器中，达到目标状态的选择取决于不同状态之间的转换（例如，可用于确定赢得比赛的最小可能移动数）。

循环检测循环检测

循环是图中第一个顶点和最后一个顶点相同的路径。如果我们从一个顶点开始，沿着一条路径走，最后到达起点，那么这条路径就是一个循环。环路检测是检测这些环路的过程。图 5 显示了遍历循环的动画。

算法

弗洛伊德循环检测算法、布伦特算法

申请

最小生成树

最小生成树是图的边的子集，它连接具有最小边权总和的所有顶点迷宫最短路径问题新算法，并且不包含任何循环。

图6是一个动画，展示了获取最小生成树的过程。

算法

Prim 算法、Kruskal 算法

申请

强连通分量

如果图中的每个顶点都可以从其他每个顶点到达，则该图是强连通的。

图 7 显示了一个示例图，其中包含三个强连通分量迷宫最短路径问题新算法，顶点分别用红色、绿色和黄色表示。

算法

Kosaraju 算法，Tarjan 强连通分量算法

申请

拓扑排序

图的拓扑排序对其顶点进行线性排序，因此对于排序中的每条有向边 (u, v)，顶点 u 在 v 之前。

图 8 显示了顶点（1、2、3、5、4、6、7、8) 示例拓扑排序。你可以看到顶点 5 应该在顶点 2 和 3 之后。同样，顶点 6 应该在顶点 4 和 5 之后。

算法

基于深度优先搜索的卡恩算法

申请

图片着色

图形着色在特定条件下为图形元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中，我们尝试用 k 种颜色对图的顶点进行着色，相邻的两个顶点不应该具有相同的颜色。其他着色技术包括边缘着色和面部着色。

图表的色数是为图表着色所需的最少颜色数。

图 9 显示了使用 4 种颜色的示例图的顶点着色。

算法

使用广度优先搜索或深度优先搜索、贪心着色的算法

申请

最大流量

我们可以将图建模为以边权重为流量容量的流网络。在最大流量问题中，我们必须找到一条能够获得最大可能流量的流路。

图 10 显示了一个动画示例，用于确定网络的最大和最终流量值。

算法

Ford-Fulkerson 算法、Edmonds-Karp 算法、Dinic 算法

申请

匹配

图中的匹配是一组没有公共顶点的边（即没有两条边共享一个公共顶点）。如果匹配包含尽可能多的顶点匹配最大边数，则称为最大匹配。

图 11 显示了为具有两组顶点（以橙色和蓝色表示）的二部图获得精确匹配的动画。

算法

Hopcroft-Karp算法、匈牙利算法、Blossom算法

申请

最后

希望本文对图算法的简要概述对您有所帮助

作者：Vijini Mallawaarachchi

deephub 翻译团队

谷歌历史上第二大收购

Android再次推“杀手锏”功能

国内开源项目力克英伟达和微软