目錄


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