Algorithms in C, Part 5 : Graph Algorithms, 3/e (Paperback)
暫譯: C 語言演算法，第 5 部分：圖形演算法，第三版（平裝本）

Robert Sedgewick

Algorithms in C, Part 5 : Graph Algorithms, 3/e (Paperback)

買這商品的人也買了...

商品描述

Graph algorithms are increasingly critical for a wide range of applications, such as network connectivity, circuit design, scheduling, transaction processing, and resource allocation. In the third edition, many new algorithms are presented, and the explanations of each algorithm are much more detailed than in previous editions. A new text design and detailed, innovative figures, with accompanying commentary, greatly enhance the presentation. Source code for the implementations is available via the Internet.

Table of Contents

Preface.
Notes on Exercises.
17. Graph Properties and Types.

Glossary.
Graph ADT.
Adjacency-Matrix Representation.
Adjacency-Lists Representation.
Variations, Extensions, and Costs.
Graph Generators.
Simple, Euler, and Hamilton Paths.
Graph-Processing Problems.


18. Graph Search.

Exploring a Maze.
Depth-First Search.
Graph-Search ADT Functions.
Properties of DFS Forests.
DFS Algorithms.
Separability and Biconnectivity.
Breadth-First Search.
Generalized Graph Search.
Analysis of Graph Algorithms.


19. Digraphs and DAGs.

Glossary and Rules of the Game.
Anatomy of DFS in Digraphs.
Reachability and Transitive Closure.
Equivalence Relations and Partial Orders.
DAGs.
Topological Sorting.
Reachability in DAGs.
Strong Components in Digraphs.
Transitive Closure Revisited.
Perspective.


20. Minimum Spanning Trees.

Representations.
Underlying Principles of MST Algorithms.
Prim's Algorithm and Priority-First Search.
Kruskal's Algorithm.
Boruvka's Algorithm.
Comparisons and Improvements.
Euclidean MST.


21. Shortest Paths.

Underlying Principles.
Dijkstra's algorithm.
All-Pairs Shortest Paths.
Shortest Paths in Acyclic Networks.
Euclidean Networks.
Reduction.
Negative Weights.
Perspective.


22. Network Flows.

Flow Networks.
Augmenting-Path Maxflow Algorithms.
Preflow-Push Maxflow Algorithms.
Maxflow Reductions.
Mincost Flows.
Network Simplex Algorithm.
Mincost-Flow Reductions.
Perspective.


References for Part Five.
Index

商品描述(中文翻譯)

圖形演算法在各種應用中變得越來越重要，例如網路連接、電路設計、排程、交易處理和資源分配。在第三版中，介紹了許多新的演算法，並且每個演算法的解釋比之前的版本更為詳細。全新的文本設計和詳細、創新的圖示，配合說明，極大地增強了內容的呈現。實作的源代碼可透過互聯網獲得。

目錄

前言。
練習題註解。
17. 圖形屬性與類型。

詞彙表。
圖形抽象資料型別 (Graph ADT)。
鄰接矩陣表示法 (Adjacency-Matrix Representation)。
鄰接列表表示法 (Adjacency-Lists Representation)。
變體、擴展與成本。
圖形生成器。
簡單路徑、歐拉路徑與哈密頓路徑。
圖形處理問題。

18. 圖形搜尋。
探索迷宮。
深度優先搜尋 (Depth-First Search)。
圖形搜尋抽象資料型別函數。
DFS 樹的性質。
DFS 演算法。
可分性與雙連通性。
廣度優先搜尋 (Breadth-First Search)。
廣義圖形搜尋。
圖形演算法分析。

19. 有向圖與有向無環圖 (DAG)。
詞彙表與遊戲規則。
有向圖中 DFS 的解剖。
可達性與傳遞閉包。
等價關係與部分序。
有向無環圖 (DAG)。
拓撲排序。
DAG 中的可達性。
有向圖中的強連通分量。
重新探討傳遞閉包。
觀點。

20. 最小生成樹。
表示法。
最小生成樹演算法的基本原則。
普里姆演算法 (Prim's Algorithm) 與優先搜尋。
克魯斯克爾演算法 (Kruskal's Algorithm)。
博魯夫卡演算法 (Boruvka's Algorithm)。
比較與改進。
歐幾里得最小生成樹。

21. 最短路徑。
基本原則。
迪傑斯特拉演算法 (Dijkstra's algorithm)。
所有對最短路徑。
無環網路中的最短路徑。
歐幾里得網路。
簡化。
負權重。
觀點。

22. 網路流。
流網路。
增廣路徑最大流演算法。
預流推進最大流演算法。
最大流簡化。
最小成本流。
網路單純形演算法。
最小成本流簡化。
觀點。

第五部分的參考文獻。
索引

類似商品