Algorithms in a Nutshell

Chapter 6. Graph Algorithms

Overview

Graphs are fundamental structures used in computer science to represent complex structured information. The images in Figure 6-1 are all sample graphs.

Figure 6-1. (a) House of Tudor, (b) computer network, (c) airline schedule

In this chapter we investigate common ways to represent graphs and some associated algorithms that occur frequently. Inherently, a graph contains a set of elements, known as vertices, and relationships between pairs of these elements, known as edges. In this chapter we consider only simple graphs that avoid (a) self-edges from a vertex to itself, and (b) multiple edges between the same pair of vertices.

Graphs

A graph G = (V, E) is defined by a set of vertices, V, and a set of edges, E, over pairs of these vertices. There are distinct types of graphs that occur commonly in algorithms:

Undirected graphs

Model relationships between vertices (u, v) without caring about the direction of the relationship. These graphs are useful for capturing symmetric information. For example, a road from town A to town B can be traversed in either direction.

Directed graphs

Model relationships between vertices (u,v) that are distinct from, say, the relationship between (v, u), which may or may not exist. For example, a program to provide driving directions must store information on one-way streets to avoid giving illegal directions.

Weighted graphs ...