10个基本的图算法:
bfs广度优先搜索:
这是一种遍历算法。它从给定的顶点开始,并在移动到下一层的顶点之前探索当前级别的所有邻居。它是使用队列数据结构实现的。
用途:
- 确定未加权图中的最短路径和最小生成树
- 构建网页索引
- 在社交网络上搜索
- 在对等网络中找到可用的邻居节点
dfs深度优先搜索:
这是一种遍历算法。它从给定的顶点开始,并在回溯之前沿着每个分支尽可能地探索。它是使用堆栈数据结构实现的。
用途:
- 找到 2 个顶点之间的路径
- 检测图中的循环
- 拓扑排序
- 解决迷宫难题
最短路径:
在 2 个给定顶点之间找到一条路径,使得应该经过的边的权重之和最小。有两种主要算法:
- Dijkstra
- Bellman–Ford
用途:
- 在地图软件中查找从一个位置到另一位置的行进方向
- 解决网络中的最小延迟路径问题
- 通过不同状态之间的转换确定到达目标状态的选择
循环检测:
检测是否存在首尾顶点相同的路径。有两种主要算法:
- 弗洛伊德循环检测
- 布伦特
用途:
- 基于分布式消息的算法
- 检测并发系统中的死锁
- 在分布式集群上处理大规模图
- 确定可以将消息映射到相同加密值的键。
最小生成树:
找到连接所有顶点的边的子集,没有循环的权重总和最小。有两种主要算法:
- Prim
- Kruskal
用途:
- 图像注册
- 避免网络循环的协议
- 基于图形的数据集群的分析
强连接部件
寻找顶点的子集,其中每个顶点都可以从其他每个顶点到达。
有2种主要算法:
- Kosaraju
- Tarjan
用途:
- 对二元图的边进行分类
- 形式验证中的模型检查。
- 在社交网络中找到强联系的人群,并根据共同兴趣进行推荐
拓扑排序
找到一个DAG中顶点的线性排序,使排序中的每条有向边(x,y),顶点x都在y之前。
有2种主要算法。
- Kahn
- 深度优先搜索
用途:
- 指令调度
- 数据序列化
- 确定编译任务的顺序
- 解决链接器中的符号依赖问题
图形着色:
为顶点(或边)分配k种颜色,同时确保任何两个相邻的顶点(或边)不具有相同的颜色。
有2种主要算法。
- 广度优先搜索
- 深度优先搜索
用途:
- 检查一个图是否是二方bipartite的
- 着色日程安排时间表
- 分配移动无线电频率
- 给国家的地理地图着色
最大流动
一个图也可以被建模为一个流动网络,边的权重为流动能力。最大流动是指能够获得最大可能流量的流动路径。
有3种主要算法。
- 福特-福尔克森
- 埃德蒙兹-卡普
- Dinic
用途:
- 流通需求问题
- 航空公司的机组人员安排
- 抛弃那些在剩下的比赛中无法到达当前领导者的团队
- 图像分割以区分图像中的背景和前景
匹配
寻找没有共同顶点的边的子集。
有3种主要算法:
- Hopcroft-Karp
- Hungarian
- Blossom
用途:
- 在两组人之间牵线搭桥
- 资源分配问题
- 旅行中的资源分配和优化