算法詳解 卷2 圖算法和數(shù)據(jù)結(jié)構(gòu)

第1章 圖的基礎(chǔ)知識(shí)\t1
1．1　基本術(shù)語　1
1．2　圖的一些應(yīng)用　2
1．3　圖形的度量　3
1．3．1　圖的邊數(shù)量　3
1．3．2　稀疏圖和稠密圖　4
1．3．3　小測驗(yàn)1．1的答案　5
1．4　圖的表示方法　7
1．4．1　鄰接列表　7
1．4．2　鄰接矩陣　8
1．4．3　圖的表示形式之間的比較　9
1．4．4　小測驗(yàn)1．2和小測驗(yàn)1．3的答案　10
1．5　本章要點(diǎn)　11
1．6　章末習(xí)題　12
第2章　圖的搜索及其應(yīng)用　14
2．1　概述　14
2．1．1　一些應(yīng)用　15
2．1．2　零代價(jià)的基本算法　16
2．1．3　通用的圖搜索算法　17
2．1．4　寬度優(yōu)先的搜索和深度優(yōu)先的搜索　20
2．1．5　GenericSearch算法的正確性　22
2．2　寬度優(yōu)先的搜索和最短路徑　23
2．2．1　高層思路　23
2．2．2　BFS的偽碼　24
2．2．3　BFS的一個(gè)例子　25
2．2．4　正確性和運(yùn)行時(shí)間　27
2．2．5　最短路徑　28
2．2．6　小測驗(yàn)2．1的答案　31
2．3　計(jì)算連通分量　32
2．3．1　連通分量　32
2．3．2　連通分量的應(yīng)用　33
2．3．3　UCC（無向圖連通分量）算法　34
2．3．4　UCC算法的一個(gè)例子　35
2．3．5　UCC算法的正確性和運(yùn)行時(shí)間　36
2．3．6　小測驗(yàn)2．2的答案　37
2．4　深度優(yōu)先的搜索　37
2．4．1　DFS的一個(gè)例子　37
2．4．2　DFS的偽碼　39
2．4．3　正確性和運(yùn)行時(shí)間　41
2．5　拓?fù)渑判颉?1
2．5．1　拓?fù)漤樞颉?1
2．5．2　什么時(shí)候存在拓?fù)漤樞颉?3
2．5．3　計(jì)算拓?fù)漤樞颉?5
2．5．4　通過DFS的拓?fù)渑判颉?6
2．5．5　拓?fù)渑判虻囊粋€(gè)例子　47
2．5．6　正確性和運(yùn)行時(shí)間　48
2．5．7　小測驗(yàn)2．3和小測驗(yàn)2．4的答案　49
*2．6　計(jì)算強(qiáng)連通分量　50
2．6．1　強(qiáng)連通分量的定義　50
2．6．2　為什么要使用深度優(yōu)先的搜索　52
2．6．3　為什么要使用反轉(zhuǎn)的圖　53
2．6．4　Kosaraju的偽碼　57
2．6．5　一個(gè)例子　59
2．6．6　正確性和運(yùn)行時(shí)間　60
2．6．7　小測驗(yàn)2．5和小測驗(yàn)2．6的答案　60
2．7　Web的結(jié)構(gòu)　61
2．7．1　Web圖　62
2．7．2　蝴蝶結(jié)　63
2．7．3　主要發(fā)現(xiàn)　64
2．8　本章要點(diǎn)　65
2．9　章末習(xí)題　65
第3章　Dijkstra最短路徑算法　70
3．1　單源最短路徑問題　70
3．1．1　問題定義　70
3．1．2　一些前提條件　72
3．1．3　為什么不使用寬度優(yōu)先的搜索　72
3．1．4　小測驗(yàn)3．1的答案　73
3．2　Dijkstra算法　74
3．2．1　偽碼　74
3．2．2　一個(gè)例子　76
*3．3　為什么Dijkstra算法是正確的　77
3．3．1　一種虛假的簡化　77
3．3．2　Dijkstra算法的一個(gè)糟糕例子　78
3．3．3　非負(fù)邊長時(shí)的正確性　78
3．4　算法的實(shí)現(xiàn)及其運(yùn)行時(shí)間　82
3．5　本章要點(diǎn)　84
3．6　章末習(xí)題　84
第4章　堆數(shù)據(jù)結(jié)構(gòu)　88
4．1　數(shù)據(jù)結(jié)構(gòu)概述　88
4．1．1　選擇正確的數(shù)據(jù)結(jié)構(gòu)　88
4．1．2　進(jìn)入更高層次　89
4．2　堆所支持的操作　90
4．2．1　Insert和ExtractMin　91
4．2．2　其他操作　92
4．3　堆的應(yīng)用　93
4．3．1　應(yīng)用：排序　93
4．3．2　應(yīng)用：事件管理器　96
4．3．3　應(yīng)用：中位值維護(hù)　96
4．4　Dijkstra算法的提速　98
4．4．1　為什么要使用堆　98
4．4．2　計(jì)劃　99
4．4．3　維持不變性　101
4．4．4　運(yùn)行時(shí)間　103
*4．5　實(shí)現(xiàn)細(xì)節(jié)　104
4．5．1　樹形式的堆　104
4．5．2　數(shù)組形式的堆　106
4．5．3　在O (log n)時(shí)間內(nèi)實(shí)現(xiàn)Insert操作　107
4．5．4　在O (log n)時(shí)間內(nèi)實(shí)現(xiàn)ExtractMin操作　111
4．6　本章要點(diǎn)　114
4．7　章末習(xí)題　114
第5章　搜索樹　117
5．1　有序數(shù)組　117
5．1．1　有序數(shù)組支持的操作　117
5．1．2　有序數(shù)組不支持的操作　119
5．2　搜索樹支持的操作　120
*5．3　實(shí)現(xiàn)細(xì)節(jié)　122
5．3．1　搜索樹的屬性　122
5．3．2　搜索樹的高度　123
5．3．3　在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Search　124
5．3．4　在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Min和Max　125
5．3．5　在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Predecessor　126
5．3．6　在O(n)時(shí)間內(nèi)實(shí)現(xiàn)OutputSorted操作　127
5．3．7　在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Insert操作　128
5．3．8　在O（高度）時(shí)間內(nèi)實(shí)現(xiàn)Delete操作　129
5．3．9　強(qiáng)化的搜索樹支持Select操作　132
5．3．10　小測驗(yàn)5．1的答案　134
*5．4　平衡搜索樹　134
5．4．1　努力實(shí)現(xiàn)更好的平衡　134
5．4．2　旋轉(zhuǎn)　135
5．5　本章要點(diǎn)　137
5．6　章末習(xí)題　138
第6章　散列表和布隆過濾器　140
6．1　支持的操作　140
6．2　散列表的應(yīng)用　143
6．2．1　應(yīng)用：消除重復(fù)　144
6．2．2　應(yīng)用：兩數(shù)之和問題　145
6．2．3　應(yīng)用：搜索巨大的狀態(tài)空間　147
6．2．4　小測驗(yàn)6．2的答案　148
*6．3　實(shí)現(xiàn)的高層思路　148
6．3．1　兩個(gè)簡單的解決方案　148
6．3．2　散列函數(shù)　149
6．3．3　沖突是不可避免的　150
6．3．4　解決沖突的方法：鏈地址法　152
6．3．5　解決沖突的方法：開放地址法　153
6．3．6　良好的散列函數(shù)是怎么樣的　156
6．3．7　小測驗(yàn)6．3至小測驗(yàn)6．5的答案　160
*6．4　更多的實(shí)現(xiàn)細(xì)節(jié)　162
6．4．1　負(fù)載和性能　162
6．4．2　管理散列表的負(fù)載　164
6．4．3　選擇散列函數(shù)　165
6．4．4　選擇沖突解決策略　166
6．4．5　小測驗(yàn)6．6的答案　166
6．5　布隆過濾器的基礎(chǔ)知識(shí)　166
6．5．1　布隆過濾器支持的操作　167
6．5．2　布隆過濾器的應(yīng)用　169
6．5．3　布隆過濾器的實(shí)現(xiàn)　169
*6．6　布隆過濾器的啟發(fā)式分析　172
6．6．1　啟發(fā)式假設(shè)　172
6．6．2　部分位被設(shè)置為1　174
6．6．3　假陽性率　175
6．6．4　結(jié)束語　176
6．6．5　小測驗(yàn)6．7的答案　177
6．7　本章要點(diǎn)　178
6．8　章末習(xí)題　179
附錄　快速回顧漸進(jìn)性表示法　181
部分習(xí)題答案　187