Database Reference
In-Depth Information
made it to the deepest point in the graph—from the root node (node 1) to node 5. This is
why the depth-first algorithm is named that: you're traversing the graph so that you go as
deep as you can, as soon as you can.
Now that you're on node 5, you should go to its child node, but node 5 is a leaf in the
graph, so it doesn't have any child nodes to hop to. In that case, the depth-first algorithm
has a rule that says to go backwards to the first node that has a descendant that hasn't been
visited before. You return to node 2 and then apply the original rule. Node 2 has two des-
cendants (nodes 5 and 6), and you've already visited node 5, so the next stop is node 6 (via
relationship
c
).
Using the same rules, you'll end up walking the graph in the following order of nodes:
1 → 2 → 5 → 6 → 3 → 7 → 8 → 4 → 9
If you're looking at
figure 8.2
,
you've hopped via relationships
a
,
b
,
c
,
d
,
e
,
f
,
g,
and
h
dur-
ing the traversal, in that order.
It's interesting to realize that you visited node 4 next to last, although that node is very
close to the root node, the starting point. You'll also notice that youvisited the nodes in the
left part of the graph (nodes 1, 2, 5, and 6) much sooner than the nodes in the right part of
the graph (nodes 4, 8, and 9). This is a consequence of the depth-first traversal, and you
should use it to your advantage when modeling a graph and designing the traversals. We'll
discuss this again when we compare the depth-first and breadth-first orderings.
The question now is how we can make use of the depth-first algorithm in the Neo4j
TraversalAPI.Let'sdojustthat:implementthetraversalwejustdescribedusingtheNeo4j
Traversal API. You can see the solution in the following listing.
