掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
算法詳解 卷2 圖算法和數據結構 版權信息
- ISBN：9787115526038
- 條形碼：9787115526038 ; 978-7-115-52603-8
- 裝幀：平裝-膠訂
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
算法詳解 卷2 圖算法和數據結構 本書特色
算法詳解系列圖書共有4卷，本書是第2卷—圖算法和數據結構。本書共有6章，主要介紹了3個主題，分別是圖的搜索和應用、*短路徑以及數據結構。附錄簡單回顧了漸進性表示法。本書的每一章均有小測驗、章末習題，這為讀者的自我檢查以及進一步學習提供了方便。 本書提供了豐富而實用的資料，能夠幫助讀者提升算法思維能力。本書適合計算機專業的高校教師和學生，想要培養和訓練算法思維和計算思維的IT專業人士，以及正在準備面試的應聘者和面試官閱讀參考。
算法詳解 卷2 圖算法和數據結構 內容簡介
算法詳解系列圖書共有4卷，本書是第2卷—圖算法和數據結構。本書共有6章，主要介紹了3個主題，分別是圖的搜索和應用、很短路徑以及數據結構。附錄簡單回顧了漸進性表示法。本書的每一章均有小測驗、章末習題，這為讀者的自我檢查以及進一步學習提供了方便。 本書提供了豐富而實用的資料，能夠幫助讀者提升算法思維能力。本書適合計算機專業的高校教師和學生，想要培養和訓練算法思維和計算思維的IT專業人士，以及正在準備面試的應聘者和面試官閱讀參考。
算法詳解 卷2 圖算法和數據結構 目錄
第1章 圖的基礎知識 1
1.1 基本術語 1
1.2 圖的一些應用 2
1.3 圖形的度量 3
1.3.1 圖的邊數量 3
1.3.2 稀疏圖和稠密圖 4
1.3.3 小測驗1.1的答案 5
1.4 圖的表示方法 7
1.4.1 鄰接列表 7
1.4.2 鄰接矩陣 8
1.4.3 圖的表示形式之間的比較 9
1.4.4 小測驗1.2和小測驗1.3的答案 10
1.5 本章要點 11
1.6 章末習題 12
第2章 圖的搜索及其應用 14
2.1 概述 14
2.1.1 一些應用 15
2.1.2 零代價的基本算法 16
2.1.3 通用的圖搜索算法 17
2.1.4 寬度優先的搜索和深度優先的搜索 20
2.1.5 GenericSearch算法的正確性 22
2.2 寬度優先的搜索和*短路徑 23
2.2.1 高層思路 23
2.2.2 BFS的偽碼 24
2.2.3 BFS的一個例子 25
2.2.4 正確性和運行時間 27
2.2.5 *短路徑 28
2.2.6 小測驗2.1的答案 31
2.3 計算連通分量 32
2.3.1 連通分量 32
2.3.2 連通分量的應用 33
2.3.3 UCC（無向圖連通分量）算法 34
2.3.4 UCC算法的一個例子 35
2.3.5 UCC算法的正確性和運行時間 36
2.3.6 小測驗2.2的答案 37
2.4 深度優先的搜索 37
2.4.1 DFS的一個例子 37
2.4.2 DFS的偽碼 39
2.4.3 正確性和運行時間 41
2.5 拓撲排序 41
2.5.1 拓撲順序 41
2.5.2 什么時候存在拓撲順序 43
2.5.3 計算拓撲順序 45
2.5.4 通過DFS的拓撲排序 46
2.5.5 拓撲排序的一個例子 47
2.5.6 正確性和運行時間 48
2.5.7 小測驗2.3和小測驗2.4的答案 49
*2.6 計算強連通分量 50
2.6.1 強連通分量的定義 50
2.6.2 為什么要使用深度優先的搜索 52
2.6.3 為什么要使用反轉的圖 53
2.6.4 Kosaraju的偽碼 57
2.6.5 一個例子 59
2.6.6 正確性和運行時間 60
2.6.7 小測驗2.5和小測驗2.6的答案 60
2.7 Web的結構 61
2.7.1 Web圖 62
2.7.2 蝴蝶結 63
2.7.3 主要發現 64
2.8 本章要點 65
2.9 章末習題 65
第3章 Dijkstra*短路徑算法 70
3.1 單源*短路徑問題 70
3.1.1 問題定義 70
3.1.2 一些前提條件 72
3.1.3 為什么不使用寬度優先的搜索 72
3.1.4 小測驗3.1的答案 73
3.2 Dijkstra算法 74
3.2.1 偽碼 74
3.2.2 一個例子 76
*3.3 為什么Dijkstra算法是正確的 77
3.3.1 一種虛假的簡化 77
3.3.2 Dijkstra算法的一個糟糕例子 78
3.3.3 非負邊長時的正確性 78
3.4 算法的實現及其運行時間 82
3.5 本章要點 84
3.6 章末習題 84
第4章 堆數據結構 88
4.1 數據結構概述 88
4.1.1 選擇正確的數據結構 88
4.1.2 進入更高層次 89
4.2 堆所支持的操作 90
4.2.1 Insert和ExtractMin 91
4.2.2 其他操作 92
4.3 堆的應用 93
4.3.1 應用：排序 93
4.3.2 應用：事件管理器 96
4.3.3 應用：中位值維護 96
4.4 Dijkstra算法的提速 98
4.4.1 為什么要使用堆 98
4.4.2 計劃 99
4.4.3 維持不變性 101
4.4.4 運行時間 103
*4.5 實現細節 104
4.5.1 樹形式的堆 104
4.5.2 數組形式的堆 106
4.5.3 在O (log n)時間內實現Insert操作 107
4.5.4 在O (log n)時間內實現ExtractMin操作 111
4.6 本章要點 114
4.7 章末習題 114
第5章 搜索樹 117
5.1 有序數組 117
5.1.1 有序數組支持的操作 117
5.1.2 有序數組不支持的操作 119
5.2 搜索樹支持的操作 120
*5.3 實現細節 122
5.3.1 搜索樹的屬性 122
5.3.2 搜索樹的高度 123
5.3.3 在O（高度）時間內實現Search 124
5.3.4 在O（高度）時間內實現Min和Max 125
5.3.5 在O（高度）時間內實現Predecessor 126
5.3.6 在O(n)時間內實現OutputSorted操作 127
5.3.7 在O（高度）時間內實現Insert操作 128
5.3.8 在O（高度）時間內實現Delete操作 129
5.3.9 強化的搜索樹支持Select操作 132
5.3.10 小測驗5.1的答案 134
*5.4 平衡搜索樹 134
5.4.1 努力實現更好的平衡 134
5.4.2 旋轉 135
5.5 本章要點 137
5.6 章末習題 138
第6章 散列表和布隆過濾器 140
6.1 支持的操作 140
6.2 散列表的應用 143
6.2.1 應用：消除重復 144
6.2.2 應用：兩數之和問題 145
6.2.3 應用：搜索巨大的狀態空間 147
6.2.4 小測驗6.2的答案 148
*6.3 實現的高層思路 148
6.3.1 兩個簡單的解決方案 148
6.3.2 散列函數 149
6.3.3 沖突是不可避免的 150
6.3.4 解決沖突的方法：鏈地址法 152
6.3.5 解決沖突的方法：開放地址法 153
6.3.6 良好的散列函數是怎么樣的 156
6.3.7 小測驗6.3至小測驗6.5的答案 160
*6.4 更多的實現細節 162
6.4.1 負載和性能 162
6.4.2 管理散列表的負載 164
6.4.3 選擇散列函數 165
6.4.4 選擇沖突解決策略 166
6.4.5 小測驗6.6的答案 166
6.5 布隆過濾器的基礎知識 166
6.5.1 布隆過濾器支持的操作 167
6.5.2 布隆過濾器的應用 169
6.5.3 布隆過濾器的實現 169
*6.6 布隆過濾器的啟發式分析 172
6.6.1 啟發式假設 172
6.6.2 部分位被設置為1 174
6.6.3 假陽性率 175
6.6.4 結束語 176
6.6.5 小測驗6.7的答案 177
6.7 本章要點 178
6.8 章末習題 179
附錄 快速回顧漸進性表示法 181
部分習題答案 187
1.1 基本術語 1
1.2 圖的一些應用 2
1.3 圖形的度量 3
1.3.1 圖的邊數量 3
1.3.2 稀疏圖和稠密圖 4
1.3.3 小測驗1.1的答案 5
1.4 圖的表示方法 7
1.4.1 鄰接列表 7
1.4.2 鄰接矩陣 8
1.4.3 圖的表示形式之間的比較 9
1.4.4 小測驗1.2和小測驗1.3的答案 10
1.5 本章要點 11
1.6 章末習題 12
第2章 圖的搜索及其應用 14
2.1 概述 14
2.1.1 一些應用 15
2.1.2 零代價的基本算法 16
2.1.3 通用的圖搜索算法 17
2.1.4 寬度優先的搜索和深度優先的搜索 20
2.1.5 GenericSearch算法的正確性 22
2.2 寬度優先的搜索和*短路徑 23
2.2.1 高層思路 23
2.2.2 BFS的偽碼 24
2.2.3 BFS的一個例子 25
2.2.4 正確性和運行時間 27
2.2.5 *短路徑 28
2.2.6 小測驗2.1的答案 31
2.3 計算連通分量 32
2.3.1 連通分量 32
2.3.2 連通分量的應用 33
2.3.3 UCC（無向圖連通分量）算法 34
2.3.4 UCC算法的一個例子 35
2.3.5 UCC算法的正確性和運行時間 36
2.3.6 小測驗2.2的答案 37
2.4 深度優先的搜索 37
2.4.1 DFS的一個例子 37
2.4.2 DFS的偽碼 39
2.4.3 正確性和運行時間 41
2.5 拓撲排序 41
2.5.1 拓撲順序 41
2.5.2 什么時候存在拓撲順序 43
2.5.3 計算拓撲順序 45
2.5.4 通過DFS的拓撲排序 46
2.5.5 拓撲排序的一個例子 47
2.5.6 正確性和運行時間 48
2.5.7 小測驗2.3和小測驗2.4的答案 49
*2.6 計算強連通分量 50
2.6.1 強連通分量的定義 50
2.6.2 為什么要使用深度優先的搜索 52
2.6.3 為什么要使用反轉的圖 53
2.6.4 Kosaraju的偽碼 57
2.6.5 一個例子 59
2.6.6 正確性和運行時間 60
2.6.7 小測驗2.5和小測驗2.6的答案 60
2.7 Web的結構 61
2.7.1 Web圖 62
2.7.2 蝴蝶結 63
2.7.3 主要發現 64
2.8 本章要點 65
2.9 章末習題 65
第3章 Dijkstra*短路徑算法 70
3.1 單源*短路徑問題 70
3.1.1 問題定義 70
3.1.2 一些前提條件 72
3.1.3 為什么不使用寬度優先的搜索 72
3.1.4 小測驗3.1的答案 73
3.2 Dijkstra算法 74
3.2.1 偽碼 74
3.2.2 一個例子 76
*3.3 為什么Dijkstra算法是正確的 77
3.3.1 一種虛假的簡化 77
3.3.2 Dijkstra算法的一個糟糕例子 78
3.3.3 非負邊長時的正確性 78
3.4 算法的實現及其運行時間 82
3.5 本章要點 84
3.6 章末習題 84
第4章 堆數據結構 88
4.1 數據結構概述 88
4.1.1 選擇正確的數據結構 88
4.1.2 進入更高層次 89
4.2 堆所支持的操作 90
4.2.1 Insert和ExtractMin 91
4.2.2 其他操作 92
4.3 堆的應用 93
4.3.1 應用：排序 93
4.3.2 應用：事件管理器 96
4.3.3 應用：中位值維護 96
4.4 Dijkstra算法的提速 98
4.4.1 為什么要使用堆 98
4.4.2 計劃 99
4.4.3 維持不變性 101
4.4.4 運行時間 103
*4.5 實現細節 104
4.5.1 樹形式的堆 104
4.5.2 數組形式的堆 106
4.5.3 在O (log n)時間內實現Insert操作 107
4.5.4 在O (log n)時間內實現ExtractMin操作 111
4.6 本章要點 114
4.7 章末習題 114
第5章 搜索樹 117
5.1 有序數組 117
5.1.1 有序數組支持的操作 117
5.1.2 有序數組不支持的操作 119
5.2 搜索樹支持的操作 120
*5.3 實現細節 122
5.3.1 搜索樹的屬性 122
5.3.2 搜索樹的高度 123
5.3.3 在O（高度）時間內實現Search 124
5.3.4 在O（高度）時間內實現Min和Max 125
5.3.5 在O（高度）時間內實現Predecessor 126
5.3.6 在O(n)時間內實現OutputSorted操作 127
5.3.7 在O（高度）時間內實現Insert操作 128
5.3.8 在O（高度）時間內實現Delete操作 129
5.3.9 強化的搜索樹支持Select操作 132
5.3.10 小測驗5.1的答案 134
*5.4 平衡搜索樹 134
5.4.1 努力實現更好的平衡 134
5.4.2 旋轉 135
5.5 本章要點 137
5.6 章末習題 138
第6章 散列表和布隆過濾器 140
6.1 支持的操作 140
6.2 散列表的應用 143
6.2.1 應用：消除重復 144
6.2.2 應用：兩數之和問題 145
6.2.3 應用：搜索巨大的狀態空間 147
6.2.4 小測驗6.2的答案 148
*6.3 實現的高層思路 148
6.3.1 兩個簡單的解決方案 148
6.3.2 散列函數 149
6.3.3 沖突是不可避免的 150
6.3.4 解決沖突的方法：鏈地址法 152
6.3.5 解決沖突的方法：開放地址法 153
6.3.6 良好的散列函數是怎么樣的 156
6.3.7 小測驗6.3至小測驗6.5的答案 160
*6.4 更多的實現細節 162
6.4.1 負載和性能 162
6.4.2 管理散列表的負載 164
6.4.3 選擇散列函數 165
6.4.4 選擇沖突解決策略 166
6.4.5 小測驗6.6的答案 166
6.5 布隆過濾器的基礎知識 166
6.5.1 布隆過濾器支持的操作 167
6.5.2 布隆過濾器的應用 169
6.5.3 布隆過濾器的實現 169
*6.6 布隆過濾器的啟發式分析 172
6.6.1 啟發式假設 172
6.6.2 部分位被設置為1 174
6.6.3 假陽性率 175
6.6.4 結束語 176
6.6.5 小測驗6.7的答案 177
6.7 本章要點 178
6.8 章末習題 179
附錄 快速回顧漸進性表示法 181
部分習題答案 187
展開全部
算法詳解 卷2 圖算法和數據結構 作者簡介
蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大學計算機科學系的教授,也是該校管理科學和工程系的客座教授，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第一卷，基于他從2012年開始定期舉行的在線算法課程編寫。
書友推薦
- >
小考拉的故事-套裝共3冊
- >
經典常談
- >
唐代進士錄
- >
二體千字文
- >
企鵝口袋書系列·偉大的思想20:論自然選擇(英漢雙語)
- >
伯納黛特,你要去哪(2021新版)
- >
苦雨齋序跋文-周作人自編集
- >
李白與唐代文化
本類暢銷
