ACM-ICPC程序設計系列圖論及應用

第1章  圖
  1.1  圖的定義和術語
    1.1.1  圖的定義
    1.1.2  特殊的圖
    1.1.3  有向圖和無向圖
    1.1.4  路徑與連通
  1.2  圖的存儲結(jié)構
    1.2.1  鄰接矩陣
    1.2.2  前向星
    1.2.3  鄰接表
  1.3  圖的遍歷
    1.3.1  圖的深度優(yōu)先遍歷
    1.3.2  圖的寬度優(yōu)先遍歷
    1.3.3  圖的拓撲排序
    1.3.4  圖的可行遍性
第2章  樹
  2.1  樹的定義和遍歷
    2.1.1  樹的相關定義
    2.1.2　樹的遍歷
  2.2  圖的生成樹
    2.2.1  最小生成樹
    2.2.2　次小生成樹
    2.2.3  有向圖的最小樹形圖
  2.3  樹的其他問題
    2.3.1  樹上兩點的最近公共祖先
    2.3.2  樹的最小支配集，最小點覆蓋與最大獨立集
第3章  圖的最短路徑問題
  3.1  單源最短路徑
    3.1.1  Dijkstra算法
    3.1.2  Bellman—Ford算法
    3.1.3  SPFA算法
    3.1.4　例題
  3.2  每對頂點間的最短距離
    3.2.1  Floyd算法
    3.2.2　例題
  3.3  最短路問題的擴展與應用
    3.3.1  k短路
    3.3.2  差分約束系統(tǒng)
    3.3.3  DAG圖上的單源最短路徑
    3.3.4 Floyd求最小環(huán)
第4章  連通性問題
  4.1  圖的強連通
    4.1.1  強連通的定義
    4.1.2  Kosaraju算法 
    4.1.3  Tarjan算法 
    4.1.4  Garbow算法
    4.1.5  例題
  4.2　最小點基
    4.2.1  最小點基的定義
    4.2.2  最小點基
    4.2.3  最小權點基
    4.2.4  例題
  4.3  圖的雙連通
    4.3.1  雙連通的定義
    4.3.2  點雙連通分量
    4.3.3  邊雙連通分量
    4.3.4　例題
 4.4  圖的全局最小割問題和Stoer—Wagner算法
 4.5  2一SAT 
    4.5.1  SAT 
    4.5.2  2一SAT
    4.5.3  例題
第5章  網(wǎng)絡流
第6章  二分圖及匹配算法
參考文獻