圖論算法理論、實現及應用

內容概要

本書選取經典的ACM/ICPC競賽題目為例闡述圖論算法思想，側重于圖論算法的程序實現及圖論算法的應用。本書分為上、下兩冊。上冊為第1～5章，其中第1章介紹圖論基本概念和圖的兩種存儲表示方法：鄰接矩陣和鄰接表，第2～5章分別討論圖的遍歷與活動網絡，樹與生成樹問題，最短路徑問題，可行遍性問題。下冊為第6～9章，分別討論網絡流問題，圖的連通性，點支配集、點覆蓋集、點獨立集、邊覆蓋集、邊獨立集（匹配），平面圖與圖的著色問題等等。本書可以作為高等院校計算機（或相關專業(yè)）圖論等相關課程的教材，也可作為ACM/ICPC競賽的輔導教材。

書籍目錄

第1章  圖的基本概念及圖的存儲  1.1  基本概念    1.1.1  有向圖與無向圖    1.1.2  完全圖、稀疏圖、稠密圖    1.1.3  頂點與頂點、頂點與邊的關系    1.1.4  頂點的度數及度序列    1.1.5  二部圖與完全二部圖    1.1.6  圖的同構    1.1.7  子圖與生成樹    1.1.8  路徑    1.1.9  連通性    1.1.10  權值、有向網與無向網  1.2  圖的存儲表示    1.2.1  鄰接矩陣    1.2.2  鄰接表    1.2.3  關于鄰接矩陣和鄰接表的進一步討論   練習第2章  圖的遍歷與活動網絡問題  2.1  DFS遍歷    2.1.1  DFS算法思想    2.1.2  DFS算法的實現及復雜度分析    2.1.3  例題解析    練習  2.2  BFS遍歷    2.2.1  BFS算法思想    2.2.2  BFS算法的實現及復雜度分析    2.2.3  關于DFS算法和BFS算法的說明    2.2.4  例題解析    練習  2.3  活動網絡——AOV網絡    2.3.1  AOV網絡與拓撲排序    2.3.2  拓撲排序實現方法    2.3.3  關于拓撲排序的進一步說明    2.3.4  例題解析    練習  2.4  活動網絡——AOE網絡    2.4.1  AOE網絡與關鍵路徑    2.4.2  關鍵路徑求解方法第3章  樹與圖的生成樹  3.1  樹與森林    3.1.1  樹    3.1.2　森林  3.2  生成樹及最小生成樹    3.2.1  生成樹    3.2.2最小生成樹  3.3  克魯斯卡爾(Kruskal)算法    3.3.1  Kruskal算法思想    3.3.2  等價類與并查集    3.3.3  Kruskal算法實現    3.3.4  Boruvka算法    3.3.5  例題解析    練習  3.4 普里姆(Prim)算法    3.4.1  Prim算法思想    3.4.2  Prim算法實現    3.4.3  關于Prim算法的進一步討論    3.4.4  例題解析    練習  3.5  判定最小生成樹是否唯一    3.5.1  最小生成樹不唯一的原因分析    3.5.2  判定最小生成樹是否唯一的方法    3.5.3  例題解析第4章　最短路徑問題第5章　可行遍性問題第6章　網絡流問題第7章　支配集、覆蓋集、獨立集與匹配第8章　圖的連通性問題第9章　平面圖及圖的著色問題附錄　本書例題和練習題目錄索引參考文獻

章節(jié)摘錄

版權頁：插圖：在本題中，每個單詞只有首尾兩個字母很關鍵，并且每個單詞可以看成連接首尾兩個字母的一條有向邊（由首字母指向尾字母）。這樣每個測試數據中的一組單詞可以構造成一個圖：圖中的頂點為26個小寫字母，每個單詞為圖中的一條邊。例如，本題樣例輸入中兩個測試數據所構造的有向圖如圖5.7所示。構造好有向圖后，題目要判定是否可以經過重組使得每個單詞的第1個字母跟前一個單詞最后一個字母相同，等效于判斷圖中是否存在一條路徑經過每條邊一次且僅一次，這就是有向歐拉通路。本題的處理方法如下。   （1）讀入每個單詞時，因為每個單詞相當于一條從首字母指向尾字母的邊，所以對單詞首字母對應的頂點，出度加1；尾字母對應的頂點，入度加1。（2）26個頂點的入度和出度都統(tǒng)計完畢后，根據各項點的出度、入度關系來判斷是否存在歐拉通路，但要注意排除每個單詞的首尾字母中沒有出現過的字母。在下面的代碼中，用bused數組來表示每個字母是否在單詞的首尾中出現。例如，在圖5.7（a）中，只有3個字母對應有頂點，其他23個字母都沒有對應頂點。

編輯推薦

《圖論算法理論、實現及應用》：21世紀全國應用型本科計算機案例型規(guī)劃教材

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    圖論算法理論、實現及應用 PDF格式下載

---