10种图算法直观可视化解释 _图算法

图已经成为一种强大的建模和捕获真实场景中的数据的手段，比如社交媒体网络、网页和链接，以及GPS中的位置和路线。如果您有一组相互关联的对象，那么您可以使用图来表示它们。

文章插图

在这篇文章中，我将简要地解释10个对分析和应用非常有用的基本图形算法。
首先，让我们介绍图。
什么是图?图由一组有限的顶点或节点和一组连接这些顶点的边组成。如果两个顶点通过同一条边互相连接，则称它们为邻接。
下面给出了一些与图相关的基本定义。您可以参考图1中的示例。

阶Order:图中顶点的数量
边数Size:图中的边数
顶点度Vertex degree:与一个顶点关联的边的数量
孤立顶点Isolated vertex:图中与其他顶点没有连接的顶点
自循环Self-loop:从顶点到自身的一条边
有向图Directed graph:所有的边都有一个方向来表示起始点和结束点的图
无向图Undirected graph:具有没有方向的边的图
有权图Weighted graph:图的边具有权值
无权图Unweighted graph:图的边没有权值

文章插图

广度优先搜索（Breadth-first search）

文章插图

遍历或搜索是可在图上执行的基本操作之一。在广度优先搜索(BFS)中，我们从一个特定的顶点开始，在进入下一层的顶点之前探索它当前深度的所有邻居。与树不同，图可以包含循环(第一个和最后一个顶点是相同的路径) 。因此，我们必须跟踪访问过的顶点。在实现BFS时，我们使用队列数据结构。
图2表示一个示例图的BFS遍历的动画。注意顶点是如何被发现(黄色)和被访问(红色)的。
应用
· 用于确定最短路径和最小生成树。
· 被搜索引擎爬虫用来建立网页的索引。
· 用来在社交网络上搜索。
· 用于查找可用的邻接节点在对等网络，如BitTorrent 。
深度优先搜索（Depth-first search）

文章插图

在深度优先搜索(DFS)中，我们从一个特定的顶点开始，在回溯(backtracking)之前沿着每个分支尽可能地搜索。在DFS中，我们还需要跟踪访问过的顶点。在实现DFS时，我们使用堆栈数据结构来支持回溯。
图3表示对图2中使用的同一个示例图进行DFS遍历的动画。注意它是如何遍历到深度和回溯的。
应用
· 用于查找两个顶点之间的路径。
· 用于检测图中的循环。
· 用于拓扑排序。
· 用于解决只有一个解的谜题(如迷宫)
最短路径

文章插图

从一个顶点到另一个顶点的最短路径是图中应该移动的边的权值总和最小的路径。
图4显示了一个动画，其中确定了图中顶点1到顶点6的最短路径。
算法
Dijkstra的最短路径算法、bellman算法
应用
用于在谷歌maps或Apple maps等地图软件中查找从一个地方到另一个地方的路线。
用于网络中解决最小时延路径问题。
在抽象机器中，通过不同状态之间的转换来确定达到某一目标状态的选择(例如，可以用来确定赢得一场比赛的最小可能的走法数) 。
循环检测 Cycle Detection

文章插图

循环是图中第一个顶点和最后一个顶点相同的路径。如果我们从一个顶点出发，沿着一条路径，最后到达起始点，那么这条路径就是一个循环。循环检测是检测这些循环的过程。图5显示了遍历一个循环的动画。
算法
Floyd周期检测算法、布伦特算法
应用
· 用于基于消息的分布式算法。
· 用于使用集群上的分布式处理系统处理大规模图形。
· 用于检测并发系统中的死锁。
【10种图算法直观可视化解释】· 在加密应用程序中用于确定可以将消息映射到相同加密值的消息的密钥。