路徑問題
0/1邊權(quán)最短路徑
BFS
非負(fù)邊權(quán)最短路徑（Dijkstra）
可以用Dijkstra解決問題的特征
負(fù)邊權(quán)最短路徑
Bellman-Ford
Bellman-Ford的Yen-氏優(yōu)化
差分約束系統(tǒng)
Floyd
廣義路徑問題
傳遞閉包
極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構(gòu)造
生成樹問題
最小生成樹
第k小生成樹
最優(yōu)比率生成樹
0/1分?jǐn)?shù)規(guī)劃
度限制生成樹
連通性問題
強大的DFS算法
無向圖連通性
割點
割邊
二連通分支
有向圖連通性
強連通分支
2-SAT
最小點基
有向無環(huán)圖
拓?fù)渑判?br> 有向無環(huán)圖與動態(tài)規(guī)劃的關(guān)系
二分圖匹配問題
一般圖問題與二分圖問題的轉(zhuǎn)換思路
最大匹配
有向圖的最小路徑覆蓋
0 / 1矩陣的最小覆蓋
完備匹配
最優(yōu)匹配
穩(wěn)定婚姻
網(wǎng)絡(luò)流問題
網(wǎng)絡(luò)流模型的簡單特征和與線性規(guī)劃的關(guān)系
最大流最小割定理
最大流問題
有上下界的最大流問題
循環(huán)流
最小費用最大流 / 最大費用最大流
弦圖的性質(zhì)和判定
posted on 2009-11-27 14:37
西風(fēng)蕭瑟 閱讀(737)
評論(0) 編輯 收藏 引用 所屬分類:
圖論