Next: The Friendship Graph Up: Techniques Previous: Implementation Challenges

# Graph Algorithms

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:

• Graphs can be used to model a wide variety of structures and relationships.
• Properly formulated, most applications of graphs can be reduced to standard graph properties and using well-known algorithms. These include minimum spanning trees, shortest paths, and several problems presented in the catalog.
• Breadth-first and depth-first search provide mechanisms to visit each edge and vertex of the graph. They prove the basis of most simple, efficient graph algorithms.

Next: The Friendship Graph Up: Techniques Previous: Implementation Challenges

Algorithms
Mon Jun 2 23:33:50 EDT 1997