A graph G=(V,E) consists of a set of vertices V
together with a set E of
vertex pairs or edges.
Graphs are important because they
can be used to represent essentially any relationship.
For example, graphs can model a network of roads,
with cities as vertices and roads between cities as edges, as shown in
Figure 
.
Electronic circuits
can also be modeled as graphs,
with junctions as vertices and components as edges.
Figure: Modeling road networks and electronic circuits as graphs
The key to understanding many algorithmic problems is to think of them in terms of graphs. Graph theory provides a language for talking about the properties of graphs, and it is amazing how often messy applied problems have a simple description and solution in terms of classical graph properties.
Designing truly novel graph algorithms is a very difficult task. The key to using graph algorithms effectively in applications lies in correctly modeling your problem as a standard graph property, so you can take advantage of existing algorithms. Becoming familiar with many different graph algorithmic problems is more important than understanding the details of particular graph algorithms, particularly since Part II of this book can point you to an implementation as soon as you know the name of your problem.
In this chapter, we will present basic data structures and traversal operations for graphs, which will enable you to cobble together solutions to rudimentary graph problems. We will also describe more sophisticated algorithms for problems like shortest paths and minimum spanning trees in some detail. But we stress the primary importance of correctly modeling your problem. Time spent browsing through the catalog now will leave you better informed of your options when a real job arises.
The take-home lessons of this chapter include: