Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 8 down vote favorite
2

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?

share|improve this question
5  
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. – templatetypedef Aug 20 '12 at 4:49
1  
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. – Luke Mathieson Aug 20 '12 at 8:38
2  
@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. – saadtaame Aug 20 '12 at 9:51
2  
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. – Luke Mathieson 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. – saadtaame Aug 20 '12 at 17:48
show 3 more comments

1 Answer

up vote 4 down vote

Assume our BFS and dfs has a rule to start from specific node and in each two-way they first visit node with lowest degree:

DFS-BFS

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

share|improve this answer
   
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. – saadtaame 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. – Niel de Beaudrap Aug 22 '12 at 0:00
1  
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. – Saeed Amiri Nov 8 '12 at 16:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.