目錄


第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)先搜索的搜索過(guò)程 14
2.1.3　代碼框架 17
2.1.4　深度優(yōu)先搜索三部曲 18
2.2　可達(dá)路徑 20
2.2.1　解題思路 23
2.2.2　圖的存儲(chǔ) 23
2.2.3　求解過(guò)程 24
2.2.4　輸出結(jié)果 26
2.2.5　實(shí)現(xiàn)代碼 27
2.2.6　小結(jié) 30
2.3　廣度優(yōu)先搜索的理論基礎(chǔ) 30
2.3.1　廣度優(yōu)先搜索的使用場(chǎng)景 30
2.3.2　廣度優(yōu)先搜索的搜索過(guò)程 30
2.3.3　代碼框架 32
2.4　島嶼問(wèn)題（一） 34
2.4.1　解題思路 35
2.4.2　深度優(yōu)先搜索的實(shí)現(xiàn)代碼 36
2.5　島嶼問(wèn)題（二） 39
2.6　島嶼問(wèn)題（三） 42
2.6.1　解題思路 44
2.6.2　深度優(yōu)先搜索的實(shí)現(xiàn)代碼 44
2.6.3　廣度優(yōu)先搜索的實(shí)現(xiàn)代碼 47
2.7　島嶼問(wèn)題（四） 49
2.7.1　解題思路 50
2.7.2　實(shí)現(xiàn)代碼 52
2.8　島嶼問(wèn)題（五） 55
2.8.1　解題思路 56
2.8.2　實(shí)現(xiàn)代碼 58
2.9　島嶼問(wèn)題（六） 59
2.9.1　解題思路 61
2.9.2　實(shí)現(xiàn)代碼 61
2.9.3　優(yōu)化思路 64
2.10　島嶼問(wèn)題（七） 68
2.10.1　解題思路 69
2.10.2　優(yōu)化思路 70
2.11　島嶼問(wèn)題（八） 76
2.11.1　解題思路 78
2.11.2　具體解法 78
2.12　字符串遷移 81
2.12.1　解題思路 82
2.12.2　實(shí)現(xiàn)代碼 84
2.13　有向圖的完全連通 86
2.13.1　解題思路 87
2.13.2　實(shí)現(xiàn)代碼 90
2.14　拓?fù)渑判?93
2.14.1　拓?fù)渑判虻膽?yīng)用 95
2.14.2　拓?fù)渑判虻慕忸}思路 95
2.14.3　模擬拓?fù)渑判虻倪^(guò)程 97
2.14.4　判斷圖中是否有環(huán) 99
2.14.5　實(shí)現(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　常見(jiàn)誤區(qū) 111
3.1.6　模擬過(guò)程 114
3.1.7　拓展路徑壓縮的思路 116
3.1.8　復(fù)雜度分析 119
3.2　并查集尋找路徑 120
3.2.1　解題思路 121
3.2.2　實(shí)現(xiàn)代碼 121
3.3　并查集尋找無(wú)向邊 123
3.3.1　解題思路 125
3.3.2　實(shí)現(xiàn)代碼 126
3.3.3　常見(jiàn)疑問(wèn) 127
3.4　并查集尋找有向邊 128
3.4.1　解題思路 130
3.4.2　實(shí)現(xiàn)代碼 131
第４章　最小生成樹(shù) 136
4.1　Prim算法 137
4.1.1　解題思路 138
4.1.2　模擬過(guò)程 139
4.1.3　實(shí)現(xiàn)代碼 147
4.1.4　拓展思路 149
4.1.5　小結(jié) 152
4.2　Kruskal算法 153
4.2.1　解題思路 153
4.2.2　實(shí)現(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算法的工作過(guò)程 165
5.1.3　Dijkstra算法與Prim算法的區(qū)別 183
5.2　Dijkstra算法（堆優(yōu)化版） 184
5.2.1　解題思路 184
5.2.2　實(shí)現(xiàn)代碼 190
5.2.3　拓展思路 194
5.3　Bellman-Ford算法 196
5.3.1　解題思路 198
5.3.2　什么是松弛 199
5.3.3　模擬過(guò)程 200
5.3.4　實(shí)現(xiàn)代碼 205
5.3.5　拓展思路 206
5.4　Bellman-Ford算法之隊(duì)列優(yōu)化 208
5.4.1　背景 208
5.4.2　模擬過(guò)程 209
5.4.3　實(shí)現(xiàn)代碼 214
5.4.4　效率分析 216
5.4.5　拓展思路 218
5.5　Bellman-Ford算法之判斷負(fù)權(quán)回路 219
5.5.1　解題思路 220
5.5.2　實(shí)現(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　實(shí)現(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*算法的解題過(guò)程 263
5.8.3　復(fù)雜度分析 267
5.8.4　拓展思路 267
5.8.5　A*算法的缺點(diǎn) 268