掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
闖進數學世界――探秘歷史名題
-
>
中醫基礎理論
-
>
當代中國政府與政治(新編21世紀公共管理系列教材)
-
>
高校軍事課教程
-
>
思想道德與法治(2021年版)
-
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)
-
>
中醫內科學·全國中醫藥行業高等教育“十四五”規劃教材
圖論算法理論、實現及應用(第2版) 版權信息
- ISBN：9787301323854
- 條形碼：9787301323854 ; 978-7-301-32385-4
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>>
圖論算法理論、實現及應用(第2版) 本書特色
本書可以作為高等院校計算機專業(或相關專業)圖論等相關課程的主教材，也可作為 ACM/ICPC的輔導教材。
圖論算法理論、實現及應用(第2版) 內容簡介
本書系統地介紹了圖論算法理論，并選取經典的 ACM/ICPC 題目為例題闡述圖論算法思想，側重于圖論算法的程序實現及應用。本書第 1章介紹圖的基本概念和圖的兩種存儲表示方法：鄰接矩陣和鄰接表。第 2～9章分別討論圖的遍歷與活動網絡問題，樹與圖的生成樹，*短路徑問題，可行遍性問題，網絡流問題，支配集、覆蓋集、獨立集與匹配，圖的連通性問題，平面圖及圖的著色問題。 本書可以作為高等院校計算機專業(或相關專業)圖論等相關課程的主教材，也可作為 ACM/ICPC的輔導教材。
圖論算法理論、實現及應用(第2版) 目錄
第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
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
展開全部
圖論算法理論、實現及應用(第2版) 作者簡介
王桂平，博士，副教授，碩導，重慶交通大學數據科學與大數據技術專業負責人，近20年程序設計競賽指導經驗，出版教材6本，主持省部級教學研究項目2項；主要從事交通基礎設施狀態監測、損傷識別研究，以及機器學習、深度學習算法和大數據分析與處理算法研究，主持省部級科研項目3項，主研國家自然科學基金項目3項（均排名第2）、省部級科研項目4項；發表學術論文40多篇，其中第一作者SCI檢索期刊論文9篇、EI檢索期刊論文10篇。楊建喜，博士，教授，重慶交通大學，主要從事橋梁健康監測、安全性評估及壽命預測方面的基礎理論研究及工程實踐。獲得國家科技進步二等獎1項、省部級科技一、二、三等獎各1項；發明專利1項；出版學術著作1部；獲得軟件著作權3項；發表學術論文30多篇，其中：第一作者SCI檢索6篇、EI檢索10篇；主持國家自然科學基金項目1項、省部級重點課題1項、省部級一般基金項目3項；主研973前期計劃項目1項、國家自然科學基金2項、省部級課題10項。李韌，博士，副教授，重慶交通大學，主要從事大數據、神經網絡方面的研究，共開發表論文21篇，主參編教材6部。
書友推薦
- >
中國歷史的瞬間
- >
唐代進士錄
- >
伯納黛特,你要去哪(2021新版)
- >
詩經-先民的歌唱
- >
朝聞道
- >
有舍有得是人生
- >
上帝之肋:男人的真實旅程
- >
名家帶你讀魯迅:朝花夕拾
本類暢銷
