首页 > 代码库 > 图算法初步总结

图算法初步总结

主要是对图算法做一总结.

  1. 最基本的图算法思想是dfs和bfs,dfs组要是用于考察图的结构时使用而bfs一般用于求解无权最短路径问题.

  2. 拓扑排序依赖于dfs算法,拓扑排序可以解决事件依赖关系,强连通分支问题以及单源最短路径问题.

  3. 欧拉回路可以使用dfs解决.

  4. 汉密尔顿回路的存在性可以用拓扑排序解决.

  5. 强连通分支问题的解法可以使用拓扑排序的解法,也能使用tarjan,两者都会用到dfs.

  6. 最小生成树问题可以使用kruskal或者prim来解决.

  7. 单源最短路径问题可以使用Bellman-ford或者dijkstra来解决,但dijkstra不能解决负权环问题,两者都依赖于路径路径松弛技术.无环路图可以使用拓扑排序对Bellman-ford解法提速.

  8. 单源最短路径问题也可以扩展来解决差分式约束系统.

  9. 多源最短路径可以使用矩阵乘法或者Floyd-warshell来解决,两者都是动态规划解法.

  10. 闭包传递问题的思想是如果只考虑是否可到,那么就可以将路径是否可达用0,1表示,通过与或运算来进行路径的递推。本的解法还是依赖于前面的算法.

  11. 此外,对于不同场景使用回溯来减少路径搜索很重要.


图算法初步总结