10种图算法直观可视化解释( 二 ) _图算法

最小生成树

文章插图

最小生成树是图的边的子集，它连接所有边权值最小和的顶点，不包含任何循环。
图6是一个显示获得最小生成树的过程的动画。
算法
Prim算法、Kruskal算法
应用
· 用于在计算机网络中构建广播树。
· 用于基于图的聚类分析。
· 用于图像分割。
· 用于社会地理区域的区域化，将区域划分为相邻区域。
强连通分量(strongly connected components)

文章插图

如果图中的每个顶点都能从其他每个顶点到达，那么这个图就是强连通的。
图7显示了一个示例图，其中包含三个强连接的组件，顶点用红色、绿色和黄色表示。
算法
Kosaraju的算法、Tarjan的强连通分量算法
应用
· 用于计算Dulmage-Mendelsohn分解，它是完全二分图的一种分类。
· 在社交网络中，用来寻找一群关系密切的人，并根据共同的兴趣提出建议。
拓扑排序

文章插图

图的拓扑排序是对它的顶点进行线性排序，因此对于排序中的每条有向边(u, v) ，顶点u都在v之前。
图8显示了顶点(1、2、3、5、4、6、7、8)的拓扑排序示例。可以看到顶点5应该在顶点2和3之后。类似地，顶点6应该在顶点4和5之后。
算法
Kahn算法基于深度优先搜索的算法
应用
· 用于指令调度。
· 用于数据序列化。
· 用于确定在makefile中执行的编译任务的顺序。
· 用于解析链接器中的符号依赖关系。
图着色

文章插图

图着色在保证一定条件下给图的元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中，我们尝试用k种颜色给图的顶点着色，任何两个相邻的顶点都不应该有相同的颜色。其他着色技术包括边缘着色和脸部着色。
图的色数是为图着色所需的颜色的最小数目。
图9显示了使用4种颜色的示例图的顶点着色。
算法
使用广度优先搜索或深度优先搜索的算法、贪婪着色
应用
· 用于制定时间表。
· 用于分配移动无线电频率。
· 用于模拟和解决游戏，如数独。
· 用于检查图是否是二分图。
· 用于在相邻国家或州的地理地图上涂上不同颜色。
最大流(Maximum Flow)

文章插图

我们可以将一个图建模为一个以边权值作为流量容量的流网络。在最大流量问题中，我们必须找到一个能获得最大可能流量的流动路径。
图10显示了一个确定网络的最大流量和最终流量值的动画示例。
算法
Ford-Fulkerson算法、Edmonds-Karp算法、Dinic的算法
应用
· 用于航空公司调度，安排航班机组人员。
· 用于图像分割，在图像中找到背景和前景。
· 用来淘汰那些不能赢得足够的比赛来赶上当前分区的球队。
匹配

文章插图

图中的匹配是指一组没有共同顶点的边(也就是说，没有两条边共享一个共同顶点) 。如果一个匹配包含尽可能多的顶点匹配的边的最大数量，那么这个匹配被称为最大匹配。
图11显示了获得一个二分图的完全匹配的动画，该二分图有两组顶点，分别用橙色和蓝色表示。
算法
Hopcroft-Karp算法、匈牙利算法、Blossom 算法
应用
· 用于为新娘和新郎牵线搭桥(婚姻的稳定问题) 。
· 用于确定顶点覆盖。
· 用于交通理论中解决出行资源配置和优化问题。
最后我希望这篇文章对图形算法的简单概括介绍对您有所帮助
作者：Vijini Mallawaarachchi
deephub翻译组