图形已经成为在真实场景中建模和捕捉数据的强大手段，例如社交媒体网络、网页和链接，以及全球定位系统中的位置和路线。如果你有一组相互关联的对象，你可以用图来表示它们。
在本文中，我将简要解释10个基本的图形算法，这些算法对分析和应用非常有用。
首先，我们来介绍一下图表。
什么是图表？
图由一组有限的顶点或节点以及一组连接这些顶点的边组成。如果两个顶点通过同一条边相互连接，它们被称为邻接。
下面给出了一些与图形相关的基本定义。您可以参考图1中的例子。
顺序:图中顶点的数量
尺寸:图形中的边数
顶点度数:与一个顶点相关的边的数量
孤立顶点:图中不与其他顶点相连的顶点
自循环:从顶点到自身的边
有向图:所有边都有方向来表示起点和终点的图
无向图:边没有方向的图
加权图形:图形的边有权重
未加权图:图的边没有权重
广度优先搜索
遍历或搜索是可以在图上执行的基本操作之一。在广度优先搜索中，我们从一个特定的顶点开始，并在进入下一个顶点之前探索其当前深度的所有邻居。与树不同，图可以包含循环。因此，我们必须跟踪访问过的顶点。当实现BFS时，我们使用队列数据结构。
图2示出了示例图的BFS遍历的动画。请注意顶点是如何被发现和访问的。
app应用
用于确定最短路径和最小生成树。
被搜索引擎爬虫用来建立网页索引。
用来在社交网络上搜索。
用于查找对等网络中可用的相邻节点，如BitTorrent。
深度优先搜索
在深度优先搜索中，我们从一个特定的顶点开始，在回溯之前尽可能沿着每个分支进行搜索。在DFS中，我们还需要跟踪访问过的顶点。在实现DFS时，我们使用堆栈数据结构来支持回溯。
图3示出了图2中使用的相同示例图的DFS遍历的动画。请注意它如何遍历到深度和回溯。
app应用
用于查找两个顶点之间的路径。
用于检测图形中的循环。
用于拓扑排序。
用来解决只有一个答案的难题
最短路径
从一个顶点到另一个顶点的最短路径是图中应该移动的边的权重之和最小的路径。
图4示出了确定从顶点1到顶点6的最短路径的动画。
算法
迪克斯特拉最短路径算法和贝尔曼算法
app应用
用于在谷歌地图或苹果地图等地图软件中查找从一个地方到另一个地方的路线。
用于解决网络中最小时延路径的问题。
在抽象机器中，实现某个目标状态的选择由不同状态之间的转换决定。
循环检测循环检测
循环是图中第一个顶点和最后一个顶点相同的路径。如果我们从一个顶点开始，沿着一条路径，最后到达起点，那么这条路径就是一个循环。循环检测是检测这些循环的过程。图5显示了一个遍历循环的动画。
算法
弗洛伊德循环检测算法、布伦特算法
app应用
用于基于消息的分布式算法。
用于使用集群上的分布式处理系统处理大规模图形。
用于检测并发系统中的死锁。
在加密应用程序中，它用于确定可以将消息映射到具有相同加密值的消息的密钥。
最小生成树
最小生成树是图的边的子集，它连接所有边的最小和的顶点，不包含任何圈。
图6是示出获得最小生成树的过程的动画。
算法
Prim算法，Kruskal算法
app应用
用于在计算机网络中建立广播树。
用于基于图的聚类分析。
用于图像分割。
它用于社会地理区域的区域化，将区域划分为相邻的区域。
强连接组件
如果一个图中的每个顶点都可以从其他顶点到达，那么这个图就是强连通的。
图7显示了一个示例图，它包含三个强连接的组件，顶点由红色、绿色和黄色表示。
算法
Kosaraju算法，Tarjan强连通分支算法
app应用
用于计算完全二部图的分类——Dulmage-Mendelsohn分解。
在社交网络中，用来寻找一群关系密切的人，根据他们的共同兴趣提出建议。
拓扑排序
图的拓扑排序是对其顶点进行线性排序，所以对于排序中的每一条有向边，顶点u都在v之前。
图8显示了一个顶点拓扑排序的例子。可以看出，顶点5应该在顶点2和3之后。类似地，顶点6应该在顶点4和5之后。
算法
卡恩算法基于深度优先搜索
app应用
用于指令调度。
用于数据序列化。
用于确定在makefile中执行的编译任务的顺序。
用于解决链接器中的符号依赖关系。
图形着色
图着色在一定条件下给图的元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中，我们试图用k种颜色给图的顶点着色，任何两个相邻的顶点不应该有相同的颜色。其他着色技术包括边缘着色和面部着色。
图形的颜色数是给图形着色所需的最小颜色数。
图9示出了使用四种颜色的示例图的顶点着色。
算法
使用广度优先搜索或深度优先搜索算法，贪婪着色
app应用
用来制定时间表。
用于分配移动无线电频率。
用于模拟和解决游戏，如数独。
用于检查图是否是二分图。
用于在邻近国家或州的地理地图上绘制不同的颜色。
最大流量
我们可以将一个图建模为一个流量网络，边权重作为流量容量。在最大流量的问题中，我们必须找到一条能够获得最大可能流量的流路。
图10示出了确定网络的最大和最终流量值的动画示例。
算法
福特-富尔克森算法、埃德蒙兹-卡普算法、迪尼奇算法
app应用
用于飞行空公司调度和飞行机组安排。
用于图像分割，以找到图像中的背景和前景。
用于淘汰无法赢得足够比赛来追赶当前赛区的球队。
相称的
图中的匹配是指没有公共顶点的一组边。如果匹配包含尽可能多顶点的最大边数，则该匹配称为最大匹配。
图11示出了获得二分图的完美匹配的动画，该二分图具有两组顶点，分别由橙色和蓝色表示。
算法
霍普克罗夫特-卡普算法，匈牙利算法，布鲁姆算法
app应用
用来搭配新郎新娘。
用于确定顶点覆盖。
用于交通运输理论，解决出行资源配置和优化问题。
最后的
希望本文对图形算法的简要概述能对你有所帮助。
Deephub翻译组
