10种基本图算法的快速介绍，包括示例和可视化图已经成为现实世界中的一个强大结构，例如社交媒体网络、网页和链接，以及GPS中的位置和路线建模和捕获数据。如果您有一组相互关联的对象，则可以使用图形来表示它们。>ImagebyAuthor在本文中，我将简要介绍10种对分析及其应用有用的基本图形算法。首先介绍一张图。什么是图表？图由一组有限的顶点或节点和一组连接这些顶点的边组成。如果两个顶点由同一条边相互连接，则它们称为相邻顶点。下面给出了与图形相关的一些基本定义。您可以参考图1的示例。order：图中的顶点数size：图中的边数vertexdegree：入射到一个顶点的边数isolatedvertex：一个顶点没有连接到图中的任何其他顶点自循环：从一个顶点到自身有向图：所有边都有一个方向指示起始顶点和结束顶点的图形>图1.图术语的可视化（作者图片）1。广度优先搜索>图2.图的BFS遍历动画（作者图片）遍历或搜索是可以在图上执行的基本操作之一。在广度优先搜索(BFS)中，我们从一个特定的顶点开始，在继续到下一级顶点之前探索其当前深度的所有邻居。与树不同，图可以包含循环（具有相同的第一个和最后一个顶点的路径）。因此，我们必须跟踪访问过的顶点。在实现BFS时，我们使用队列数据结构。图2表示示例图的BFS遍历动画。请注意如何发现顶点（黄色）和访问顶点（红色）。应用领域用于确定最短路径和最小生成树。搜索引擎爬虫用于构建网页索引。用于在社交网络上搜索。用于在对等网络（例如BitTorrent）中查找可用的邻居节点。2.深度优先搜索>图3.图的DFS遍历动画（作者图片）在深度优先搜索(DFS)中，我们从一个特定的顶点开始，在回溯之前沿着每个分支尽可能远地走（回溯).可能的探索。在DFS中，我们还必须跟踪访问过的顶点。在实现DFS时，我们使用栈数据结构来支持回溯。如图。图3表示与图2中相同的示例图的DFS遍历的动画。2.注意它是如何遍历深度和回溯的。应用领域用于寻找两个顶点之间的路径。用于检测图中的循环。用于拓扑排序。解决只有一个解决方案的谜题（例如迷宫）3.最短路径>图4.显示从顶点1到顶点6??的最短路径的动画（作者图片）从一个顶点到另一个顶点的最短路径是图中的一条路径，因此应移动的边的权重之和最小。图4显示了确定图中从顶点1到顶点6??的最短路径的动画。算法Dijkstra的最短路径算法Bellman–Ford算法用于在GoogleMaps或AppleMaps等地图软件中查找从一个位置到另一个位置的路线。在网络中用于解决最小延迟路径问题。在抽象机器中用于通过在不同状态之间转换来确定达到某个目标状态的选项（例如，用于确定赢得游戏的最小可能次数）。>图片来自Pixabay的DanielDino-Slofer4.循环检测>图5.循环（作者图片）循环是图中第一个顶点和最后一个顶点相同的路径。如果我们从一个顶点开始，遵循一条路径，并在起始顶点结束，则该路径是一个循环。环路检测就是检测这些环路的过程。图5显示了遍历循环的动画。算法弗洛伊德循环检测算法布伦特算法应用领域用于基于分布式消息的算法。用于在集群上使用分布式处理系统处理大规模图形。用于检测并发系统中的死锁。在加密应用程序中用于确定将消息映射到相同加密值的消息的密钥。5.Minimumspanningtree>图6.显示最小生成树的动画（作者图片）最小生成树是图的边的子集，它连接具有最小边权重和的所有顶点并且不包含循环。图6是一个动画，展示了获得最小生成树的过程。算法Prim算法Kruskal算法应用领域用于构建计算机网络中的广播树。用于基于图形的聚类分析。用于图像分割。用于将社会区域划分为连续区域的社会地理区域区域化。6.Stronglyconnectedcomponents>图7.Stronglyconnectedcomponents(ImagebyAuthor)如果图中的每个顶点都可以从其他每个顶点到达，则称该图是强连通的。图7显示了一个示例图，其中包含三个强连通分量，顶点分别为红色、绿色和黄色。算法Kosaraju算法Tarjan强连通分量算法应用领域用于计算Dulmage–Mendelsohn分解，这是二分图中边的分类。在社交网络中用于寻找一群关系密切的人，他们根据共同的兴趣提出建议。>图片来自Pixabay的GerdAltmann。拓扑排序>图8.图中顶点的拓扑排序（作者图片）图的拓扑排序是其顶点的线性排序，因此对于每个有向边(u,v)，顶点u位于之前v.图8显示了顶点的拓扑顺序(1,2,3,5,4,6,7,8)的示例。可以看到顶点5应该在顶点2和3之后。同样，顶点6应该在顶点4和5之后。AlgorithmKahn'sAlgorithmDepth-firstsearch-basedalgorithmapplicationfield用于指令调度。用于数据序列化。用于确定在makefile中执行编译任务的顺序。用于解决链接器中的符号依赖关系。8.Graphiccoloring>Fig9.Vertexcoloring(ImagebyAuthor)图形着色在保证一定条件的情况下，为图形元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中，我们尝试用k种颜色为图的顶点着色，并且任何两个相邻顶点都不应具有相同的颜色。其他着色技术包括边缘着色和面部着色。图的色数是为图着色所需的最少颜色数。图9显示了使用4种颜色的示例图的顶点着色。算法使用广度优先搜索或深度优先搜索的算法贪心着色应用领域用于调度。用于分配移动无线电频率。用于建模和解决数独难题。用于检查图是否是二分图。可用于为具有不同颜色的相邻国家或地区的国家或州的地理地图着色。>图片来自Pixabay的TheAndrasBarta。最大流>图10.确定最大流（作者图片）我们可以将图建模为流网络，边权重作为流。在最大流量问题中，我们必须找到一条能获得最大可能流量的流路。图10给出了确定网络最大流量和确定最终流量值的动画示例。算法Ford-FoxenAlgorithmEdmonds–KarpAlgorithmDinic'sAlgorithm应用领域航空公司调度中用于调度航班人员。用于图像分割以查找图像中的背景和前景。用于淘汰无法赢得足够比赛以赶上其部门领导者的棒球队。10.匹配>图11.二部图的匹配（作者图片）图中的匹配项是一组没有公共顶点的边（即，没有两条边共享一个公共顶点）。如果匹配包含尽可能多的边并匹配尽可能多的顶点，则该匹配称为最大匹配。图11显示了获得二部图与橙色和蓝色指示的两组顶点的精确匹配的动画。算法Hopcroft-KarpAlgorithmHungarianAlgorithmBlossomAlgorithm应用领域用于婚介匹配新娘和新郎（稳定婚姻问题）。用于确定顶点覆盖。在交通理论中用于解决资源分配和出行优化问题。最后的想法我希望您发现这篇文章对图算法的简单和一般介绍很有用。我很想听听你的想法。非常感谢您的阅读。
