首页 > 代码库 > 图算法初步总结
图算法初步总结
主要是对图算法做一总结.
最基本的图算法思想是dfs和bfs,dfs组要是用于考察图的结构时使用而bfs一般用于求解无权最短路径问题.
拓扑排序依赖于dfs算法,拓扑排序可以解决事件依赖关系,强连通分支问题以及单源最短路径问题.
欧拉回路可以使用dfs解决.
汉密尔顿回路的存在性可以用拓扑排序解决.
强连通分支问题的解法可以使用拓扑排序的解法,也能使用tarjan,两者都会用到dfs.
最小生成树问题可以使用kruskal或者prim来解决.
单源最短路径问题可以使用Bellman-ford或者dijkstra来解决,但dijkstra不能解决负权环问题,两者都依赖于路径路径松弛技术.无环路图可以使用拓扑排序对Bellman-ford解法提速.
单源最短路径问题也可以扩展来解决差分式约束系统.
多源最短路径可以使用矩阵乘法或者Floyd-warshell来解决,两者都是动态规划解法.
闭包传递问题的思想是如果只考虑是否可到,那么就可以将路径是否可达用0,1表示,通过与或运算来进行路径的递推。本的解法还是依赖于前面的算法.
- 此外,对于不同场景使用回溯来减少路径搜索很重要.
图算法初步总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。