圖論常用算法

DFS的應(yīng)用

      1. 求無(wú)向圖的連通分量

           求無(wú)向圖的割點(diǎn)和橋

      2. 求無(wú)向圖的雙連通分量

      3. 求有向圖的強(qiáng)連通分量

      4. 拓?fù)渑判?/h3>

      5. 二分圖判斷

    最小生成樹

      最小生成樹

    最短路徑

        單源最短路

            Dijkstra算法

                    最短路徑·一

            Bellman-Ford算法（SPFA算法）

                    最短路徑·三：SPFA算法

        任意兩點(diǎn)間的最短路

            Floyd算法(佛洛依德算法)

                 最短路徑·二：Floyd算法

    拓?fù)渑判?/h3>

    二分圖

二分圖二·二分圖最大匹配之匈牙利算法
相關(guān)定理

網(wǎng)絡(luò)流問題

     最大流

        網(wǎng)絡(luò)流一·Ford-Fulkerson算法
        網(wǎng)絡(luò)流二.網(wǎng)絡(luò)流二·最大流最小割定理

    最小費(fèi)用流

        最小費(fèi)用流

例題

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
   最短路，狀態(tài)壓縮，邊是隱形邊需要在求最短路的時(shí)候求邊
   Code

4.