10种算法一文打尽！基本图表算法的视觉化阐释

图源：unsplash

来源：读芯术

 

在社交媒体网络、网页和链接、GPS中位置和路线等真实场景中，图表已成为一种强大的建模和捕获数据手段，如果一组对象相互关联，则可以用图表来表示。

 

本文就将简要解释10个非常有助于分析和应用的基本图表算法。

 

首先，图表是什么？

 

图表由一组有限顶点或节点和一组连接这些顶点的边组成，如果两个顶点通过同一条边互相连接，则称之为邻接。下面是一些与图表相关的基本定义，可以参考图中示例。

 

·    顺序：图表中的顶点数

·    大小：图表中的边数

·    顶点度：入射到顶点的边数

·    孤立顶点：未连接到图中任何其它顶点的顶点

·    自循环：从顶点到自身的一条边

·    有向图：图中所有的边都有方向，来表示起点和终点

·    无向图：图的边无方向

·    加权图：图的边有权值

·    未加权图：图的边无权值

 

图1：图表术语的可视化

 

1.广度优先搜索

 

图2 ：广度优先搜索（BFS）遍历动画

 

遍历或搜索是图表上执行的基本操作之一。在广度优先搜索(BFS)中，从特定某个顶点开始，在进入下一层的顶点前先探索它当前深度的所有相关信息。与树不同，图表可以包含循环(第一个和最后一个顶点是相同的路径)。因此，必须跟踪访问过的顶点。在实现BFS时，应使用队列数据结构。

 

图2是一个示例图的BFS遍历的动画，注意一下顶点如何被发现(黄色)和被访问(红色)。

 

应用：

·    用于社交网络搜索

·    用于确定最短路径和最小生成树

·    被搜索引擎爬网程序用于构建网页索引

·    用于查找对等网络（如BitTorrent）中的可用邻近节点

 

2.深度优先搜索

 

图3：为深度优先搜索（DFS）的遍历动画

 

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

 

图3对图2中使用的同一个示例图进行DFS遍历的动画，注意它如何遍历到深度和回溯。

 

应用：

·    用于查找两个顶点之间的路径

·    用于检测图中的循环

·    用于拓扑排序

·    用于解决只有一种解决方案的难题（例如迷宫）

 

3.最短路径

 

图4动画显示了从顶点1到顶点6的最短路径

 

从一个顶点到另一个顶点的最短路径是图形中的路径，因此应使移动边的权重之和最小。图4显示了一个动画，其中确定了图中顶点1到顶点6的最短路径。

 

算法：

·    Dijkstra的最短路径算法

·    贝尔曼福特（Bellman–Ford）算法

 

应用：

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

·    用于在Google或Apple地图等软件中查找一个位置到另一位置的路线。

·    用于抽象机器中，通过不同状态之间的转换来确定达到某一目标状态的方法。例如，可以用来确定如何用最少走法赢得一场比赛。

4.循环检测

 

图5：一个循环

 

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

 

算法：

·    弗洛伊德循环检测算法

·    布伦特算法

 

应用：

·    用于基于消息的分布式算法

·    用于使用集群上的分布式处理系统处理大规模图表

·    用于检测并发系统中的僵局

·    在加密应用程序中用于确定能够将消息映射到相同加密值消息的**

 

5.最小生成树

 

图6.显示最小生成树的动画

 

最小生成树是图表边的子集，它连接所有边权值最小和的顶点，不包含任何循环。图6是一个获得最小生成树过程的动画。

 

算法：

·    普林演算法

·    克鲁斯卡尔算法

 

应用：

·    用于在计算机网络中构建广播树

·    用于基于图表的聚类分析

·    用于图像分割

·    用于社会地理领域的区域化，将区域划分为相邻区域。

 

6.强连通分量

 

图7：强连通分量

 

如果图表中的每个顶点都能通过其他顶点到达，那么这个图就是强连通的。图7包含三个强连接分量，顶点分别用红色、绿色和黄色表示。

 

算法：

·    Kosaraju算法

·    Tarjan强连通分量算法

 

应用：

·    用于计算Dulmage Mendelsohn分解，是二分图表边的一种分类。

·    用于社交网络中，根据共同爱好，发现并推荐具有密切联系的人。

 

7.拓扑排序

 

图8：图中顶点的拓扑排序

 

图表的拓扑排序是对其顶点进行线性排序，因此对于排序中的每条有向边(u, v)，顶点u都在v之前。图8显示了顶点(1、2、3、5、4、6、7、8)的拓扑排序示例。可以看到，顶点5应在顶点2和3之后。同样，顶点6应该在顶点4和5之后。

 

算法：

·    卡恩算法

·    基于深度优先算法

 

应用：

·    用于指令调度

·    用于数据序列化

·    用于确定要在生成文件中执行的编译任务的顺序

·    用于解析链接器中的符号依赖关系

 

8.图着色

 

图9：顶点着色

 

图着色指的是在保证一定条件下给图的元素分配颜色，顶点着色是最常用的图形着色技术。在顶点着色中，我们尝试用k种颜色给图的顶点着色，任何两个相邻的顶点颜色都不相同。其他着色技术包括边缘着色和面部着色。图的色数是为图着色所需颜色的最小数目。图9显示了用4种颜色为顶点着色。

 

算法：

·    使用广度优先搜索或深度优先搜索的算法

·    贪婪着色

 

应用：

·    用于制定时间表

·    用于分配移动无线电频率

·    用于建模和求解数独游戏

·    用于检查图是否为二部图

·    用于在相邻国家或州的地图上用不同颜色着色

 

9.最大流量

 

图10：确定最大流量

 

可以将一个图建模为以边权值作为流量容量的流网络。在最大流量问题中，必须找到能获得最大可能流量速率的流动路径。图10是一个确定网络的最大流量和最终流量值的动画示例。

 

算法：

·    Ford-Fulkerson算法

·    Edmonds–Karp算法

·    Dinic算法

 

应用：

·    用于航空公司调度，安排航班机组人员。

·    用于图像分割，查找图像中的背景和前景。

·    用来淘汰那些无法赢得比赛、无法与当前队伍优秀者相匹敌的队员。

 

10.匹配

 

图11：二部图匹配

 

图表中的匹配是一组没有共同顶点的边(也就是说，任何两条都没有共同顶点)。如果一个匹配包含尽可能多顶点匹配的边的最大数量，那么这个匹配被称为最大匹配。图11显示了获得二部图的完全匹配动画，该二部图有两组顶点，分别用橙色和蓝色表示。

 

算法：

·    霍普克洛夫特－卡普（Hopcroft–Karp）算法

·    匈牙利（Hungarian）算法

·    开花算法

 

应用：

·    用于为新娘和新郎牵线搭桥（婚姻的稳定问题）

·    用于确定顶点覆盖率

·    用于交通理论中解决出行资源配置和优化问题

 

图源：unsplash

这10种基本图表算法应用广泛，你get了吗？

近期开班情况

课程详情请扫码咨询