Database Reference
In-Depth Information
Figure 8.1. Simple graph with nine nodes and eight relationships
The graph in
figure 8.1
has nine nodes. It represents a tree, which is a graph type where
each two nodes are connected via a single path. In other words, a tree is a graph without
any cycles. To make our illustration of traversal ordering simpler, we'll use the tree graph
as an example. (For an example of a graph with cycles, and therefore not a tree, see
figure
The root node of the graph is marked as 1. Nodes directly connected to the root node
(branches)aremarked2,3,and4.Therestofthenodes(leaves)aretworelationshipsaway
from the root node (nodes 5-9).
Let's look at the differences between walking this graph using the depth-first and breadth-
first traversal orderings. Our goal is to walk the graph so that we visit each node in the
graph exactly once.
