Traversals in depth - Neo4j in Action - page 180

Depth level Node location Depth-first Breadth-first

6 First on left side 6 364

6 Last on right side 796,068 1,092

9 First on left side 9 9,841

9 Last on right side 797,121 29,523

12 First on left side 12 265,720

12 Last on right side 797,160 797,160

As you can see from the table, when the result is close to the starting node, breadth-first
ordering will generally yield better performance. But further away from the starting node,
breadth-first ordering is always slow, and depth-first ordering can be extremely efficient,
depending on whether the resulting node is located in the left or right part of the graph.

Intheworst-casescenario,wheretheentiregraphneedstobetraversed(whentheresulting
node is in the bottom-right corner of the graph), both depth-first and breadth-first ordering
need to visit all nodes. But due to the larger memory footprint of breadth-first traversals,
it's better to use depth-first ordering in this case.

In addition to speed, another aspect you need to consider when deciding on the traversal
ordering is memory consumption of the traversals. Imagine once again that the traverser is
likealittle robotthatjumpsfromnodetonodeviarelationships. Thisrobotwillhavetore-
membersomestateaboutwhichnodeitcamefrom,andwhichnodesithasyettovisit.The
larger the graph, the more memory is needed to store that state. But the selected traversal
ordering affects the memory it needs. Let's see how.

When using depth-first ordering, you try to go deep into the graph as soon as you can. As
soonasyoucometothebottomofthegraph(visitanodethathasnodescendantsthathave
not been visited before), you can completely forget about that branch of the graph—from
thetraversalperspective,it'sconsideredcomplete.IntheNeo4jJavaworld,thatmeansyou
can dereference that path from memory and leave it for garbage collection cleanup. Be-
cause some of these paths will be visited early during the traversal, you can start deallocat-
ing memory as soon as you start traversing.

Breadth-first traversal tries to go as wide as it can in the graph, before starting with the
nodes on the next depth level. As a result, during traversal you need to remember all the
nodes you've visited and which descendants you haven't yet visited. The larger and more