¿Podemos transformar un gráfico de tal manera que aplicar DFS al nuevo gráfico resultaría en el mismo orden de recorrido que aplicar BFS en el primer gráfico?

Esta pregunta es puramente teórica.

Digamos que tienes un grafo A, un algoritmo de búsqueda en profundidad (DFS, por sus siglas en inglés) y una búsqueda en amplitud (BFS, por sus siglas en inglés) que buscan en el grafo los nodos que coinciden con un predicado dado y devuelven la lista de nodos coincidentes en el orden en que se encontraron durante el recorrido del grafo.

Mi pregunta es:

¿Existe un grafo B tal que aplicar el algoritmo DFS a él nos dé el mismo resultado que si aplicáramos un algoritmo BFS al grafo A?

Es decir, ¿la lista de nodos coincidentes devuelta por el algoritmo BFS en el grafo A es la misma lista de nodos (los mismos nodos en el mismo orden) devuelta por el algoritmo DFS aplicado al grafo B?

Y si es así, ¿qué algoritmo puede transformar el grafo A en el grafo B?

Si dicho grafo B no existe en general, ¿existe alguno si se imponen restricciones en el grafo A permitido? (como por ejemplo, no tener ciclos, es decir, ser un árbol)

PD: El problema formulado de esta manera me hace pensar en la ilustración de funtores, de ahí la etiqueta de teoría de categorías.

EDIT:
Ahora que he visto que existe una solución trivial para mi pregunta, me doy cuenta de que mi pregunta real se refiere más al caso específico de grafos infinitos. Pensé que al preguntar si había una solución en general se incluiría, pero eso fue antes de ver la solución de la lista enlazada que parece ser solo aplicable a grafos finitos.