圖論算法理論、實現(xiàn)及應(yīng)用

內(nèi)容概要

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

書籍目錄

第1章  圖的基本概念及圖的存儲  1.1  基本概念    1.1.1  有向圖與無向圖    1.1.2  完全圖、稀疏圖、稠密圖    1.1.3  頂點與頂點、頂點與邊的關(guān)系    1.1.4  頂點的度數(shù)及度序列    1.1.5  二部圖與完全二部圖    1.1.6  圖的同構(gòu)    1.1.7  子圖與生成樹    1.1.8  路徑    1.1.9  連通性    1.1.10  權(quán)值、有向網(wǎng)與無向網(wǎng)  1.2  圖的存儲表示    1.2.1  鄰接矩陣    1.2.2  鄰接表    1.2.3  關(guān)于鄰接矩陣和鄰接表的進一步討論   練習(xí)第2章  圖的遍歷與活動網(wǎng)絡(luò)問題  2.1  DFS遍歷    2.1.1  DFS算法思想    2.1.2  DFS算法的實現(xiàn)及復(fù)雜度分析    2.1.3  例題解析    練習(xí)  2.2  BFS遍歷    2.2.1  BFS算法思想    2.2.2  BFS算法的實現(xiàn)及復(fù)雜度分析    2.2.3  關(guān)于DFS算法和BFS算法的說明    2.2.4  例題解析    練習(xí)  2.3  活動網(wǎng)絡(luò)——AOV網(wǎng)絡(luò)    2.3.1  AOV網(wǎng)絡(luò)與拓?fù)渑判?   2.3.2  拓?fù)渑判驅(qū)崿F(xiàn)方法    2.3.3  關(guān)于拓?fù)渑判虻倪M一步說明    2.3.4  例題解析    練習(xí)  2.4  活動網(wǎng)絡(luò)——AOE網(wǎng)絡(luò)    2.4.1  AOE網(wǎng)絡(luò)與關(guān)鍵路徑    2.4.2  關(guān)鍵路徑求解方法第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算法實現(xiàn)    3.3.4  Boruvka算法    3.3.5  例題解析    練習(xí)  3.4 普里姆(Prim)算法    3.4.1  Prim算法思想    3.4.2  Prim算法實現(xiàn)    3.4.3  關(guān)于Prim算法的進一步討論    3.4.4  例題解析    練習(xí)  3.5  判定最小生成樹是否唯一    3.5.1  最小生成樹不唯一的原因分析    3.5.2  判定最小生成樹是否唯一的方法    3.5.3  例題解析第4章　最短路徑問題第5章　可行遍性問題第6章　網(wǎng)絡(luò)流問題第7章　支配集、覆蓋集、獨立集與匹配第8章　圖的連通性問題第9章　平面圖及圖的著色問題附錄　本書例題和練習(xí)題目錄索引參考文獻

章節(jié)摘錄

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

編輯推薦

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

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    圖論算法理論、實現(xiàn)及應(yīng)用 PDF格式下載

---