1
$\begingroup$

It seems intuitive, and is actually proven in many books, that each path from starting vertex to another one in any search tree of a breadth-first algorithm is the shortest. However, I couldn't find anything about the opposite statement: is any tree, containing all the graph vertices, where exist a vertex such as any path from it is the shortest, actually a search tree of a breadth-first algorithm applied to this graph. It's not so intuitive, so I even don't know for sure is it true or false. Could anyone clarify this point?

$\endgroup$

1 Answer 1

3
$\begingroup$

The answer is no. For example, let your graph $G = (V,E)$ be defined as \begin{align} V &= \{a,b_1,b_2,c_1,c_2\},\\ G &= \{a \to b_i, b_j \to c_k\} \text{ for any }i,j,k \in \{1,2\}. \end{align}

Then $$T = \{a\to b_1, a\to b_2, b_1\to c_1, b_2\to c_2\}$$ is a tree that has your property (every path is the shortest), but this cannot be a result of BFS since visiting $b_1$ first would imply $b_1 \to c_i$ and visiting $b_2$ first would imply $b_2 \to c_j$.

$\hspace{70pt}$bfs

I hope this helps ;-)

$\endgroup$
6
  • $\begingroup$ Yes, this helped =) And isn't there any similar statement, maybe with some additional restrictions on the tree, but which is true? $\endgroup$
    – aplavin
    Apr 2, 2013 at 19:59
  • 1
    $\begingroup$ Well, yes, this restriction is: it is a result of some BFS run :-P More seriously (only slightly more), you could say that, for some given total order $\preceq$ on $V \times V$ we have that each path is not only the shortest, but from all the shortest you pick the smallest with respect to lexicographic order induced by $\preceq$. This only slightly more serious, because it is BFS stated in different words. The corresponding BFS run is just the standard BFS run that considers vertices in the given order $\preceq$. $\endgroup$
    – dtldarek
    Apr 2, 2013 at 20:14
  • $\begingroup$ Is total order really necessary for BFS? Can't we just take a random vertex from list of adjacent ones on each step? $\endgroup$
    – aplavin
    Apr 2, 2013 at 20:18
  • 1
    $\begingroup$ Yeah, you can. It is enough to have a total order on each level of the tree (and by picking a random vertex you indeed construct this order). Still, any such partial order (total on each level) can be extended to some total order on $V \times V$, also any total order implies the partial order that is total on each level. I'm glad it is clear for you how this and the BFS are almost the same. $\endgroup$
    – dtldarek
    Apr 2, 2013 at 20:21
  • 1
    $\begingroup$ @chersanya Note, that any BFS run will give you some corresponding total order, that is, it will be the order in which the algorithm considers vertices. $\endgroup$
    – dtldarek
    Apr 2, 2013 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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