路徑問題
0/1邊權最短路徑
BFS
非負邊權最短路徑（Dijkstra）
可以用Dijkstra解決問題的特征
負邊權最短路徑
Bellman-Ford
Bellman-Ford的Yen-氏優化
差分約束系統
Floyd
廣義路徑問題
傳遞閉包
極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構造
生成樹問題
最小生成樹
第k小生成樹
最優比率生成樹
0/1分數規劃
度限制生成樹
連通性問題
強大的DFS算法
無向圖連通性
割點
割邊
二連通分支
有向圖連通性
強連通分支
2-SAT
最小點基
有向無環圖
拓撲排序
有向無環圖與動態規劃的關系
二分圖匹配問題
一般圖問題與二分圖問題的轉換思路
最大匹配
有向圖的最小路徑覆蓋
0 / 1矩陣的最小覆蓋
完備匹配
最優匹配
穩定婚姻
網絡流問題
網絡流模型的簡單特征和與線性規劃的關系
最大流最小割定理
最大流問題
有上下界的最大流問題
循環流
最小費用最大流 / 最大費用最大流
弦圖的性質和判定
posted on 2009-11-27 14:37
西風蕭瑟 閱讀(720)
評論(0) 編輯 收藏 引用 所屬分類:
圖論