●章圖的基礎知識
1.1基本術語
1.2圖的一些應用
1.3圖形的度量
1.3.1圖的邊數量
1.3.2稀疏圖和稠密圖
1.3.3小測驗1.1的答案
1.4圖的表示方法
1.4.1鄰接列表
1.4.2鄰接矩陣
1.4.3圖的表示形式之間的比較
1.4.4小測驗1.2和小測驗1.3的答案
1.5本章要點
1.6章末習題
第2章圖的搜索及其應用
2.1概述
2.1.1一些應用
2.1.2零代價的基本算法
2.1.3通用的圖搜索算法
2.1.4寬度優先的搜索和深度優先的搜索
2.1.5GenericSearch算法的正確性
2.2寬度優先的搜索和最短路徑
2.2.1高層思路
2.2.2BFS的偽碼
2.2.3BFS的一個例子
2.2.4正確性和運行時間
2.2.5最短路徑
2.2.6小測驗2.1的答案
2.3計算連通分量
2.3.1連通分量
2.3.2連通分量的應用
2.3.3UCC（無向圖連通分量）算法
2.3.4UCC算法的一個例子
2.3.5UCC算法的正確性和運行時間
2.3.6小測驗2.2的答案
2.4深度優先的搜索
2.4.1DFS的一個例子
2.4.2DFS的偽碼
2.4.3正確性和運行時間
2.5拓撲排序
2.5.1拓撲順序
2.5.2什麼時候存在拓撲順序
2.5.3計算拓撲順序
2.5.4通過DFS的拓撲排序
2.5.5拓撲排序的一個例子
2.5.6正確性和運行時間
2.5.7小測驗2.3和小測驗2.4的答案
2.6計算強連通分量
2.6.1強連通分量的定義
2.6.2為什麼要使用深度優先的搜索
2.6.3為什麼要使用反轉的圖
2.6.4Kosaraju的偽碼
2.6.5一個例子
2.6.6正確性和運行時間
2.6.7小測驗2.5和小測驗2.6的答案
2.7Web的結構
2.7.1Web圖
2.7.2蝴蝶結
2.7.3主要發現
2.8本章要點
2.9章末習題
第3章Dijkstra最短路徑算法
3.1單源最短路徑問題
3.1.1問題定義
3.1.2一些前提條件
3.1.3為什麼不使用寬度優先的搜索
3.1.4小測驗3.1的答案
3.2Dijkstra算法
3.2.1偽碼
3.2.2一個例子
3.3為什麼Dijkstra算法是正確的
3.3.1一種虛假的簡化
3.3.2Dijkstra算法的一個糟糕例子
3.3.3非負邊長時的正確性
3.4算法的實現及其運
……
內容簡介
算法詳解繫列圖書共有4卷，本書是第2卷—圖算法和數據結構。本書共有6章，主要介紹了3個主題，分別是圖的搜索和應用、很短路徑以及數據結構。附錄簡單回顧了漸進性表示法。本書的每一章均有小測驗、章末習題，這為讀者的自我檢查以及進一步學習提供了方便。本書提供了豐富而實用的資料，能夠幫助讀者提升算法思維能力。本書適合計算機專業的高校教師和學生，想要培養和訓練算法思維和計算思維的IT專業人士，以及正在準備面試的應聘者和面試官閱讀參考。
