¿En qué tipos de gráfico DFS y BFS producirán el mismo árbol (misma fuente) independientemente de la secuencia de visitas de los vecinos?
Hay dos respuestas posibles para su pregunta. Todo depende de cómo se defina el “mismo árbol”.
Primera respuesta posible
- ¿Cómo analizaría la complejidad temporal de fibbonacci?
- ¿Cuál es la complejidad del tiempo para la escalera de palabras?
- Cómo guardar un árbol binario en una matriz de recorrido en orden
- Cómo resolver el problema SPOJ XORROUND
- ¿Cuáles son los mejores libros para aprender estructuras de datos y algoritmos para un principiante con poco lenguaje de programación de C?
Asumiré que ambos árboles tienen que ser idénticos. Por ejemplo:
Los árboles anteriores son iguales.
Los árboles anteriores, por otro lado, no lo son.
¿Qué pasaría si el nodo fuente [math] s [/ math] tuviera dos (o más) hijos?
El BFS podría visitar el nodo [math] a [/ math] primero y el DFS podría visitar el nodo [math] b [/ math] primero (o viceversa). Entonces, si queremos garantizar que DFS y BFS produzcan árboles idénticos, el nodo fuente debe tener como máximo un hijo.
El mismo argumento se aplica recursivamente porque [math] s_1 [/ math] ahora es el nodo fuente.
Significa que el gráfico original tiene que ser algún tipo de “lista vinculada” (finita o no).
Otra forma de visualizar es darse cuenta de que el bucle for es un caso especial de recorrido de gráfico cuando BFS y DFS son iguales, porque tanto la cola como la pila funcionan de la misma manera.
Segunda respuesta posible
¿Qué pasa si relajamos la definición? Ambos árboles ya no tienen que ser idénticos, sino isomórficos.
Los árboles anteriores son “lo mismo” porque son isomorfos.
Deje de leer mi respuesta ahora y ejecute BFS y DFS para el gráfico de abajo, con y sin el borde discontinuo (para el nodo fuente [math] a [/ math]).
Si el gráfico no tiene ciclos, entonces lo único que cambió entre DFS y BFS es qué niños visita primero. Si el gráfico tiene ciclos, todo se vuelve un desastre y no podemos predecir nada.
Por lo tanto, en este segundo caso, el BFS y el DFS producen el “mismo árbol” si el gráfico original ya es un árbol.
