代碼隨想錄2：圖論

孫秀洋

代碼隨想錄2：圖論
  • 出版商: 電子工業
  • 出版日期: 2025-10-01
  • 售價: $648
  • 語言: 簡體中文
  • 頁數: 280
  • ISBN: 7121513765
  • ISBN-13: 9787121513763
  • 相關分類: Algorithms-data-structures

    • 下單後立即進貨 (約4週~6週)

買這商品的人也買了...

商品描述

本書歸納了計算機的經典算法題，並按照由淺入深、循序漸進的順序講解。本書對圖論等算法中的重點內容進行了詳細的講解，重點講解並查集、最小生成樹算法（包括Prim和Kruskal算法）和最短路徑算法（包括 Dijkstra、Bellman-Ford、Floyd和A*算法），既註重理論推導，也強調代碼實現與調試技巧。每一章均有清晰的思路分析、代碼模板和常見錯誤總結，兼顧基礎知識鞏固與應用能力提升。

目錄大綱

目錄

第1章　圖論理論基礎 1
1.1　圖論的第一印象 2
1.1.1　連通性 4
1.1.2　圖的構造 7
1.1.3　圖的遍歷方式 11
1.1.4　小結 12
1.2　為什麼使用ACM輸入/輸出模式 12
第2章　深度優先搜索與廣度優先搜索 13
2.1　深度優先搜索的理論基礎 14
2.1.1　深度優先搜索與廣度優先搜索的區別 14
2.1.2　深度優先搜索的搜索過程 14
2.1.3　代碼框架 17
2.1.4　深度優先搜索三部曲 18
2.2　可達路徑 20
2.2.1　解題思路 23
2.2.2　圖的存儲 23
2.2.3　求解過程 24
2.2.4　輸出結果 26
2.2.5　實現代碼 27
2.2.6　小結 30
2.3　廣度優先搜索的理論基礎 30
2.3.1　廣度優先搜索的使用場景 30
2.3.2　廣度優先搜索的搜索過程 30
2.3.3　代碼框架 32
2.4　島嶼問題（一） 34
2.4.1　解題思路 35
2.4.2　深度優先搜索的實現代碼 36
2.5　島嶼問題（二） 39
2.6　島嶼問題（三） 42
2.6.1　解題思路 44
2.6.2　深度優先搜索的實現代碼 44
2.6.3　廣度優先搜索的實現代碼 47
2.7　島嶼問題（四） 49
2.7.1　解題思路 50
2.7.2　實現代碼 52
2.8　島嶼問題（五） 55
2.8.1　解題思路 56
2.8.2　實現代碼 58
2.9　島嶼問題（六） 59
2.9.1　解題思路 61
2.9.2　實現代碼 61
2.9.3　優化思路 64
2.10　島嶼問題（七） 68
2.10.1　解題思路 69
2.10.2　優化思路 70
2.11　島嶼問題（八） 76
2.11.1　解題思路 78
2.11.2　具體解法 78
2.12　字符串遷移 81
2.12.1　解題思路 82
2.12.2　實現代碼 84
2.13　有向圖的完全連通 86
2.13.1　解題思路 87
2.13.2　實現代碼 90
2.14　拓撲排序 93
2.14.1　拓撲排序的應用 95
2.14.2　拓撲排序的解題思路 95
2.14.3　模擬拓撲排序的過程 97
2.14.4　判斷圖中是否有環 99
2.14.5　實現代碼 100
第3章　並查集 105
3.1　並查集理論基礎 106
3.1.1　背景 106
3.1.2　基本原理 106
3.1.3　路徑壓縮 108
3.1.4　代碼模板 110
3.1.5　常見誤區 111
3.1.6　模擬過程 114
3.1.7　拓展路徑壓縮的思路 116
3.1.8　復雜度分析 119
3.2　並查集尋找路徑 120
3.2.1　解題思路 121
3.2.2　實現代碼 121
3.3　並查集尋找無向邊 123
3.3.1　解題思路 125
3.3.2　實現代碼 126
3.3.3　常見疑問 127
3.4　並查集尋找有向邊 128
3.4.1　解題思路 130
3.4.2　實現代碼 131
第４章　最小生成樹 136
4.1　Prim算法 137
4.1.1　解題思路 138
4.1.2　模擬過程 139
4.1.3　實現代碼 147
4.1.4　拓展思路 149
4.1.5　小結 152
4.2　Kruskal算法 153
4.2.1　解題思路 153
4.2.2　實現代碼 156
4.2.3　題目拓展（一） 158
4.2.4　題目拓展（二） 160
第5章　最短路徑算法 162
5.1　Dijkstra算法（樸素版） 163
5.1.1　解題思路 165
5.1.2　Dijkstra算法的工作過程 165
5.1.3　Dijkstra算法與Prim算法的區別 183
5.2　Dijkstra算法（堆優化版） 184
5.2.1　解題思路 184
5.2.2　實現代碼 190
5.2.3　拓展思路 194
5.3　Bellman-Ford算法 196
5.3.1　解題思路 198
5.3.2　什麼是松弛 199
5.3.3　模擬過程 200
5.3.4　實現代碼 205
5.3.5　拓展思路 206
5.4　Bellman-Ford算法之隊列優化 208
5.4.1　背景 208
5.4.2　模擬過程 209
5.4.3　實現代碼 214
5.4.4　效率分析 216
5.4.5　拓展思路 218
5.5　Bellman-Ford算法之判斷負權回路 219
5.5.1　解題思路 220
5.5.2　實現代碼 222
5.5.3　拓展思路 223
5.6　Bellman-Ford算法之單源有限最短路徑 228
5.6.1　解題思路 230
5.6.2　拓展一（邊的順序對結果的影響） 237
5.6.3　拓展二（本題本質） 240
5.6.4　拓展三（SPFA算法） 240
5.6.5　拓展四（能否使用Dijkstra算法） 244
5.7　Floyd算法 247
5.7.1　解題思路 249
5.7.2　實現代碼 256
5.7.3　空間優化 257
5.7.4　小結 259
5.8　A*算法 259
5.8.1　解題思路 261
5.8.2　A*算法的解題過程 263
5.8.3　復雜度分析 267
5.8.4　拓展思路 267
5.8.5　A*算法的缺點 268

類似商品