算法VC实现 图算法 原版风暴系列 第3版·影印版PDF电子书下载

Graph Algorithms 3

Chapter 17．Graph Properties and Types 3

17.1 Glossary 7

17.2 Graph ADT 16

17.3 Adjacency-Matrix Representation 21

17.4 Adjacency-Lists Representation 27

17.5 Variations,Extensions,and Costs 31

17.6 Graph Generators 40

17.7 Simple,Euler,and Hamilton Paths 50

17.8 Graph-Processing Problems 64

Chapter 18．Graph Search 75

18.1 Exploring a Maze 76

18.2 Depth-First Search 81

18.3 Graph-Search ADT Functions 86

18.4 Properties of DFS Forests 91

18.5 DFS Algorithms 99

18.6 Separability and Biconnectivity 106

18.7 Breadth-First Search 114

18.8 Generalized Graph Search 124

18.9 Analysis of Graph Algorithms 133

Chapter 19．Digraphs and DAGs 141

19.1 Glossary and Rules of the Game 144

19.2 Anatomy of DFS in Digraphs 152

19.3 Reachability and Transitive Closure 161

19.4 Equivalence Relations and Partial Orders 174

19.5 DAGs 178

19.6 Topological Sorting 183

19.7 Reachability in DAGs 193

19.8 Strong Components in Digraphs 196

19.9 Transitive Closure Revisited 208

19.10 Perspective 212

Chapter 20．Minimum Spanning Trees 219

20.1 Representations 222

20.2 Underlying Principles of MST Algorithms 228

20.3 Prim's Algorithm and Priority-First Search 235

20.4 Kruskal's Algorithm 246

20.5 Boruvka's Algorithm 252

20.6 Comparisons and Improvements 255

20.7 Euclidean MST 261

Chapter 21．Shortest Paths 265

21.1 Underlying Principles 273

21.2 Dijkstra's algorithm 280

21.3 All-Pairs Shortest Paths 290

21.4 Shortest Paths in Acyclic Networks 300

21.5 Euclidean Networks 308

21.6 Reduction 314

21.7 Negative Weights 331

21.8 Perspective 350

Chapter 22．Network Flows 353

22.1 Flow Networks 359

22.2 Augmenting-Path Maxflow Algorithms 370

22.3 Preflow-Push Maxflow Algorithms 396

22.4 Maxflow Reductions 411

22.5 Mincost Flows 429

22.6 Network Simplex Algorithm 439

22.7 Mincost-Flow Reductions 457

22.8 Perspective 467

References for Part Five 473

Index 475