第1章　圖的基本概念及圖的存儲 1 1.1　基本概念 1 1.1.1　有向圖與無向圖 1 1.1.2　完全圖、稀疏圖、稠密圖 2 1.1.3　頂點與頂點、頂點與邊的關(guān)系 3 1.1.4　頂點的度數(shù)及度序列 3 1.1.5　二部圖與完全二部圖 6 1.1.6　圖的同構(gòu) 7 1.1.7　子圖與生成樹 8 1.1.8　路徑 9 1.1.9　連通性 10 1.1.10　權(quán)值、有向網(wǎng)與無向網(wǎng) 11 1.2　圖的存儲表示 11 1.2.1　鄰接矩陣 12 1.2.2　可達性矩陣 20 1.2.3　鄰接表 21 1.2.4　關(guān)于鄰接矩陣和鄰接表的進一步討論 26 練習 27 第2章　圖的遍歷與活動網(wǎng)絡(luò)問題 28 2.1　DFS遍歷 28 2.1.1　DFS算法思想 28 2.1.2　DFS算法的實現(xiàn)及復雜度分析 29 2.1.3　例題解析 32 練習 42 2.2　BFS遍歷 45 2.2.1　BFS算法思想 45 2.2.2　BFS算法的實現(xiàn)及復雜度分析 46 2.2.3　關(guān)于DFS算法和BFS算法的說明 48 2.2.4　例題解析 48 練習 58 2.3　活動網(wǎng)絡(luò)——AOV網(wǎng)絡(luò) 66 2.3.1　AOV網(wǎng)絡(luò)與拓撲排序 66 2.3.2　拓撲排序?qū)崿F(xiàn)方法 67 2.3.3　關(guān)于拓撲排序的進一步說明 71 2.3.4　例題解析 72 練習 82 2.4　活動網(wǎng)絡(luò)——AOE網(wǎng)絡(luò) 84 2.4.1　AOE網(wǎng)絡(luò)與關(guān)鍵路徑 84 2.4.2　關(guān)鍵路徑求解方法 85 第3章　樹與圖的生成樹 91 3.1　樹與森林 91 3.1.1　樹 91 3.1.2　森林 92 3.2　生成樹及最小生成樹 92 3.2.1　生成樹 92 3.2.2　最小生成樹 92 3.3　Kruskal算法和Boruvka算法 93 3.3.1　Kruskal算法思想 93 3.3.2　等價類與并查集 94 3.3.3　Kruskal算法實現(xiàn) 98 3.3.4　關(guān)于Kruskal算法的進一步討論 101 3.3.5　Boruvka算法 101 3.3.6　例題解析 102 練習 106 3.4　Prim算法 109 3.4.1　Prim算法思想 109 3.4.2　Prim算法實現(xiàn) 111 3.4.3　關(guān)于Prim算法的進一步討論 114 3.4.4　例題解析 114 練習 118 3.5　最小生成樹問題的拓展 121 3.5.1　帶權(quán)并查集 121 3.5.2　最大生成樹 124 3.5.3　最小生成森林、最大生成 森林 124 3.5.4　判定最小生成樹是否唯一 125 練習 129 第4章　最短路徑問題 131 4.1　邊上權(quán)值非負情形的單源最短路徑問題——Dijkstra算法 131 4.1.1　算法思想 131 4.1.2　算法實現(xiàn) 133 4.1.3　關(guān)于Dijkstra算法的進一步討論 137 4.1.4　例題解析 137 練習 142 4.2　邊上權(quán)值為任意值的單源最短路徑問題——Bellman-Ford算法 146 4.2.1　算法思想 146 4.2.2　算法實現(xiàn) 148 4.2.3　關(guān)于Bellman-Ford算法的進一步討論 151 4.2.4　例題解析 154 練習 161 4.3　Bellman-Ford算法的改進——SPFA算法 163 4.3.1　算法思想 163 4.3.2　算法實現(xiàn) 164 4.3.3　關(guān)于SPFA算法的進一步討論 167 4.3.4　例題解析 167 練習 173 4.4　所有頂點之間的最短路徑——Floyd算法 175 4.4.1　算法思想 176 4.4.2　算法實現(xiàn) 177 4.4.3　關(guān)于Floyd算法的進一步討論 180 4.4.4　例題解析 180 練習 186 4.5　最短路徑問題拓展 190 4.5.1　有向網(wǎng)最短路徑、回路與最短簡單路徑 190 4.5.2　無向網(wǎng)中的最短路徑問題 190 4.5.3　單源最短路徑三角形不等式 192 4.5.4　最長路徑 193 4.6　差分約束系統(tǒng) 197 4.6.1　差分約束系統(tǒng)與最短路徑問題 197 4.6.2　例題解析 199 練習 207 第5章　可行遍性問題 210 5.1　歐拉回路 210 5.1.1　基本概念及定理 210 5.1.2　歐拉回路的判定 214 練習 219 5.2　歐拉回路的求解 220 5.2.1　DFS算法求解歐拉回路 220 5.2.2　Fleury算法求解歐拉回路 226 練習 229 5.3　中國郵遞員問題 231 5.4　漢密爾頓回路 232 5.4.1　基本概念及定理 233 5.4.2　漢密爾頓回路求解 234 第6章　網(wǎng)絡(luò)流問題 239 6.1　網(wǎng)絡(luò)最大流 239 6.1.1　基本概念 240 6.1.2　最大流最小割定理 245 6.1.3　網(wǎng)絡(luò)最大流的求解 245 6.1.4　一般增廣路方法——Ford-Fulkerson算法 246 6.1.5　最短增廣路算法 254 6.1.6　連續(xù)最短增廣路算法——Dinic算法 257 6.1.7　一般預流推進算法 261 6.1.8　最高標號預流推進算法 265 6.1.9　網(wǎng)絡(luò)最大流算法總結(jié) 266 6.1.10　例題解析 266 練習 279 6.2　最小割的求解 283 練習 293 6.3　流量有上下界的網(wǎng)絡(luò)的最大流和最小流 296 6.3.1　流量有上下界的容量網(wǎng)絡(luò) 296 6.3.2　流量有上下界的網(wǎng)絡(luò)的最大流 299 6.3.3　流量有上下界的網(wǎng)絡(luò)的最小流 300 6.3.4　例題解析 305 練習 317 6.4　最小費用最大流 318 6.4.1　基本概念 318 6.4.2　最小費用最大流算法 319 6.4.3　例題解析 322 練習 329 第7章　支配集、覆蓋集、獨立集與匹配 333 7.1　點支配集、點覆蓋集、點獨立集 333 7.1.1　點支配集 333 7.1.2　點覆蓋集 335 7.1.3　點獨立集 336 7.1.4　點支配集、點覆蓋集、點獨立集之間的聯(lián)系 338 7.2　點支配集、點覆蓋集、點獨立集的求解 339 7.2.1　邏輯運算 339 7.2.2　極小點支配集的求解 339 7.2.3　極小點覆蓋集、極大點獨立集的求解 340 7.3　邊覆蓋集與邊獨立集 341 7.3.1　邊覆蓋集 341 7.3.2　邊獨立集(匹配) 342 7.3.3　最大邊獨立集(最大匹配)與最小邊覆蓋集之間的聯(lián)系 344 7.4　匹配問題 345 7.4.1　完美匹配 345 7.4.2　二部圖的完備匹配與完美匹配 346 7.4.3　最佳匹配 346 7.4.4　匹配問題求解的基本概念及思路 346 7.5　二部圖最大匹配問題的求解 348 7.5.1　網(wǎng)絡(luò)流解法 348 7.5.2　匈牙利算法 349 7.5.3　例題解析 352 練習 367 第8章　圖的連通性問題 373 8.1　基本概念 373 8.1.1　連通圖與非連通圖 373 8.1.2　無向圖的頂點連通性 374 8.1.3　無向圖的邊連通性 376 8.1.4　無向圖頂點連通性和邊連通性的聯(lián)系 377 8.1.5　有向圖的連通性 378 8.2　無向圖頂點連通性的求解及應用 378 8.2.1　關(guān)節(jié)點的求解 378 8.2.2　重連通分量的求解 384 8.2.3　頂點連通度的求解 390 練習 394 8.3　無向圖邊連通性的求解及應用 396 8.3.1　割邊的求解 396 8.3.2　邊雙連通分量的求解 400 8.3.3　邊連通度的求解 403 練習 404 8.4　有向圖連通性的求解及應用 405 8.4.1　有向圖的深度優(yōu)先搜索 405 8.4.2　有向圖強連通分量的求解算法 407 8.4.3　有向圖強連通分量的應用 412 8.4.4　有向圖單連通性的判定 421 8.4.5　有向圖弱連通性的判定 424 練習 424 第9章　平面圖及圖的著色問題 427 9.1　基本概念 427 9.1.1　平面圖與非平面圖 427 9.1.2　區(qū)域與邊界 428 9.1.3　極大平面圖與極小非平面圖 429 9.1.4　平面圖的對偶圖 429 9.1.5　關(guān)于平面圖的一些定理 430 9.2　歐拉公式及其應用 431 9.2.1　歐拉公式 431 9.2.2　歐拉公式的應用 431 練習 434 9.3　平面圖的判定 435 9.4　圖的著色問題 436 9.4.1　地圖染色與四色猜想 436 9.4.2　圖的著色 437 9.4.3　圖著色的應用 440 9.4.4　圖著色求解算法及例題解析 440 練習 444 附錄　本書例題和練習題目錄 446 參考文獻 450