Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Graphs

Graphs are more general and more complex than trees. Like trees, they consist of nodes with children — a tree is actually a special case of a graph. But unlike tree nodes, graph nodes (or vertices) can have multiple “parents,” possibly creating a loop (a cycle). In addition, the links between nodes, as well as the nodes themselves, may have values or weights. These links are called edges because they may contain more information than just a pointer. In a graph, edges can be one-way or two-way. A graph with one-way edges is called a directed graph. A graph with only two-way pointers is called an undirected graph. Figure 5-4 shows a directed graph, and Figure 5-5 shows an undirected graph.

Figure 5-4

Figure 5-5

Graphs are commonly used to model real-world problems that are difficult to model with other data structures. For example, a directed graph could represent the aqueducts connecting cities because water flows only one way. You might use such a graph to help you find the fastest way to get water from city A to city D. An undirected graph can represent something such as a series of relays in signal transmission.

There are several common ways to represent graph data structures. The best representation is often determined by the algorithm being implemented. One common ...