图论常用算法

      版权声明：本文为博主原创文章，可随意转载 https://blog.csdn.net/weixin_38686780/article/details/77244247

• 图论常用算法
  • DFS的应用
    •       1. 求无向图的连通分量
      •            求无向图的割点和桥
    •       2. 求无向图的双连通分量
    •       3. 求有向图的强连通分量
    •       4. 拓扑排序
    •       5. 二分图判断
  •     最小生成树
  •     最短路径
    • •         单源最短路
        •             Dijkstra算法
      •             Bellman-Ford算法（SPFA算法）
    •         任意两点间的最短路
      •             Floyd算法(佛洛依德算法)
    •     拓扑排序
    •     二分图
    • 网络流问题
      •      最大流
    •     最小费用流
      • 例题

图论常用算法

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]));$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.