计算机语言只是一种工具。光学习语言的规则还不够,最重要的是学会针对各种类型的问题,拟定出有效的解决方法和步骤即算法。有了正确而有效的算法,可以利用任何一种计算机高级语言编写程序,使计算机进行工作。
图已经成为一种强大的建模和捕获真实场景中的数据的手段,比如社交媒体网络、网页和链接,以及GPS中的位置和路线。如果您有一组相互关联的对象,那么您可以使用图来表示它们。
在这篇文章中,我将简要地解释10个对分析和应用非常有用的基本图形算法。
首先,让我们介绍图。
图由一组有限的顶点或节点和一组连接这些顶点的边组成。如果两个顶点通过同一条边互相连接,则称它们为邻接。
下面给出了一些与图相关的基本定义。您可以参考图1中的示例。
遍历或搜索是可在图上执行的基本操作之一。在广度优先搜索(BFS)中,我们从一个特定的顶点开始,在进入下一层的顶点之前探索它当前深度的所有邻居。与树不同,图可以包含循环(第一个和最后一个顶点是相同的路径)。因此,我们必须跟踪访问过的顶点。在实现BFS时,我们使用队列数据结构。
图2表示一个示例图的BFS遍历的动画。注意顶点是如何被发现(黄色)和被访问(红色)的。
应用
在深度优先搜索(DFS)中,我们从一个特定的顶点开始,在回溯(backtracking)之前沿着每个分支尽可能地搜索。在DFS中,我们还需要跟踪访问过的顶点。在实现DFS时,我们使用堆栈数据结构来支持回溯。
图3表示对图2中使用的同一个示例图进行DFS遍历的动画。注意它是如何遍历到深度和回溯的。
应用
从一个顶点到另一个顶点的最短路径是图中应该移动的边的权值总和最小的路径。
图4显示了一个动画,其中确定了图中顶点1到顶点6的最短路径。
算法
Dijkstra的最短路径算法 、bellman算法
应用
用于在谷歌maps或Apple maps等地图软件中查找从一个地方到另一个地方的路线。
用于网络中解决最小时延路径问题。
在抽象机器中,通过不同状态之间的转换来确定达到某一目标状态的选择(例如,可以用来确定赢得一场比赛的最小可能的走法数)。
循环是图中第一个顶点和最后一个顶点相同的路径。如果我们从一个顶点出发,沿着一条路径,最后到达起始点,那么这条路径就是一个循环。循环检测是检测这些循环的过程。图5显示了遍历一个循环的动画。
算法
Floyd周期检测算法、布伦特算法
应用
最小生成树是图的边的子集,它连接所有边权值最小和的顶点,不包含任何循环。
图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之后。
算法
Kahn算法
基于深度优先搜索的算法
应用
图着色在保证一定条件下给图的元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中,我们尝试用k种颜色给图的顶点着色,任何两个相邻的顶点都不应该有相同的颜色。其他着色技术包括边缘着色和脸部着色。
图的色数是为图着色所需的颜色的最小数目。
图9显示了使用4种颜色的示例图的顶点着色。
算法
使用广度优先搜索或深度优先搜索的算法、贪婪着色
应用
我们可以将一个图建模为一个以边权值作为流量容量的流网络。在最大流量问题中,我们必须找到一个能获得最大可能流量的流动路径。
图10显示了一个确定网络的最大流量和最终流量值的动画示例。
算法
Ford-Fulkerson算法、Edmonds-Karp算法、Dinic的算法
应用
图中的匹配是指一组没有共同顶点的边(也就是说,没有两条边共享一个共同顶点)。如果一个匹配包含尽可能多的顶点匹配的边的最大数量,那么这个匹配被称为最大匹配。
图11显示了获得一个二分图的完全匹配的动画,该二分图有两组顶点,分别用橙色和蓝色表示。
算法
Hopcroft-Karp算法、匈牙利算法、Blossom 算法
应用
Copyright © QY Network Company Ltd. All Rights Reserved. 2003-2018 群英 版权所有 茂名市群英网络有限公司
增值电信经营许可证 : B1.B2-20140078 粤ICP备09006778号-36 粤公网安备 44090202000006号 粤工商备P091701000595