十个基础图论算法介绍 - Franc0

21-12-03 banq

10个基本的图算法:

bfs广度优先搜索:

这是一种遍历算法。它从给定的顶点开始,并在移动到下一层的顶点之前探索当前级别的所有邻居。它是使用队列数据结构实现的。

用途:

  • 确定未加权图中的最短路径和最小生成树
  • 构建网页索引
  • 在社交网络上搜索
  •  在对等网络中找到可用的邻居节点

 

dfs深度优先搜索:

这是一种遍历算法。它从给定的顶点开始,并在回溯之前沿着每个分支尽可能地探索。它是使用堆栈数据结构实现的。

用途:

  • 找到 2 个顶点之间的路径
  • 检测图中的循环 
  • 拓扑排序
  • 解决迷宫难题

 

最短路径:

在 2 个给定顶点之间找到一条路径,使得应该经过的边的权重之和最小。有两种主要算法:

  1. Dijkstra
  2. Bellman–Ford

用途:

  • 在地图软件中查找从一个位置到另一位置的行进方向
  • 解决网络中的最小延迟路径问题
  • 通过不同状态之间的转换确定到达目标状态的选择

 

循环检测:

检测是否存在首尾顶点相同的路径。有两种主要算法:

  1. 弗洛伊德循环检测
  2. 布伦特

用途:

  • 基于分布式消息的算法 
  • 检测并发系统中的死锁 
  • 在分布式集群上处理大规模图 
  • 确定可以将消息映射到相同加密值的键。

 

最小生成树:

找到连接所有顶点的边的子集,没有循环的权重总和最小。有两种主要算法:

  1. Prim
  2. Kruskal

用途:

  • 图像注册
  • 避免网络循环的协议
  • 基于图形的数据集群的分析

 

 强连接部件

寻找顶点的子集,其中每个顶点都可以从其他每个顶点到达。

有2种主要算法:

  1. Kosaraju
  2. Tarjan

用途:

  • 对二元图的边进行分类
  • 形式验证中的模型检查。
  • 在社交网络中找到强联系的人群,并根据共同兴趣进行推荐

  

拓扑排序 

找到一个DAG中顶点的线性排序,使排序中的每条有向边(x,y),顶点x都在y之前。

有2种主要算法。

  1. Kahn
  2. 深度优先搜索

用途:

  • 指令调度
  • 数据序列化
  • 确定编译任务的顺序
  • 解决链接器中的符号依赖问题

 

图形着色:

为顶点(或边)分配k种颜色,同时确保任何两个相邻的顶点(或边)不具有相同的颜色。

有2种主要算法。

  1. 广度优先搜索
  2. 深度优先搜索

用途:

  • 检查一个图是否是二方bipartite的
  • 着色日程安排时间表
  • 分配移动无线电频率
  • 给国家的地理地图着色

  

最大流动

一个图也可以被建模为一个流动网络,边的权重为流动能力。最大流动是指能够获得最大可能流量的流动路径。

有3种主要算法。

  1. 福特-福尔克森 
  2. 埃德蒙兹-卡普 
  3. Dinic

用途:

  • 流通需求问题
  • 航空公司的机组人员安排
  • 抛弃那些在剩下的比赛中无法到达当前领导者的团队
  • 图像分割以区分图像中的背景和前景

 

匹配 

寻找没有共同顶点的边的子集。

有3种主要算法:

  1.  Hopcroft-Karp
  2.  Hungarian
  3.  Blossom

用途:

  • 在两组人之间牵线搭桥
  • 资源分配问题
  • 旅行中的资源分配和优化

 

猜你喜欢