how to find the original directed graph?

Question

I was thinking on a homework question given to me, it is as follows: If you are given with a BFS and DFS traversal of a directed( or un-directed graph), how would you find the original graph ? Is it possible in either case?

thankyou

Answer 1

If I understand it correctly, it is not possible, since BFS and DFS produce a tree, and tree has |V|-1 edges. So, in these two trees you have at most 2|V|-2 different edges, and original graph can have up to |V|(|V|-1) edges for directed, and |V|(|V|-1)/2 for undirected graph.