Contents
13.1 Graphs | 594 |
13.1.1 The Graph ADT | 599 |
13.2 Data Structures for Graphs | 600 |
13.2.1 The Edge List Structure | 600 |
13.2.2 The Adjacency List Structure | 603 |
13.2.3 The Adjacency Matrix Structure | 605 |
13.3 Graph Traversals | 607 |
13.3.1 Depth-First Search | 607 |
13.3.2 Implementing Depth-First Search | 611 |
13.3.3 A Generic DFS Implementation in C++ | 613 |
13.3.4 Polymorphic Objects and Decorator Values * | 621 |
13.3.5 Breadth-First Search | 623 |
13.4 Directed Graphs | 626 |
13.4.1 Traversing a Digraph | 628 |
13.4.2 Transitive Closure | 630 |
13.4.3 Directed Acyclic Graphs | 633 |
13.5 Shortest Paths | 637 |
13.5.1 Weighted Graphs | 637 |
13.5.2 Dijkstra's Algorithm | 639 |
13.6 Minimum Spanning Trees | 645 |
13.6.1 Kruskal's Algorithm | 647 |
13.6.2 The Prim-Jarník Algorithm | 651 |
13.7 Exercises | 654 |
A graph is a way of representing relationships that exist between pairs of objects. That is, a graph is a set of objects, called vertices, together with a collection of pairwise connections between them. This notion of a "graph" should not be confused with bar charts and function plots, as these kinds of "graphs" are unrelated to the topic of this chapter. Graphs have applications in a host of different domains, including mapping, transportation, electrical engineering, and computer networks.
Viewed abstractly, a graph G is simply a set V of vertices and a collection E of pairs of vertices from V, called edges. Thus, a graph is a way of representing ...
No credit card required