圖論算法理論、實(shí)現(xiàn)及應(yīng)用(第2版)
定 價(jià)：88 元
叢書(shū)名：高等院校電氣信息類(lèi)專(zhuān)業(yè)"互聯(lián)網(wǎng)+"創(chuàng)新規(guī)劃教材
- 作者：王桂平,楊建喜,李韌
- 出版時(shí)間：2022/1/1
- ISBN：9787301323854
- 出 版 社：北京大學(xué)出版社
- 中圖法分類(lèi)：O157.5
- 頁(yè)碼：464
- 紙張：
- 版次：2
- 開(kāi)本：16開(kāi)
本書(shū)系統(tǒng)地介紹了圖論算法理論，并選取經(jīng)典的 ACM/ICPC 題目為例題闡述圖論算法思想，側(cè)重于圖論算法的程序?qū)崿F(xiàn)及應(yīng)用。本書(shū)第 1章介紹圖的基本概念和圖的兩種存儲(chǔ)表示方法：鄰接矩陣和鄰接表。第 2～9章分別討論圖的遍歷與活動(dòng)網(wǎng)絡(luò)問(wèn)題，樹(shù)與圖的生成樹(shù)，最短路徑問(wèn)題，可行遍性問(wèn)題，網(wǎng)絡(luò)流問(wèn)題，支配集、覆蓋集、獨(dú)立集與匹配，圖的連通性問(wèn)題，平面圖及圖的著色問(wèn)題。
本書(shū)可以作為高等院校計(jì)算機(jī)專(zhuān)業(yè)(或相關(guān)專(zhuān)業(yè))圖論等相關(guān)課程的主教材，也可作為 ACM/ICPC的輔導(dǎo)教材。
王桂平，博士，副教授，碩導(dǎo)，重慶交通大學(xué)數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專(zhuān)業(yè)負(fù)責(zé)人，近20年程序設(shè)計(jì)競(jìng)賽指導(dǎo)經(jīng)驗(yàn)，出版教材6本，主持省部級(jí)教學(xué)研究項(xiàng)目2項(xiàng)；主要從事交通基礎(chǔ)設(shè)施狀態(tài)監(jiān)測(cè)、損傷識(shí)別研究，以及機(jī)器學(xué)習(xí)、深度學(xué)習(xí)算法和大數(shù)據(jù)分析與處理算法研究，主持省部級(jí)科研項(xiàng)目3項(xiàng)，主研國(guó)家自然科學(xué)基金項(xiàng)目3項(xiàng)（均排名第2）、省部級(jí)科研項(xiàng)目4項(xiàng)；發(fā)表學(xué)術(shù)論文40多篇，其中第一作者SCI檢索期刊論文9篇、EI檢索期刊論文10篇。楊建喜，博士，教授，重慶交通大學(xué)，主要從事橋梁健康監(jiān)測(cè)、安全性評(píng)估及壽命預(yù)測(cè)方面的基礎(chǔ)理論研究及工程實(shí)踐。獲得國(guó)家科技進(jìn)步二等獎(jiǎng)1項(xiàng)、省部級(jí)科技一、二、三等獎(jiǎng)各1項(xiàng)；發(fā)明專(zhuān)利1項(xiàng)；出版學(xué)術(shù)著作1部；獲得軟件著作權(quán)3項(xiàng)；發(fā)表學(xué)術(shù)論文30多篇，其中：第一作者SCI檢索6篇、EI檢索10篇；主持國(guó)家自然科學(xué)基金項(xiàng)目1項(xiàng)、省部級(jí)重點(diǎn)課題1項(xiàng)、省部級(jí)一般基金項(xiàng)目3項(xiàng)；主研973前期計(jì)劃項(xiàng)目1項(xiàng)、國(guó)家自然科學(xué)基金2項(xiàng)、省部級(jí)課題10項(xiàng)。李韌，博士，副教授，重慶交通大學(xué)，主要從事大數(shù)據(jù)、神經(jīng)網(wǎng)絡(luò)方面的研究，共開(kāi)發(fā)表論文21篇，主參編教材6部。
第1章 圖的基本概念及圖的存儲(chǔ) 1
1.1 基本概念 1
1.1.1 有向圖與無(wú)向圖 1
1.1.2 完全圖、稀疏圖、稠密圖 2
1.1.3 頂點(diǎn)與頂點(diǎn)、頂點(diǎn)與邊的關(guān)系 3
1.1.4 頂點(diǎn)的度數(shù)及度序列 3
1.1.5 二部圖與完全二部圖 6
1.1.6 圖的同構(gòu) 7
1.1.7 子圖與生成樹(shù) 8
1.1.8 路徑 9
1.1.9 連通性 10
1.1.10 權(quán)值、有向網(wǎng)與無(wú)向網(wǎng) 11
1.2 圖的存儲(chǔ)表示 11
1.2.1 鄰接矩陣 12
1.2.2 可達(dá)性矩陣 20
1.2.3 鄰接表 21
1.2.4 關(guān)于鄰接矩陣和鄰接表的進(jìn)一步討論 26
練習(xí) 27
第2章 圖的遍歷與活動(dòng)網(wǎng)絡(luò)問(wèn)題 28
2.1 DFS遍歷 28
2.1.1 DFS算法思想 28
2.1.2 DFS算法的實(shí)現(xiàn)及復(fù)雜度分析 29
2.1.3 例題解析 32
練習(xí) 42
2.2 BFS遍歷 45
2.2.1 BFS算法思想 45
2.2.2 BFS算法的實(shí)現(xiàn)及復(fù)雜度分析 46
2.2.3 關(guān)于DFS算法和BFS算法的說(shuō)明 48
2.2.4 例題解析 48
練習(xí) 58
2.3 活動(dòng)網(wǎng)絡(luò)——AOV網(wǎng)絡(luò) 66
2.3.1 AOV網(wǎng)絡(luò)與拓?fù)渑判?66
2.3.2 拓?fù)渑判驅(qū)崿F(xiàn)方法 67
2.3.3 關(guān)于拓?fù)渑判虻倪M(jìn)一步說(shuō)明 71
2.3.4 例題解析 72
練習(xí) 82
2.4 活動(dòng)網(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章 樹(shù)與圖的生成樹(shù) 91
3.1 樹(shù)與森林 91
3.1.1 樹(shù) 91
3.1.2 森林 92
3.2 生成樹(shù)及最小生成樹(shù) 92
3.2.1 生成樹(shù) 92
3.2.2 最小生成樹(shù) 92
3.3 Kruskal算法和Boruvka算法 93
3.3.1 Kruskal算法思想 93
3.3.2 等價(jià)類(lèi)與并查集 94
3.3.3 Kruskal算法實(shí)現(xiàn) 98
3.3.4 關(guān)于Kruskal算法的進(jìn)一步討論 101
3.3.5 Boruvka算法 101
3.3.6 例題解析 102
練習(xí) 106
3.4 Prim算法 109
3.4.1 Prim算法思想 109
3.4.2 Prim算法實(shí)現(xiàn) 111
3.4.3 關(guān)于Prim算法的進(jìn)一步討論 114
3.4.4 例題解析 114
練習(xí) 118
3.5 最小生成樹(shù)問(wèn)題的拓展 121
3.5.1 帶權(quán)并查集 121
3.5.2 最大生成樹(shù) 124
3.5.3 最小生成森林、最大生成
森林 124
3.5.4 判定最小生成樹(shù)是否唯一 125
練習(xí) 129
第4章 最短路徑問(wèn)題 131
4.1 邊上權(quán)值非負(fù)情形的單源最短路徑問(wèn)題——Dijkstra算法 131
4.1.1 算法思想 131
4.1.2 算法實(shí)現(xiàn) 133
4.1.3 關(guān)于Dijkstra算法的進(jìn)一步討論 137
4.1.4 例題解析 137
練習(xí) 142
4.2 邊上權(quán)值為任意值的單源最短路徑問(wèn)題——Bellman-Ford算法 146
4.2.1 算法思想 146
4.2.2 算法實(shí)現(xiàn) 148
4.2.3 關(guān)于Bellman-Ford算法的進(jìn)一步討論 151
4.2.4 例題解析 154
練習(xí) 161
4.3 Bellman-Ford算法的改進(jìn)——SPFA算法 163
4.3.1 算法思想 163
4.3.2 算法實(shí)現(xiàn) 164
4.3.3 關(guān)于SPFA算法的進(jìn)一步討論 167
4.3.4 例題解析 167
練習(xí) 173
4.4 所有頂點(diǎn)之間的最短路徑——Floyd算法 175
4.4.1 算法思想 176
4.4.2 算法實(shí)現(xiàn) 177
4.4.3 關(guān)于Floyd算法的進(jìn)一步討論 180
4.4.4 例題解析 180
練習(xí) 186
4.5 最短路徑問(wèn)題拓展 190
4.5.1 有向網(wǎng)最短路徑、回路與最短簡(jiǎn)單路徑 190
4.5.2 無(wú)向網(wǎng)中的最短路徑問(wèn)題 190
4.5.3 單源最短路徑三角形不等式 192
4.5.4 最長(zhǎng)路徑 193
4.6 差分約束系統(tǒng) 197
4.6.1 差分約束系統(tǒng)與最短路徑問(wèn)題 197
4.6.2 例題解析 199
練習(xí) 207
第5章 可行遍性問(wèn)題 210
5.1 歐拉回路 210
5.1.1 基本概念及定理 210
5.1.2 歐拉回路的判定 214
練習(xí) 219
5.2 歐拉回路的求解 220
5.2.1 DFS算法求解歐拉回路 220
5.2.2 Fleury算法求解歐拉回路 226
練習(xí) 229
5.3 中國(guó)郵遞員問(wèn)題 231
5.4 漢密爾頓回路 232
5.4.1 基本概念及定理 233
5.4.2 漢密爾頓回路求解 234
第6章 網(wǎng)絡(luò)流問(wèn)題 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 一般預(yù)流推進(jìn)算法 261
6.1.8 最高標(biāo)號(hào)預(yù)流推進(jìn)算法 265
6.1.9 網(wǎng)絡(luò)最大流算法總結(jié) 266
6.1.10 例題解析 266
練習(xí) 279
6.2 最小割的求解 283
練習(xí) 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
練習(xí) 317
6.4 最小費(fèi)用最大流 318
6.4.1 基本概念 318
6.4.2 最小費(fèi)用最大流算法 319
6.4.3 例題解析 322
練習(xí) 329
第7章 支配集、覆蓋集、獨(dú)立集與匹配 333
7.1 點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集 333
7.1.1 點(diǎn)支配集 333
7.1.2 點(diǎn)覆蓋集 335
7.1.3 點(diǎn)獨(dú)立集 336
7.1.4 點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集之間的聯(lián)系 338
7.2 點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集的求解 339
7.2.1 邏輯運(yùn)算 339
7.2.2 極小點(diǎn)支配集的求解 339
7.2.3 極小點(diǎn)覆蓋集、極大點(diǎn)獨(dú)立集的求解 340
7.3 邊覆蓋集與邊獨(dú)立集 341
7.3.1 邊覆蓋集 341
7.3.2 邊獨(dú)立集(匹配) 342
7.3.3 最大邊獨(dú)立集(最大匹配)與最小邊覆蓋集之間的聯(lián)系 344
7.4 匹配問(wèn)題 345
7.4.1 完美匹配 345
7.4.2 二部圖的完備匹配與完美匹配 346
7.4.3 最佳匹配 346
7.4.4 匹配問(wèn)題求解的基本概念及思路 346
7.5 二部圖最大匹配問(wèn)題的求解 348
7.5.1 網(wǎng)絡(luò)流解法 348
7.5.2 匈牙利算法 349
7.5.3 例題解析 352
練習(xí) 367
第8章 圖的連通性問(wèn)題 373
8.1 基本概念 373
8.1.1 連通圖與非連通圖 373
8.1.2 無(wú)向圖的頂點(diǎn)連通性 374
8.1.3 無(wú)向圖的邊連通性 376
8.1.4 無(wú)向圖頂點(diǎn)連通性和邊連通性的聯(lián)系 377
8.1.5 有向圖的連通性 378
8.2 無(wú)向圖頂點(diǎn)連通性的求解及應(yīng)用 378
8.2.1 關(guān)節(jié)點(diǎn)的求解 378
8.2.2 重連通分量的求解 384
8.2.3 頂點(diǎn)連通度的求解 390
練習(xí) 394
8.3 無(wú)向圖邊連通性的求解及應(yīng)用 396
8.3.1 割邊的求解 396
8.3.2 邊雙連通分量的求解 400
8.3.3 邊連通度的求解 403
練習(xí) 404
8.4 有向圖連通性的求解及應(yīng)用 405
8.4.1 有向圖的深度優(yōu)先搜索 405
8.4.2 有向圖強(qiáng)連通分量的求解算法 407
8.4.3 有向圖強(qiáng)連通分量的應(yīng)用 412
8.4.4 有向圖單連通性的判定 421
8.4.5 有向圖弱連通性的判定 424
練習(xí) 424
第9章 平面圖及圖的著色問(wèn)題 427
9.1 基本概念 427
9.1.1 平面圖與非平面圖 427
9.1.2 區(qū)域與邊界 428
9.1.3 極大平面圖與極小非平面圖 429
9.1.4 平面圖的對(duì)偶圖 429
9.1.5 關(guān)于平面圖的一些定理 430
9.2 歐拉公式及其應(yīng)用 431
9.2.1 歐拉公式 431
9.2.2 歐拉公式的應(yīng)用 431
練習(xí) 434
9.3 平面圖的判定 435
9.4 圖的著色問(wèn)題 436
9.4.1 地圖染色與四色猜想 436
9.4.2 圖的著色 437
9.4.3 圖著色的應(yīng)用 440
9.4.4 圖著色求解算法及例題解析 440
練習(xí) 444
附錄 本書(shū)例題和練習(xí)題目錄 446
參考文獻(xiàn) 450
書(shū)單推薦
