相關商品
商品簡介
目次
商品簡介
《圖論算法理論、實現及應用》系統地介紹了圖論算法理論，并選取經典的ACM／ICPC競賽題目為例題闡述圖論算法思想，側重于圖論算法的程序實現及應用。《圖論算法理論、實現及應用》第1章介紹圖的基本概念和圖的兩種存儲表示方法：鄰接矩陣和鄰接表，第2～9章分別討論圖的遍歷與活動網絡問題，樹與圖的生成樹，最短路徑問題，可行遍性問題，網絡流問題，支配集、覆蓋集、獨立集與匹配，圖的連通性問題，平面圖及圖的著色問題等。
《圖論算法理論、實現及應用》可以作為高等院校計算機（或相關專業）圖論等相關課程的主教材，也可作為ACM／ICPC競賽的輔導教材。
《圖論算法理論、實現及應用》可以作為高等院校計算機（或相關專業）圖論等相關課程的主教材，也可作為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章 最短路徑問題
4.1 邊上權值非負情形的單源最短路徑問題——Dijkstra算法
4.1.1 算法思想
4.1.2 算法實現
4.1.3 關於Dijkstra算法的進一步討論
4.1.4例題解析
練習
4.2 邊上權值為任意值的單源最短路徑問題——Bellman-Ford算法
4.2.1 算法思想
4.2.2 算法實現.
4.2.3 關於Bellman-Ford算法的進一步討論
4.2.4 例題解析
練習
4.3 Bellman-Ford算法的改進——SPFA算法
4.3.1 算法思想
4.3.2 算法實現
4.3.3 關於SPFA算法的進一步討論
4.3.4 例題解析
練習
4.4 所有頂點之間的最短路徑——Floyd算法
4.4.1 算法思想
4.4.2 算法實現
4.4.3 關於Floyd算法的進一步分析
4.4.4 例題解析
練習
4.5 差分約束系統
4.5.1 差分約束系統與最短路徑
4.5.2 例題解析
練習
第5章 可行遍性問題
5.1 歐拉回路
5.1.1 基本概念及定理
5.1.2 歐拉回路的判定
練習
5.2 歐拉回路的求解
5.2.1 DFS搜索求解歐拉回路
5.2.2 Fleury（佛羅萊）算法
練習
5.3 中國郵遞員問題
5.4 漢密爾頓回路
5.4.1 基本概念及定理
5.4.2 漢密爾頓回路求解
第6章 網絡流問題
6.1 網絡最大流
6.1.1 基本概念
6.1.2 最大流最小割定理
6.1.3 網絡最大流的求解
6.1.4 一般增廣路方法——Ford-Fulkerson算法
6.1.5 最短增廣路算法
6.1.6 連續最短增廣路算法——Dinic算法
6.1.7 一般預流推進算法
6.1.8 最高標號預流推進算法
6.1.9 網絡最大流算法總結
6.1.10 例題解析
練習
6.2 最小割的求解
練習
6.3 流量有上下界的網絡的最大流和最小流
6.3.1 流量有上下界的容量網絡
6.3.2 流量有上下界的網絡的最大流
6.3.3 流量有上下界的網絡的最小流
6.3.4 例題解析
練習
6.4 最小費用最大流
6.4.1 基本概念
6.4.2 最小費用最大流算法
6.4.3 例題解析
練習
第7章 支配集、覆蓋集、獨立集與匹配
7.1 點支配集、點覆蓋集、點獨立集
7.1.1 點支配集
7.1.2 點覆蓋集
7.1.3 點獨立集
7.1.4 點支配集、點覆蓋集、點獨立集之間的聯系
7.2 點支配集、點覆蓋集、點獨立集的求解
7.2.1 邏輯運算
7.2.2 極小點支配集的求解
7.2.3 極小點覆蓋集、極大點獨立集的求解
7.3 邊覆蓋集與邊獨立集
7.3.1 邊覆蓋集
7.3.2 邊獨立集（匹配）
7.3.3 最大邊獨立集（最大匹配）與最小邊覆蓋集之間的聯系
7.4 匹配問題
7.4.1 完美匹配
7.4.2 二部圖的完備匹配與完美匹配
7.4.3 最佳匹配
7.4.4 匹配問題求解的基本概念及思路
7.5 二部圖最大匹配問題的求解
7.5.1 網絡流解法
7.5.2 匈牙利算法
7.5.3 例題解析
練習
第8章 圖的連通性問題
8.1 基本概念
8.1.1 連通圖與非連通圖
8.1.2 無向圖的點連通性
8.1.3 無向圖的邊連通性
8.1.4 無向圖頂點連通性和邊連通性的聯系
8.1.5 有向圖的連通性
8.2 無向圖點連通性的求解及應用
8.2.1 關節點的求解
8.2.2 重連通分量的求解
8.2.3 頂點連通度的求解
練習
8.3 無向圖邊連通性的求解及應用
8.3.1 割邊的求解
8.3.2 邊雙連通分量的求解
8.3.3 邊連通度的求解
練習
8.4 有向圖強連通性的求解及應用
8.4.1 有向圖強連通分量的求解算法
8.4.2 有向圖強連通分量的應用
練習
第9章 平面圖及圖的著色問題
9.1 基本概念
9.1.1 平面圖與非平面圖
9.1.2 區域與邊界
9.1.3 極大平面圖與極小非平面圖
9.1.4 平面圖的對偶圖
9.1.5 關於平面圖的一些定理
9.2 歐拉公式及其應用
9.2.1 歐拉公式
9.2.2 歐拉公式的應用
練習
9.3 平面圖的判定
9.4 圖的著色問題
9.4.1 地圖染色與四色猜想
9.4.2 圖的著色
9.4.3 圖著色的應用
9.4.4 圖著色求解算法及例題解析
練習
附錄 本書例題和練習題目錄
索引
參考文獻
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章 最短路徑問題
4.1 邊上權值非負情形的單源最短路徑問題——Dijkstra算法
4.1.1 算法思想
4.1.2 算法實現
4.1.3 關於Dijkstra算法的進一步討論
4.1.4例題解析
練習
4.2 邊上權值為任意值的單源最短路徑問題——Bellman-Ford算法
4.2.1 算法思想
4.2.2 算法實現.
4.2.3 關於Bellman-Ford算法的進一步討論
4.2.4 例題解析
練習
4.3 Bellman-Ford算法的改進——SPFA算法
4.3.1 算法思想
4.3.2 算法實現
4.3.3 關於SPFA算法的進一步討論
4.3.4 例題解析
練習
4.4 所有頂點之間的最短路徑——Floyd算法
4.4.1 算法思想
4.4.2 算法實現
4.4.3 關於Floyd算法的進一步分析
4.4.4 例題解析
練習
4.5 差分約束系統
4.5.1 差分約束系統與最短路徑
4.5.2 例題解析
練習
第5章 可行遍性問題
5.1 歐拉回路
5.1.1 基本概念及定理
5.1.2 歐拉回路的判定
練習
5.2 歐拉回路的求解
5.2.1 DFS搜索求解歐拉回路
5.2.2 Fleury（佛羅萊）算法
練習
5.3 中國郵遞員問題
5.4 漢密爾頓回路
5.4.1 基本概念及定理
5.4.2 漢密爾頓回路求解
第6章 網絡流問題
6.1 網絡最大流
6.1.1 基本概念
6.1.2 最大流最小割定理
6.1.3 網絡最大流的求解
6.1.4 一般增廣路方法——Ford-Fulkerson算法
6.1.5 最短增廣路算法
6.1.6 連續最短增廣路算法——Dinic算法
6.1.7 一般預流推進算法
6.1.8 最高標號預流推進算法
6.1.9 網絡最大流算法總結
6.1.10 例題解析
練習
6.2 最小割的求解
練習
6.3 流量有上下界的網絡的最大流和最小流
6.3.1 流量有上下界的容量網絡
6.3.2 流量有上下界的網絡的最大流
6.3.3 流量有上下界的網絡的最小流
6.3.4 例題解析
練習
6.4 最小費用最大流
6.4.1 基本概念
6.4.2 最小費用最大流算法
6.4.3 例題解析
練習
第7章 支配集、覆蓋集、獨立集與匹配
7.1 點支配集、點覆蓋集、點獨立集
7.1.1 點支配集
7.1.2 點覆蓋集
7.1.3 點獨立集
7.1.4 點支配集、點覆蓋集、點獨立集之間的聯系
7.2 點支配集、點覆蓋集、點獨立集的求解
7.2.1 邏輯運算
7.2.2 極小點支配集的求解
7.2.3 極小點覆蓋集、極大點獨立集的求解
7.3 邊覆蓋集與邊獨立集
7.3.1 邊覆蓋集
7.3.2 邊獨立集（匹配）
7.3.3 最大邊獨立集（最大匹配）與最小邊覆蓋集之間的聯系
7.4 匹配問題
7.4.1 完美匹配
7.4.2 二部圖的完備匹配與完美匹配
7.4.3 最佳匹配
7.4.4 匹配問題求解的基本概念及思路
7.5 二部圖最大匹配問題的求解
7.5.1 網絡流解法
7.5.2 匈牙利算法
7.5.3 例題解析
練習
第8章 圖的連通性問題
8.1 基本概念
8.1.1 連通圖與非連通圖
8.1.2 無向圖的點連通性
8.1.3 無向圖的邊連通性
8.1.4 無向圖頂點連通性和邊連通性的聯系
8.1.5 有向圖的連通性
8.2 無向圖點連通性的求解及應用
8.2.1 關節點的求解
8.2.2 重連通分量的求解
8.2.3 頂點連通度的求解
練習
8.3 無向圖邊連通性的求解及應用
8.3.1 割邊的求解
8.3.2 邊雙連通分量的求解
8.3.3 邊連通度的求解
練習
8.4 有向圖強連通性的求解及應用
8.4.1 有向圖強連通分量的求解算法
8.4.2 有向圖強連通分量的應用
練習
第9章 平面圖及圖的著色問題
9.1 基本概念
9.1.1 平面圖與非平面圖
9.1.2 區域與邊界
9.1.3 極大平面圖與極小非平面圖
9.1.4 平面圖的對偶圖
9.1.5 關於平面圖的一些定理
9.2 歐拉公式及其應用
9.2.1 歐拉公式
9.2.2 歐拉公式的應用
練習
9.3 平面圖的判定
9.4 圖的著色問題
9.4.1 地圖染色與四色猜想
9.4.2 圖的著色
9.4.3 圖著色的應用
9.4.4 圖著色求解算法及例題解析
練習
附錄 本書例題和練習題目錄
索引
參考文獻
您曾經瀏覽過的商品
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大，除封面破損、內頁脫落等較嚴重的狀態，其餘商品將正常出貨。
特別提醒：部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供，需以QR CODE 連結至當地網站註冊“並通過驗證程序”，方可下載使用。
無現貨庫存之簡體書，將向海外調貨：
海外有庫存之書籍，等候約45個工作天;
海外無庫存之書籍，平均作業時間約60個工作天，然不保證確定可調到貨，尚請見諒。
為了保護您的權益，「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨，請在商品鑑賞期內寄回，且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。