This chapter shows you how to define, implement, and use algorithms that explore graphs, and it does so from the perspective of problem solving.

A **graph** *G* is a structure defined by:

• a set of nodes *S*;

• a set of arcs; that is, a subset *A* of the Cartesian product *S* × *S*.

This definition corresponds to the mathematical idea of a relation over a set *S*.

Graphs, in fact, constitute highly intuitive objects connected to ordinary experience. A subway map is a graph in which the nodes are subway stops; a road map is a graph in which the nodes are cities. Telecommunication networks (such as the telephone system or a computer network) provide other examples.

The intuitive character of a graph is reflected ...

Start Free Trial

No credit card required