快速介绍基本10种算法，并进行实例和可视化
照片是一种强大的建模和捕获真实场景数据的方式，包括社交媒体网络、网页和链接、在GPS中的位置和路线。 如果有一组相关的对象，则可以使用图来表示它们。
本文简要介绍了10种对分析和应用非常有用的基本图形算法。
首先，介绍一下图吧。
什么是图？ 图由一组有限的顶点或节点以及连接这些顶点的一组边组成。 如果两个顶点在同一边相连，则它们称为相邻。
以下是与图相关的基本定义。 请参见图1中的示例。
次数Order:图中顶点的数量边数Size:图中的边数顶点度Vertex degree:与顶点相关联的边的数量孤立顶点Isolated vertex:图中未连接到其他顶点的顶点， 从循环Self-loop:的顶点到自身的一条边有向图directer 360所有边都有表示起点和终点的方向的图无向图无向图Undirected graph:具有无方向边的图赋权法图
广度优先搜索(Breadth-first search ) )。
或搜索是可以在图中执行的基本操作之一。 在广度优先搜索(BFS )中，从某个特定顶点开始，在进入下一个层次的顶点之前搜索其当前深度的所有邻居。 与树不同，图可以包含循环。 第一个和最后一个顶点是同一路径。 因此，我们必须追踪访问的顶点。 实现BFS时使用队列数据结构。
图2显示了示例图表中BFS遍历的动画。 请注意顶点是如何被发现(黄色)并访问的。
应用
用于确定最短路径和最小生成树。 用于由搜索引擎爬虫索引网页。 用于在社交网络上搜索。 用于查找对等网络(如BitTorrent )中可用的相邻节点。 深度优先搜索(Depth-first search ) ) ) ) ) ) )。
深度优先搜索(DFS )从特定顶点开始，在反向跟踪(back tracking )之前沿每个分支尽可能地进行搜索。 DFS还需要跟踪访问过的顶点。 实现DFS时，使用堆栈数据结构支持回溯。
图3是示出对图2中使用的相同样本图进行DFS扫描的动态图像的图。 注意它是如何到达深度和回溯的。
应用
用于查找两个顶点之间的路径。 用于检测图的循环。 用于拓扑排序。 解决迷宫般只有一个解的谜题的最短路径
从一个顶点到另一个顶点的最短路径是图中应该移动的边的权重总和最小的路径。
图4显示了确定从图的顶点1到顶点6的最短路径的动画。
算法
Dijkstra的最短路径算法、bellman算法
应用
在谷歌地图和苹果地图等地图软件中，用于寻找从一个地方到另一个地方的路线。
用于解决网络中的最小延迟路径问题。
在抽象机器中，达到特定目标状态的选择可由不同状态之间的转换确定(例如，可以用来确定赢得比赛的最小可能行走方式)。
循环检测周期检测
循环是图的第一个顶点和最后一个顶点相同的路径。 从顶点出发，沿着路径，最后到达起点，这个路径就是循环。 循环检查是检测这些循环的过程。 图5显示了遍历循环的动画。
算法
Floyd周期检测算法、xhdfn算法
应用
基于消息的分布式算法。 用于通过集群上的分布式处理系统处理大型图形。 用于检测并发系统中的死锁。 在加密APP序列中，用于确定可以将消息映射到相同加密值的消息的密钥。 最小生成树
最小生成树是图表边的子集，连接所有边权重的最小值和最小值顶点，不包括循环。
图6是显示获取最小生成树的过程的动画。
算法
Prim算法、Kruskal算法
应用
用于在计算机网络中构建广播树。 用于基于图的聚类分析。 用于分割图像。 用于社会地理区域分区，将区域划分为相邻区域。 强连通分量)。
如果图中的各顶点能从其他各顶点到达，则该图紧密相连。
图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翻译组