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?
$\begingroup$
$\endgroup$
8
-
6$\begingroup$ 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. $\endgroup$– templatetypedefAug 20, 2012 at 4:49
-
1$\begingroup$ 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. $\endgroup$– Luke MathiesonAug 20, 2012 at 8:38
-
2$\begingroup$ @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. $\endgroup$– mrkAug 20, 2012 at 9:51
-
2$\begingroup$ 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. $\endgroup$– Luke MathiesonAug 20, 2012 at 11:53
-
$\begingroup$ @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. $\endgroup$– mrkAug 20, 2012 at 17:48
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ 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. $\endgroup$– mrkAug 21, 2012 at 17:37
-
$\begingroup$ 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. $\endgroup$ Aug 22, 2012 at 0:00
-
1$\begingroup$ 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). $\endgroup$– SamMAug 22, 2012 at 6:57
-
$\begingroup$ @NieldeBeaudrap actually this is just a structure to show that somewhere both ways are same. $\endgroup$– user742Nov 8, 2012 at 16:45