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