圖論算法理論、實現及套用

《圖論算法理論、實現及套用》是北京大學出版社出版的圖書，作者是王桂平 王 衍 任嘉辰。

基本介紹

• 書名：圖論算法理論、實現及套用
• 作者：王桂平  王  衍  任嘉辰
• ISBN：978-7-301-17578-1/TP·1122
• 出版社：北京大學出版社

內容介紹

本書系統地介紹了圖論算法理論，並選取經典的ACM/ICPC競賽題目為例題闡述圖論算法思想，側重於圖論算法的程式實現及套用。本書第1章介紹圖論基本概念和圖的兩種存儲表示方法：鄰接矩陣和鄰接表，第2～9章分別討論圖的遍歷與活動網路，樹與生成樹問題，最短路徑問題，可行遍性問題，網路流問題，點支配集、點覆蓋集、點獨立集、邊覆蓋集、邊獨立集(匹配)，圖的連通性問題，平面圖與圖的著色問題等。本書可以作為高等院校計算機(或相關專業)圖論等相關課程的主教材，也可作為ACM/ICPC競賽的輔導教材。

作品信息

書 名：圖論算法理論、實現及套用

標準書號：

定 價：54.00元

作品目錄

第1章 圖的基本概念及圖的存儲... 1

1.1 基本概念... 1

1.1.1 有向圖與無向圖... 1

1.1.2 完全圖、稀疏圖、稠密圖... 2

1.1.3 頂點與頂點、頂點與邊的

關係... 3

1.1.4 頂點的度數及度序列... 3

1.1.5 二部圖與完全二部圖... 5

1.1.6 圖的同構... 6

1.1.7 子圖與生成樹... 6

1.1.8 路徑... 8

1.1.9 連通性... 8

1.1.10 權值、有向網與無向網... 10

1.2 圖的存儲表示... 10

1.2.1 鄰接矩陣... 10

1.2.2 鄰接表... 17

1.2.3 關於鄰接矩陣和鄰接表的

進一步討論... 25

練習... 25

第2章 圖的遍歷與活動網路問題... 26

2.1 DFS遍歷... 26

2.1.1 DFS算法思想... 26

2.1.2 DFS算法的實現及複雜度

分析... 27

2.1.3 例題解析... 30

練習... 40

2.2 BFS遍歷... 43

2.2.1 BFS算法思想... 43

2.2.2 BFS算法的實現及複雜度

分析... 44

2.2.3 關於DFS算法和BFS算法

的說明... 46

2.2.4 例題解析... 46

練習... 60

2.3 活動網路——AOV網路... 66

2.3.1 AOV網路與拓撲排序... 66

2.3.2 拓撲排序實現方法... 68

2.3.3 關於拓撲排序的進一步說明... 73

2.3.4 例題解析... 74

練習... 82

2.4 活動網路——AOE網路... 84

2.4.1 AOE網路與關鍵路徑... 84

2.4.2 關鍵路徑求解方法... 85

第3章 樹與圖的生成樹... 92

3.1 樹與森林... 92

3.1.1 樹... 92

3.1.2 森林... 92

3.2 生成樹及最小生成樹... 93

3.2.1 生成樹... 93

3.2.2 最小生成樹... 93

3.3 克魯斯卡爾(Kruskal)算法... 94

3.3.1 克魯斯卡爾(Kruskal)算法

思想... 94

3.3.2 等價類與並查集... 95

3.3.3 Kruskal算法實現... 99

3.3.4 Boruvka算法... 103

3.3.5 例題解析... 104

練習... 110

3.4 普里姆算法... 114

3.4.1 Prim算法思想... 114

3.4.2 普里姆(Prim)算法實現... 115

3.4.3 關於普里姆算法的進一步

討論... 119

3.4.4 例題解析... 120

練習... 125

3.5 判定最小生成樹是否唯一... 129

3.5.1 最小生成樹不唯一的原因

分析... 129

3.5.2 判定最小生成樹是否唯一的

方法... 130

3.5.3 例題解析... 132

第4章 最短路徑問題... 137

4.1 邊上權值非負情形的單源最短

路徑問題—Dijkstra算法... 137

4.1.1 算法思想... 137

4.1.2 算法實現... 139

4.1.3 關於Dijkstra算法的

進一步討論... 143

4.1.4 例題解析... 143

練習... 150

4.2 邊上權值為任意值的單源最短

路徑問題—Bellman-Ford算法... 154

4.2.1 算法思想... 154

4.2.2 算法實現... 156

4.2.3 關於Bellman-Ford算法的

進一步討論... 160

4.2.4 例題解析... 163

練習... 171

4.3 Bellman-Ford算法的改進—

SPFA算法... 174

4.3.1 算法思想... 174

4.3.2 算法實現... 175

4.3.3 關於SPFA算法的進一步

討論... 179

4.3.4 例題解析... 179

練習... 186

4.4 所有頂點之間的最短路徑—

Floyd算法... 189

4.4.1 算法思想... 189

4.4.2 算法實現... 191

4.4.3 關於Floyd算法的進一步

分析... 194

4.4.4 例題解析... 194

練習... 202

4.5 差分約束系統... 208

4.5.1 差分約束系統與最短路徑... 208

4.5.2 例題解析... 210

練習... 219

第5章 可行遍性問題... 223

5.1 歐拉迴路... 223

5.1.1 基本概念及定理... 223

5.1.2 歐拉迴路的判定... 227

練習... 234

5.2 歐拉迴路的求解... 235

5.2.1 DFS搜尋求解歐拉迴路... 235

5.2.2 Fleury(佛羅萊)算法... 244

練習... 248

5.3 中國郵遞員問題... 250

5.4 漢密爾頓迴路... 251

5.4.1 基本概念及定理... 251

5.4.2 漢密爾頓迴路求解... 253

第6章 網路流問題... 258

6.1 網路最大流... 258

6.1.1 基本概念... 259

6.1.2 最大流最小割定理... 263

6.1.3 網路最大流的求解... 264

6.1.4 一般增廣路方法——

Ford-Fulkerson算法... 265

6.1.5 最短增廣路算法... 273

6.1.6 連續最短增廣路算法——

Dinic算法... 277

6.1.7 一般預流推進算法... 278

6.1.8 最高標號預流推進算法... 282

6.1.9 網路最大流算法總結... 283

6.1.10 例題解析... 283

練習... 299

6.2 最小割的求解... 303

練習... 316

6.3 流量有上下界的網路的最大流和

最小流... 318

6.3.1 流量有上下界的容量網路... 318

6.3.2 流量有上下界的網路的

最大流... 321

6.3.3 流量有上下界的網路的

最小流... 322

6.3.4 例題解析... 329

練習... 342

6.4 最小費用最大流... 343

6.4.1 基本概念... 343

6.4.2 最小費用最大流算法... 344

6.4.3 例題解析... 347

練習... 356

第7章 支配集、覆蓋集、獨立集與匹配... 360

7.1 點支配集、點覆蓋集、點獨立集... 360

7.1.1 點支配集... 360

7.1.2 點覆蓋集... 362

7.1.3 點獨立集... 363

7.1.4 點支配集、點覆蓋集、

點獨立集之間的聯繫... 365

7.2 點支配集、點覆蓋集、點獨立集的

求解... 365

7.2.1 邏輯運算... 365

7.2.2 極小點支配集的求解... 366

7.2.3 極小點覆蓋集、極大點

獨立集的求解... 366

7.3 邊覆蓋集與邊獨立集... 367

7.3.1 邊覆蓋集... 367

7.3.2 邊獨立集(匹配)368

7.3.3 最大邊獨立集(最大匹配)與

最小邊覆蓋集之間的聯繫... 370

7.4 匹配問題... 371

7.4.1 完美匹配... 371

7.4.2 二部圖的完備匹配與

完美匹配... 372

7.4.3 最佳匹配... 372

7.4.4 匹配問題求解的基本概念及

思路... 372

7.5 二部圖最大匹配問題的求解... 374

7.5.1 網路流解法... 374

7.5.2 匈牙利算法... 376

7.5.3 例題解析... 379

練習... 396

第8章 圖的連通性問題... 402

8.1 基本概念... 402

8.1.1 連通圖與非連通圖... 402

8.1.2 無向圖的點連通性... 403

8.1.3 無向圖的邊連通性... 405

8.1.4 無向圖頂點連通性和

邊連通性的聯繫... 406

8.1.5 有向圖的連通性... 406

8.2 無向圖點連通性的求解及套用... 407

8.2.1 關節點的求解... 407

8.2.2 重連通分量的求解... 414

8.2.3 頂點連通度的求解... 417

練習... 421

8.3 無向圖邊連通性的求解及套用... 424

8.3.1 割邊的求解... 424

8.3.2 邊雙連通分量的求解... 428

8.3.3 邊連通度的求解... 436

練習... 437

8.4 有向圖強連通性的求解及套用... 440

8.4.1 有向圖強連通分量的

求解算法... 440

8.4.2 有向圖強連通分量的套用... 442

練習... 458

第9章 平面圖及圖的著色問題... 462

9.1 基本概念... 462

9.1.1 平面圖與非平面圖... 462

9.1.2 區域與邊界... 463

9.1.3 極大平面圖與極小非平面圖... 464

9.1.4 平面圖的對偶圖... 464

9.1.5 關於平面圖的一些定理... 465

9.2 歐拉公式及其套用... 465

9.2.1 歐拉公式... 465

9.2.2 歐拉公式的套用... 466

練習... 469

9.3 平面圖的判定... 470

9.4 圖的著色問題... 472

9.4.1 地圖染色與四色猜想... 472

9.4.2 圖的著色... 472

9.4.3 圖著色的套用... 475

9.4.4 圖著色求解算法及例題解析... 475

練習... 479

附錄 本書例題和練習題目錄... 482

索引... 489

參考文獻 497