首页 文章 精选 留言 我的

精选列表

搜索[代码可视化],共10000篇文章
优秀的个人博客,低调大师

每日一博 | 10 种常用的图算法直观可视化解释

图已经成为一种强大的建模和捕获真实场景中的数据的手段,比如社交媒体网络、网页和链接,以及GPS中的位置和路线。如果您有一组相互关联的对象,那么您可以使用图来表示它们。 在这篇文章中,我将简要地解释10个对分析和应用非常有用的基本图形算法。 首先,让我们介绍图。 什么是图? 图由一组有限的顶点或节点和一组连接这些顶点的边组成。如果两个顶点通过同一条边互相连接,则称它们为邻接。 下面给出了一些与图相关的基本定义。您可以参考图1中的示例。 Order:图中顶点的数量 Size:图中的边数 Vertex degree:与一个顶点关联的边的数量 Isolated vertex:图中与其他顶点没有连接的顶点 Self-loop:从顶点到自身的一条边 Directed graph:所有的边都有一个方向来表示起始点和结束点的图 Undirected graph:具有没有方向的边的图 Weighted grap:图的边具有权值 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周期检测算法、布伦特算法 应用 用于基于消息的分布式算法。 用于使用集群上的分布式处理系统处理大规模图形。 用于检测并发系统中的死锁。 在加密应用程序中用于确定可以将消息映射到相同加密值的消息的密钥。 最小生成树 最小生成树是图的边的子集,它连接所有边权值最小和的顶点,不包含任何循环。 图6是一个显示获得最小生成树的过程的动画。 算法 Prim算法、Kruskal算法 应用 用于在计算机网络中构建广播树。 用于基于图的聚类分析。 用于图像分割。 用于社会地理区域的区域化,将区域划分为相邻区域。 强连通分量(strongly connected components) 如果图中的每个顶点都能从其他每个顶点到达,那么这个图就是强连通的。 图7显示了一个示例图,其中包含三个强连接的组件,顶点用红色、绿色和黄色表示。 算法 Kosaraju的算法、Tarjan的强连通分量算法 应用 用于计算Dulmage-Mendelsohn分解,它是完全二分图的一种分类。 在社交网络中,用来寻找一群关系密切的人,并根据共同的兴趣提出建议。 拓扑排序 图的拓扑排序是对它的顶点进行线性排序,因此对于排序中的每条有向边(u, v),顶点u都在v之前。 图8显示了顶点(1、2、3、5、4、6、7、8)的拓扑排序示例。可以看到顶点5应该在顶点2和3之后。类似地,顶点6应该在顶点4和5之后。 算法 Kahn算法基于深度优先搜索的算法 应用 用于指令调度。 用于数据序列化。 用于确定在makefile中执行的编译任务的顺序。 用于解析链接器中的符号依赖关系。 图着色 图着色在保证一定条件下给图的元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中,我们尝试用k种颜色给图的顶点着色,任何两个相邻的顶点都不应该有相同的颜色。其他着色技术包括边缘着色和脸部着色。 图的色数是为图着色所需的颜色的最小数目。 图9显示了使用4种颜色的示例图的顶点着色。 算法 使用广度优先搜索或深度优先搜索的算法、贪婪着色 应用 用于制定时间表。 用于分配移动无线电频率。 用于模拟和解决游戏,如数独。 用于检查图是否是二分图。 用于在相邻国家或州的地理地图上涂上不同颜色。 最大流(Maximum Flow) 我们可以将一个图建模为一个以边权值作为流量容量的流网络。在最大流量问题中,我们必须找到一个能获得最大可能流量的流动路径。 图10显示了一个确定网络的最大流量和最终流量值的动画示例。 算法 Ford-Fulkerson算法、Edmonds-Karp算法、Dinic的算法 应用 用于航空公司调度,安排航班机组人员。 用于图像分割,在图像中找到背景和前景。 用来淘汰那些不能赢得足够的比赛来赶上当前分区的球队。 匹配 图中的匹配是指一组没有共同顶点的边(也就是说,没有两条边共享一个共同顶点)。如果一个匹配包含尽可能多的顶点匹配的边的最大数量,那么这个匹配被称为最大匹配。 图11显示了获得一个二分图的完全匹配的动画,该二分图有两组顶点,分别用橙色和蓝色表示。 算法 Hopcroft-Karp算法、匈牙利算法、Blossom 算法 应用 用于为新娘和新郎牵线搭桥(婚姻的稳定问题)。 用于确定顶点覆盖。 用于交通理论中解决出行资源配置和优化问题。 最后 我希望这篇文章对图形算法的简单概括介绍对您有所帮助 作者:Vijini Mallawaarachchi deephub翻译组 本文分享自微信公众号 - DeepHub IMBA(deephub-imba)。如有侵权,请联系 support@oschina.cn 删除。本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

资源下载

更多资源
Mario

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长,特征是大鼻子、头戴帽子、身穿背带裤,还留着胡子。与他的双胞胎兄弟路易基一起,长年担任任天堂的招牌角色。

腾讯云软件源

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题,腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构,目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring

Spring框架(Spring Framework)是由Rod Johnson于2002年提出的开源Java企业级应用框架,旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念,提供核心容器、应用上下文、数据访问集成等模块,支持整合Hibernate、Struts等第三方框架,其适用范围不仅限于服务器端开发,绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux

Rocky Linux(中文名:洛基)是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版,作为CentOS稳定版停止维护后与RHEL(Red Hat Enterprise Linux)完全兼容的开源替代方案,由社区拥有并管理,支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性,采用模块化包装和SELinux安全架构,默认包含GNOME桌面环境及XFS文件系统,支持十年生命周期更新。

用户登录
用户注册