图论常用算法

DFS的应用

      1. 求无向图的连通分量

           求无向图的割点和桥

      2. 求无向图的双连通分量

      3. 求有向图的强连通分量

      4. 拓扑排序

      5. 二分图判断

    最小生成树

      最小生成树

    最短路径

        单源最短路

            Dijkstra算法

                    最短路径·一

            Bellman-Ford算法（SPFA算法）

                    最短路径·三：SPFA算法

        任意两点间的最短路

            Floyd算法(佛洛依德算法)

                 最短路径·二：Floyd算法

    拓扑排序

    二分图

二分图二•二分图最大匹配之匈牙利算法
相关定理

网络流问题

     最大流

        网络流一·Ford-Fulkerson算法
        网络流二.网络流二·最大流最小割定理

    最小费用流

        最小费用流

例题

1. Calling Circles UVA – 247 floyd 求传递闭包 参考代码

2. Audiophobia UVA – 10048
   floyd 求路上最大值 $d[i][j] = min(d[i][j],max(d[i][k],d[k][j]));$ 参考代码

3. It’s not a Bug, it’s a Feature! UVA – 658
   最短路，状态压缩，边是隐形边需要在求最短路的时候求边
   Code

4. 4.

今天的文章图论常用算法分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。