Equivalence of a graph and a BFS and DFS tree

Question

I have this problem which I am not able to prove. Can someone offer some insight into this problem

We have a connected graph G = (V,E), and as pecific vertex u ∈ V.Suppose we compute a depth-first search tree rooted at u, and obtain a tree T that includes all nodes of G. Suppose we then compute a breadth-first search tree rooted at u, and obtain the same tree T. Prove that G = T. (In other words, if T is both a depth-first search tree and a breadth-first search tree rooted at u, then G cannot contain any edges that do not belong to T.)

Solution 1

The proof is very simple once you understand BFS and DFS and the basic difference between them.

BFS VS DFS

The main difference between dfs and bfs is how they built the tree starting from root.The difference arises when once a vertex is visited,how the adjacent vertices are visited .Let us address each of the traversal 1 by 1 in a simple manner.

1.BFS

1.BFS starts by visiting the root.It then visits the vertices which are at a distance of 1 edge from root. Say there are 4 vertices a,b,c,d adjacent to root.Then bfs will visit these 4 vertices just after visiting root.

2.Once bfs is done visiting vertices at a distance of 1 edge from root. It then takes the first vertex visited after root and repeats the same procedure.Which vertex was the first one, this is handled by queue data structure.

This is the reason BFS is also called level order traversal, when you use it for traversing trees.Because it visits vertices level by level and levels are clearly defined in case of tree.

DFS

1.DFS starts by visiting the root. It will not visit all vertices adjacent to root after visiting root, but will go into the depth of graph.

2.Once it visits root, it visits only vertex adjacent to root and then will start dfs from that vertex itself, that is it goes into depth before visiting all vertices adjacent to root. It will only come to them once it has visited the vertices in depth of direction in which it started the dfs.

So important thing to observe is that BFS builds the tree in TOP DOWN fashion while DFS builds the tree in BOTTOM UP fashion

If the two trees are same then it is the case when your graph itself is tree.And the tree can only be of special two types.

This can only be true either for graph which is a skew trees like this:

root
|
|
V1
|
|
V2
|
|
.
.
.
Vn

In this case Both bfs and dfs goes in one direction.

Or a graph with star topology like this:

               V1
               /
              /
   Vn-----root------V2
          |  \
          |   \
          V4  V3

Proof By statement

Any other tree different from above two trees will be like where an intermediate vertex v exists at level x and it has more than 1 children(say 2) c1 and c2 at level x+1, What bfs will do is visit v and then c1 and c2, but what dfs will do is visit v and then c1 and then child of c1 so clearly the traversals wont be the same in these two cases.

Solution 2

From a Berkeley CS Course Solution

• Suppose the input graph G is undirected and connected but is not a tree.
• Then G must contain a cycle C. Suppose C consists of the k nodes v1, v2, ..., vk i.e. C is the cycle v1 → v2 → . . . → vk → v1.
• Now, in the DFS tree, nodes v1, v2, ..., vk will all be on the same path from the root to a leaf.
• Why? Suppose vf is the first of these nodes to be visited. Then, the remaining nodes must be visited at some point during explore(vf) since the other vi are all strongly connected.
• However, in the BFS tree, nodes v1, v2, ..., vk will form at least two branches, braching from the node first visited (imagine performing BFS on the cycle). Therefore, BFS and DFS produce the same tree iff the input graph is a tree.

Another approach by @dtldarek in math.stackechange:

• It is true, if the graph is simple, connected and undirected, and the very basic observation is that G is a tree if and only if every edge was traversed in the BFS/DFS search.
• Suppose that TBFS=T=TDFS, but that there is e∈E(G)∖E(T), that is, an edge that was not visited by any of the algorithms.
• The only reason the edge was not traversed could be that the vertex on the other side was already visited, but if there is a DFS-back-edge then BFS must have used it before.

Comments

[Ankit Mishra]

I didn't get the statement that DFS builds the tree in a bottom up fashion. Cause it doesn't go like building all the leaves and the one level up and so on till the top. It traverses the tree till its complete depth and then goes on to next neigbour of the root. So buttom up fashion is not clear to me. Can you explain this a bit. Because I am not able to see how all the leaves are visited first and then the next level and so on.

[Sumeet]

@AnkitMishra You are right, but what I meant was first lower levels of the tree are completed then the upper ones are completed.

[Ankit Mishra]

And also I get that for these two graphs. But lets take a general case, consider an edge (u,v) in G which is not there in T. How can I prove that this edge will also be there in T. I think this will prove it for any general case. If you can offer some explanation. It will be really great.