Can we transform a graph in a way that applying DFS to the new graph would result in the same traversal order as applying BFS on the first graph?

Question

This question is purely theoretical.

Let's say you have a graph A, a Depth-First Search algorithm and a Breadth-First Search that both searches a graph for nodes matching a given predicate and returning the list of matching nodes in the order they have been encountered during the graph traversal.

My question is :

Does there exists a graph B such that applying the DFS algorithm to it would give you the same result as if we applied a Breadth-First Search algorithm to graph A ?

IE The list of matching nodes returned by the BFS algorithm on graph A is the same list of nodes (same nodes in the same order) returned by the DFS algorithm applied to graph B.

And if so, what algorithm is able to transform graph A into graph B ?

If such graph B does not exists in general, for any graph A, does one exists if we put restrictions on which graph A are allowed ? (such as no cycles for example, ie being a tree)

PS: The problem formulated like this make me think of the illustration of functors, thus the category-theory tag.

EDIT: Now that I have seen that a trivial solution to my question exists, I realize that my actual question is rather in the specific case of infinite graphs. I thought that asking if there was a solution in general would cover it, but that was before I saw the linked-list solution which seems to be only applicable on finite graphs.

Answer 1

Let's leave A out of this, since the only thing which is interesting is the sequence of nodes in the breadth-first traverse of A: v₁, v₂, v₃, …, v_n.

Then the question is, can we create a graph whose depth-first traverse must be exactly the sequence v₁, v₂, v₃, …, v_n? And clearly we can: the nodes of the graph are {v₁, v₂, v₃, …, v_n} and its edges are {< v_i, v_i+1> for i ∈ {1, …, n−1} } (It's breadth-first traverse is the same.)

Another trivial algorithm is to take any graph B' with n nodes, and do a depth-first traverse on it. Say the result is the sequence u₁, u₂, u₃, …, u_n. Then construct the graph B from B' by renaming every u_i as v_i, which will have the effect of changing the breadth-first traverse to match the breadth-first traverse of A.