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.
how to find the original directed graph?
-
12-10-2022 - |
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
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow