Breadth-first search tree

Question

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?

Answer 1

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}$

I hope this helps ;-)