图已经成为在现实生活场景中建模和捕获数据的强大手段，例如社交媒体网络、网页和链接、GPS中的位置和路线，其中一组对象是相关的，可以用图形表示。本文将简要介绍10种对分析和应用有很大帮助的基本图表算法。首先，什么是图形？图由一组有限的顶点或节点和一组连接这些顶点的边组成。如果两个顶点通过同一条边相互连接，则称为邻接。下面是一些与图表相关的基本定义，大家可以参考图中的例子。Order：图中顶点的数量Size：图中边的数量Vertexdegree：入射到该顶点的边的数量Orphanedvertex：没有连接到图中任何其他顶点的顶点Self-loop：一条边来自avertextoitself有向图：图中的所有边都有方向指示起点和终点无向图：图的边没有方向带权图：图的边有权值无权图：图的边没有权值图1：图形术语的可视化1.广度优先搜索图2：广度优先搜索(BFS)遍历动画遍历或搜索是对图执行的基本操作之一。在广度优先搜索（BFS）中，从一个特定的顶点开始，在进入下一层的顶点之前探索其当前深度的所有相关信息。与树不同，图可以包含循环（第一个和最后一个顶点是相同的路径）。因此，有必要跟踪访问过的顶点。在实现BFS时，应该使用队列数据结构。图2是示例图的BFS遍历动画，请注意如何发现（黄色）和访问（红色）顶点。应用：用于社交网络搜索用于确定最短路径和最小生成树用于搜索引擎爬虫建立网页索引用于在对等网络（如BitTorrent）中寻找可用的相邻节点2.深度优先search图3：深度优先搜索（DFS）的遍历动画在深度优先搜索（DFS）中，从一个特定的顶点开始，在回溯（backtracking）之前，尽可能沿着每个分支搜索。在DFS中，还需要跟踪访问过的顶点。在实现DFS时，使用栈数据结构来支持回溯。图3是图2中使用的同一示例图的DFS遍历动画，注意它如何遍历到深度和回溯。应用：寻找两个顶点之间的路径检测图中的环拓扑排序解决只有一个解决方案的谜题（例如迷宫）3.shortestpathsShortestpathtovertex6从一个顶点到另一个顶点的最短路径是图中的路径这样移动边缘的权重之和应该最小化。图4显示了确定图中从顶点1到顶点6??的最短路径的动画。算法：Dijkstra的最短路径算法贝尔曼福特（Bellman–Ford）算法应用：用于解决网络中的最小延迟路径问题。用于在Google或Apple地图等软件中查找从一个位置到另一个位置的路线。用于抽象机中，通过不同状态之间的转换来确定达到某个目标状态的方法。例如，它可用于确定如何以最少的步数赢得比赛。4.循环检测图5：循环循环是图中第一个顶点和最后一个顶点相同的路径。如果从一个顶点出发，沿着一条路走，最后到达起点，那么这条路就是一个圈。环路检测就是检测这些环路的过程。图5显示了遍历循环的动画。算法：弗洛伊德循环检测算法布伦特算法应用：用于基于消息的分布式算法用于在集群上使用分布式处理系统处理大规模图形用于检测并发系统中的死锁密码应用中5.最小生成树图6.显示最小生成树的动画最小生成树是连接所有边权重之和最小的顶点的图边的子集，不包含任何循环。图6是获取最小生成树过程的动画。算法：Pullin算法Kruskal算法应用：用于在计算机网络中构建广播树用于基于图的聚类分析用于图像分割。6.强连通分量图7：强连通分量如果图中的每个顶点都可以通过其他所有顶点到达，则该图是强连通的。图7包含三个强连通分量，顶点分别用红色、绿色和黄色表示。算法：KosarajuAlgorithmTarjanStronglyConnectedComponentAlgorithm应用：用于计算DulmageMendelsohn分解，它是二分图边的分类。在社交网络中用于根据共同爱好发现和推荐关系密切的人。7.拓扑排序图8：图中顶点的拓扑排序图的拓扑排序是对其顶点的线性排序，因此对于排序中的每条有向边（u，v），顶点u在v之前。图图8显示了顶点(1、2、3、5、4、6、7、8)的拓扑排序的示例。如您所见，顶点5应位于顶点2和3之后。同样，顶点6应位于顶点4和5之后。算法：Kahn算法基于深度优先算法应用：用于指令调度用于数据序列化用于确定编译任务在makefile中执行的顺序用于解决链接器中的符号依赖8.图着色图9：顶点着色图着色是指在特定条件下为图形的元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中，我们尝试用k种颜色为图的顶点着色，使得没有两个相邻顶点具有相同的颜色。其他着色技术包括边缘着色和面部着色。图的色数是为图着色所需的最少颜色数。图9显示顶点有4种颜色。算法：使用广度优先搜索或深度优先搜索的算法贪婪着色应用：用于制定时间表用于分配移动无线电频率用于建模和解决数独游戏用于检查图形是否为二分图国家或州的地图用不同的颜色着色9.最大流量图10：确定最大流量可以将图建模为流量网络，其中边权重作为流量。在最大流量问题中，有必要找到实现最高可能流量的流动路径。图10是确定网络的最大和最终流量值的动画示例。算法：Ford-Fulkerson算法Edmonds–Karp算法Dinic算法应用：用于航空公司调度和安排机组人员。对于图像分割，找到图像中的背景和前景。用于淘汰无法赢得比赛并匹配当前球队最佳球员的球员。10.MatchingGraph11:BipartiteGraphMatching图中的匹配是一组没有公共顶点（即没有两个公共顶点）的边。如果匹配包含与尽可能多的顶点匹配的最大边数，则该匹配称为最大匹配。图11显示了为具有两组顶点的二分图获得完美匹配的动画，分别用橙色和蓝色表示。算法：Hopcroft–KarpAlgorithmHungarianAlgorithmBlossomAlgorithm应用：用于匹配新娘和新郎（婚姻稳定问题）用于确定顶点覆盖率用于交通理论这10种基本图算法被广泛用于解决出行资源分配和优化问题.你明白了吗？本文转载自微信公众号“读书芯”，可通过以下二维码关注。转载本文请联系核心阅读公众号。
