# Graphs that cause DFS and BFS to process nodes in the exact same order

For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-shaped (trees of depth $1$ with an arbitrary number of children). Is there some way for categorizing graphs that satisfy this property?

• Note that in both cases this only works if you start at some specific node. If you pick a central node in a long path, for example, you will get back different orderings from DFS and BFS. Aug 20 '12 at 4:49
• Are there any other interesting possibilities than a star or a path? At first glance it would seem that if you had a vertex with both a sibling and a child then you immediately get different traversals, so either no vertex has children (apart from the root) and you get a star, or no vertex has a sibling and you get a path. I guess a clique also works, but it has both the star and path embedded. Aug 20 '12 at 8:38
• @LukeMathieson I'm thinking of a star with the rightmost child being the root of another star. I guess that would work as well. We can even make a general statement: if $G = (V,E)$ satisfies the property when the search starts at node v∈V, then so does a star whose rightmost child $= v$. Even better, if $G_1$ and $G_2$ satisfy the property and node $v_1$ is the last one processed in $G_1$ and $v_2$ is where the search starts in $G_2$, then adding the bridge edge $(v_1, v_2)$ creates a graph that satisfies the property. Replacing $v_1$ by $v_2$ also works I think.
– mrk
Aug 20 '12 at 9:51
• Good point, so there's some sort of right-recursive composition where you could identify the right leaf of the first graph with the root of the second. Aug 20 '12 at 11:53
• @LukeMathieson It looks like you can fix the case where a node $v$ has a sibling and a child by adding an edge between that child and the parent of $v$. Here is my proposition: Given a graph $G=(V,E)$. $\forall x \in V$, if $\exists y,z,w \in V$ such that $(y,x),(z,y),(x,w) \in E$, then $(x,z) \in E \implies$ the property holds for $G$. The next step is to prove or disprove this proposition.
– mrk
Aug 20 '12 at 17:48

Assume our BFS and DFS have the rule to start from a specific node and both of them then visit the node with the lowest degree:

Start from left most black node, then both (BFS and DFS) traversals will visit left most red node, then they will visit next black node, and so on. To make it more general, you could add some paths in between triangles, or add star after finishing triangles.

• That's correct under your assumption. You raised a good point actually; we should specify in what order are the nodes added to the agenda (stack or queue) when faced with a choice.
– mrk
Aug 21 '12 at 17:37
• Bearing in mind that LIFO and FIFO for scheduling yield DFS and BFS respectively, one might argue that scheduling such as this (in which the scheduling may not either be stack- or queue-like) is neither depth- nor breadth-first search — though you can in some cases describe its tendancy to resemble one or the other. Aug 22 '12 at 0:00
• I think it can be implemented in terms of a stack or queue. It doesn't change how things are taken off (LIFO or FIFO), it changes the order in which children are added (in this case, lowest degree first).
– SamM
Aug 22 '12 at 6:57
• @NieldeBeaudrap actually this is just a structure to show that somewhere both ways are same.
– user742
Nov 8 '12 at 16:45