Graphs

A graph is a set of nodes (or points) connected by edges (or arcs).

A simple example of a graph is a map of cities connected by roads. The cities are nodes; the roads are edges. Most questions you might pose about such a map can be posed in terms of operations on a graph. For example, finding the shortest route between two cities, or the shortest route that visits all cities, are common graph problems.

In fact, a wide variety of problems can be posed as operations on graphs, including network routing, city planning, VLSI layout, deadlock detection, and register allocation in a compiler.

As with most data structures, there are several different implementations of graphs, with different tradeoffs in time and space.

Several classical graph problems (and their solutions) have been studied extensively because they arise frequently in practical settings, including

• breadth-first and depth-first search
• single-source-shortest-path problem
• all-pairs-shortest-path problem
• transitive closure
• minimum spanning tree problem