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 edges is called an undirected graph. Figure 6-4 shows a directed graph, and Figure 6-5 shows an undirected graph.

FIGURE 6-4

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