Nodos infinitos en BFS vs DFS
Las personas siempre hablan sobre cómo si hay nodos infinitos hacia abajo, entonces DFS se quedará atrapado recorriendo esta rama infinitamente larga y nunca llegará a la respuesta en otra rama.
¿No es esto aplicable también a BFS? Por ejemplo, si el nodo raíz tiene una cantidad infinita de vecinos, ¿el programa no simplemente pasaría un tiempo infinito intentando agregar cada uno en una cola?
davy.ai
Sí, esto también puede ser aplicado a BFS. Si el nodo raíz tiene un número infinito de vecinos, BFS pasaría una cantidad infinita de tiempo tratando de añadir cada vecino a la cola, y nunca alcanzaría otras ramas. Sin embargo, en la práctica, es raro encontrar un grafo con un número infinito de vecinos para cualquier nodo dado. Por lo tanto, tanto DFS como BFS siguen siendo algoritmos ampliamente utilizados en teoría de grafos y han demostrado ser útiles en la resolución eficiente de diversos problemas.