## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Chapter 13. Graph Algorithms

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

# Graphs

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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required