Database Reference
In-Depth Information
8.1.1. Depth-first
Everytimeyouvisitanode,youneedtodecidewhichrelationshiptofollownext,orwhich
nodes to hop to next. Depth-first ordering says that you should first hop to the first child of
the node you're currently on that hasn't been visited before. If all descendant nodes have
alreadybeenvisited,youshouldgobackwardstothefirstnodethathasachildyouhaven't
yet visited.
Figure 8.2
illustrates the order of visits to each node using depth-first traversal.
Figure 8.2. Walking the graph using depth-first ordering
You start the traversal at node 1. Node 1 has relationships to three other nodes (2, 3, and
4) and you're going to visit the first child node you haven't visited before—in this case,
node 2. You can imagine the traverser as a little robot that jumps from node 1 to node 2 via
relationship
a
.
Once you inspect node 2, you have to decide where to go next. Remember the depth-first
rule: visit a child of the node that hasn't been visited before, if one is available. So you'll
make the next hop from node 2 to node 5 (via relationship
b
). In only two hops, you've
