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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .