Contents xvii Programs 309 Notes and References 309 7 Graphs and Graph Traversals 313 7.】Introduction314 7.2 Definitions and Representations 314 7.3 Traversing Graphs 328 7.4 Depth-First Search on Directed Graphs 336 7.5 Strongly Connected Components of a Directed Graph 357 7.6 Depth-First Search on Undirected Graphs 364 7.7 Biconnected Components of an Undirected Graph 366 Exercises 375 Programs 384 Notes and References 385 8 Graph Optimization Problems and Greedy Algorithms 387 8.1 Introduction 388 8.2 Prim's Minimum Spanning Tree Algorithm 388 8.3 Single-Source Shortest Paths 403 8.4 Kruskal's Minimum Spanning Tree Algorithm 412 Exercises 416 Programs 421 Notes and References 422 9 Transitive Closure,All-Pairs Shortest Paths 425 9.1 Introduction 426 9.2 The Transitive Closure of a Binary Relation 426 9.3 Warshall's Algorithm for Transitive Closure 430 9.4 All-Pairs Shortest Paths in Graphs 433 9.5 Computing Transitive Closure by Matrix Operations 436 9.6 Multiplying Bit Matrices-Kronrod's Algorithm 439 Exercises 446 Programs 449 Notes and References 449 10 Dynamic Programming 451 10.1 Introduction 452 10.2 Subproblem Graphs and Their Traversal 453 10.3 Multiplying a Sequence of Matrices 457