《圖論算法理論、實現及套用(第2版)》是北京大學出版社出版圖書，作者是王桂平、楊建喜、李韌。
基本介紹
- 中文名：圖論算法理論、實現及套用(第2版)
- 作者：王桂平、楊建喜、李韌
- 類別：高等院校電氣信息類專業"網際網路+"創新規劃教材
- 出版社：北京大學出版社
- 出版時間：2022年1月1日
- 頁數：464 頁
- 定價：88.00 元
- 開本：16 開
- 裝幀：平裝
- ISBN：9787301323854
- 字數：696000
內容簡介,圖書目錄,
內容簡介
本書系統地介紹了圖論算法理論，並選取經典的 ACM/ICPC 題目為例題闡述圖論算法思想，側重於圖論算法的程式實現及套用。本書第 1章介紹圖的基本概念和圖的兩種存儲表示方法：鄰接矩陣和鄰接表。第 2～9章分別討論圖的遍歷與活動網路問題，樹與圖的生成樹，最短路徑問題，可行遍性問題，網路流問題，支配集、覆蓋集、獨立集與匹配，圖的連通性問題，平面圖及圖的著色問題。
本書可以作為高等院校計算機專業(或相關專業)圖論等相關課程的主教材，也可作為 ACM/ICPC的輔導教材。
圖書目錄
第1章 圖的基本概念及圖的存儲 1
1.1 基本概念 1
1.1.1 有向圖與無向圖 1
1.1.2 完全圖、稀疏圖、稠密圖 2
1.1.3 頂點與頂點、頂點與邊的關係 3
1.1.4 頂點的度數及度序列 3
1.1.5 二部圖與完全二部圖 6
1.1.6 圖的同構 7
1.1.7 子圖與生成樹 8
1.1.8 路徑 9
1.1.9 連通性 10
1.1.10 權值、有向網與無向網 11
1.2 圖的存儲表示 11
1.2.1 鄰接矩陣 12
1.2.2 可達性矩陣 20
1.2.3 鄰接表 21
1.2.4 關於鄰接矩陣和鄰接表的進一步討論 26
練習 27
第2章 圖的遍歷與活動網路問題 28
2.1 DFS遍歷 28
2.1.1 DFS算法思想 28
2.1.2 DFS算法的實現及複雜度分析 29
2.1.3 例題解析 32
練習 42
2.2 BFS遍歷 45
2.2.1 BFS算法思想 45
2.2.2 BFS算法的實現及複雜度分析 46
2.2.3 關於DFS算法和BFS算法的說明 48
2.2.4 例題解析 48
練習 58
2.3 活動網路——AOV網路 66
2.3.1 AOV網路與拓撲排序 66
2.3.2 拓撲排序實現方法 67
2.3.3 關於拓撲排序的進一步說明 71
2.3.4 例題解析 72
練習 82
2.4 活動網路——AOE網路 84
2.4.1 AOE網路與關鍵路徑 84
2.4.2 關鍵路徑求解方法 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算法實現 98
3.3.4 關於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算法實現 111
3.4.3 關於Prim算法的進一步討論 114
3.4.4 例題解析 114
練習 118
3.5 最小生成樹問題的拓展 121
3.5.1 帶權並查集 121
3.5.2 最大生成樹 124
3.5.3 最小生成森林、最大生成
森林 124
3.5.4 判定最小生成樹是否唯一 125
練習 129
第4章 最短路徑問題 131
4.1 邊上權值非負情形的單源最短路徑問題——Dijkstra算法 131
4.1.1 算法思想 131
4.1.2 算法實現 133
4.1.3 關於Dijkstra算法的進一步討論 137
4.1.4 例題解析 137
練習 142
4.2 邊上權值為任意值的單源最短路徑問題——Bellman-Ford算法 146
4.2.1 算法思想 146
4.2.2 算法實現 148
4.2.3 關於Bellman-Ford算法的進一步討論 151
4.2.4 例題解析 154
練習 161
4.3 Bellman-Ford算法的改進——SPFA算法 163
4.3.1 算法思想 163
4.3.2 算法實現 164
4.3.3 關於SPFA算法的進一步討論 167
4.3.4 例題解析 167
練習 173
4.4 所有頂點之間的最短路徑——Floyd算法 175
4.4.1 算法思想 176
4.4.2 算法實現 177
4.4.3 關於Floyd算法的進一步討論 180
4.4.4 例題解析 180
練習 186
4.5 最短路徑問題拓展 190
4.5.1 有向網最短路徑、迴路與最短簡單路徑 190
4.5.2 無向網中的最短路徑問題 190
4.5.3 單源最短路徑三角形不等式 192
4.5.4 最長路徑 193
4.6 差分約束系統 197
4.6.1 差分約束系統與最短路徑問題 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章 網路流問題 239
6.1 網路最大流 239
6.1.1 基本概念 240
6.1.2 最大流最小割定理 245
6.1.3 網路最大流的求解 245
6.1.4 一般增廣路方法——Ford-Fulkerson算法 246
6.1.5 最短增廣路算法 254
6.1.6 連續最短增廣路算法——Dinic算法 257
6.1.7 一般預流推進算法 261
6.1.8 最高標號預流推進算法 265
6.1.9 網路最大流算法總結 266
6.1.10 例題解析 266
練習 279
6.2 最小割的求解 283
練習 293
6.3 流量有上下界的網路的最大流和最小流 296
6.3.1 流量有上下界的容量網路 296
6.3.2 流量有上下界的網路的最大流 299
6.3.3 流量有上下界的網路的最小流 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 點支配集、點覆蓋集、點獨立集之間的聯繫 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 最大邊獨立集(最大匹配)與最小邊覆蓋集之間的聯繫 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 網路流解法 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 無向圖頂點連通性和邊連通性的聯繫 377
8.1.5 有向圖的連通性 378
8.2 無向圖頂點連通性的求解及套用 378
8.2.1 關節點的求解 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 有向圖的深度優先搜尋 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 區域與邊界 428
9.1.3 極大平面圖與極小非平面圖 429
9.1.4 平面圖的對偶圖 429
9.1.5 關於平面圖的一些定理 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
