您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

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

时间:2020-09-02 10:14:40  来源:  作者:

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

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

 

 

在这篇文章中,我将简要地解释10个对分析和应用非常有用的基本图形算法。

首先,让我们介绍图。

什么是图?

图由一组有限的顶点或节点和一组连接这些顶点的边组成。如果两个顶点通过同一条边互相连接,则称它们为邻接。

下面给出了一些与图相关的基本定义。您可以参考图1中的示例。

  1. 阶Order:图中顶点的数量
  2. 边数Size:图中的边数
  3. 顶点度Vertex degree:与一个顶点关联的边的数量
  4. 孤立顶点Isolated vertex:图中与其他顶点没有连接的顶点
  5. 自循环Self-loop:从顶点到自身的一条边
  6. 有向图Directed graph:所有的边都有一个方向来表示起始点和结束点的图
  7. 无向图Undirected graph:具有没有方向的边的图
  8. 有权图Weighted graph:图的边具有权值
  9. 无权图Unweighted graph:图的边没有权值
10种图算法直观可视化解释

 

 

广度优先搜索(Breadth-first search)

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

 

 

遍历或搜索是可在图上执行的基本操作之一。在广度优先搜索(BFS)中,我们从一个特定的顶点开始,在进入下一层的顶点之前探索它当前深度的所有邻居。与树不同,图可以包含循环(第一个和最后一个顶点是相同的路径)。因此,我们必须跟踪访问过的顶点。在实现BFS时,我们使用队列数据结构。

图2表示一个示例图的BFS遍历的动画。注意顶点是如何被发现(黄色)和被访问(红色)的。

应用

· 用于确定最短路径和最小生成树。

· 被搜索引擎爬虫用来建立网页的索引。

· 用来在社交网络上搜索。

· 用于查找可用的邻接节点在对等网络,如BitTorrent。

深度优先搜索 (Depth-first search)

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

 

 

在深度优先搜索(DFS)中,我们从一个特定的顶点开始,在回溯(backtracking)之前沿着每个分支尽可能地搜索。在DFS中,我们还需要跟踪访问过的顶点。在实现DFS时,我们使用堆栈数据结构来支持回溯。

图3表示对图2中使用的同一个示例图进行DFS遍历的动画。注意它是如何遍历到深度和回溯的。

应用

· 用于查找两个顶点之间的路径。

· 用于检测图中的循环。

· 用于拓扑排序。

· 用于解决只有一个解的谜题(如迷宫)

最短路径

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

 

 

从一个顶点到另一个顶点的最短路径是图中应该移动的边的权值总和最小的路径。

图4显示了一个动画,其中确定了图中顶点1到顶点6的最短路径。

算法

Dijkstra的最短路径算法 、bellman算法

应用

用于在谷歌maps或Apple maps等地图软件中查找从一个地方到另一个地方的路线。

用于网络中解决最小时延路径问题。

在抽象机器中,通过不同状态之间的转换来确定达到某一目标状态的选择(例如,可以用来确定赢得一场比赛的最小可能的走法数)。

循环检测 Cycle Detection

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

 

 

循环是图中第一个顶点和最后一个顶点相同的路径。如果我们从一个顶点出发,沿着一条路径,最后到达起始点,那么这条路径就是一个循环。循环检测是检测这些循环的过程。图5显示了遍历一个循环的动画。

算法

Floyd周期检测算法、布伦特算法

应用

· 用于基于消息的分布式算法。

· 用于使用集群上的分布式处理系统处理大规模图形。

· 用于检测并发系统中的死锁。

· 在加密应用程序中用于确定可以将消息映射到相同加密值的消息的密钥。

最小生成树

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

 

 

最小生成树是图的边的子集,它连接所有边权值最小和的顶点,不包含任何循环。

图6是一个显示获得最小生成树的过程的动画。

算法

Prim算法、Kruskal算法

应用

· 用于在计算机网络中构建广播树。

· 用于基于图的聚类分析。

· 用于图像分割。

· 用于社会地理区域的区域化,将区域划分为相邻区域。

强连通分量(strongly connected components)

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

 

 

如果图中的每个顶点都能从其他每个顶点到达,那么这个图就是强连通的。

图7显示了一个示例图,其中包含三个强连接的组件,顶点用红色、绿色和黄色表示。

算法

Kosaraju的算法、Tarjan的强连通分量算法

应用

· 用于计算Dulmage-Mendelsohn分解,它是完全二分图的一种分类。

· 在社交网络中,用来寻找一群关系密切的人,并根据共同的兴趣提出建议。

拓扑排序

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

 

 

图的拓扑排序是对它的顶点进行线性排序,因此对于排序中的每条有向边(u, v),顶点u都在v之前。

图8显示了顶点(1、2、3、5、4、6、7、8)的拓扑排序示例。可以看到顶点5应该在顶点2和3之后。类似地,顶点6应该在顶点4和5之后。

算法

Kahn算法基于深度优先搜索的算法

应用

· 用于指令调度。

· 用于数据序列化。

· 用于确定在makefile中执行的编译任务的顺序。

· 用于解析链接器中的符号依赖关系。

图着色

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

 

 

图着色在保证一定条件下给图的元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中,我们尝试用k种颜色给图的顶点着色,任何两个相邻的顶点都不应该有相同的颜色。其他着色技术包括边缘着色和脸部着色。

图的色数是为图着色所需的颜色的最小数目。

图9显示了使用4种颜色的示例图的顶点着色。

算法

使用广度优先搜索或深度优先搜索的算法、贪婪着色

应用

· 用于制定时间表。

· 用于分配移动无线电频率。

· 用于模拟和解决游戏,如数独。

· 用于检查图是否是二分图。

· 用于在相邻国家或州的地理地图上涂上不同颜色。

最大流(Maximum Flow)

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

 

 

我们可以将一个图建模为一个以边权值作为流量容量的流网络。在最大流量问题中,我们必须找到一个能获得最大可能流量的流动路径。

图10显示了一个确定网络的最大流量和最终流量值的动画示例。

算法

Ford-Fulkerson算法、Edmonds-Karp算法、Dinic的算法

应用

· 用于航空公司调度,安排航班机组人员。

· 用于图像分割,在图像中找到背景和前景。

· 用来淘汰那些不能赢得足够的比赛来赶上当前分区的球队。

匹配

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

 

 

图中的匹配是指一组没有共同顶点的边(也就是说,没有两条边共享一个共同顶点)。如果一个匹配包含尽可能多的顶点匹配的边的最大数量,那么这个匹配被称为最大匹配。

图11显示了获得一个二分图的完全匹配的动画,该二分图有两组顶点,分别用橙色和蓝色表示。

算法

Hopcroft-Karp算法、匈牙利算法、Blossom 算法

应用

· 用于为新娘和新郎牵线搭桥(婚姻的稳定问题)。

· 用于确定顶点覆盖。

· 用于交通理论中解决出行资源配置和优化问题。

最后

我希望这篇文章对图形算法的简单概括介绍对您有所帮助

作者:Vijini Mallawaarachchi

deephub翻译组



Tags:图算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
图已经成为一种强大的建模和捕获真实场景中的数据的手段,比如社交媒体网络、网页和链接,以及GPS中的位置和路线。如果您有一组相互关联的对象,那么您可以使用图来表示它们。...【详细内容】
2020-09-02  Tags: 图算法  点击:(103)  评论:(0)  加入收藏
作为数据科学家,我们对pandas、SQL或任何其他关系数据库非常熟悉。...【详细内容】
2019-12-31  Tags: 图算法  点击:(32)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条