Cito de Inteligencia artificial: un enfoque moderno:

Las propiedades de la búsqueda en profundidad dependen en gran medida de si se utiliza la versión de búsqueda de gráficos o de búsqueda de árbol. La versión de búsqueda de gráficos, que evita estados repetidos y rutas redundantes, se completa en espacios de estado finito porque eventualmente expandirá cada nodo. La versión de búsqueda de árbol, por otro lado, esn completo [...]. La búsqueda en primer árbol en profundidad se puede modificar sin costo de memoria adicional para que compruebe los nuevos estados con los que se encuentran en la ruta desde la raíz hasta el nodo actual; esto evita bucles infinitos en espacios de estado finito pero no evita la proliferación de rutas redundantes.

No entiendo cómo puede ser completa la búsqueda de gráficos y no puede ser la búsqueda de árbol, siendo un árbol un gráfico particular.

Además, no entiendo claramente la diferencia entre "bucles infinitos" y "rutas redundantes" ...

¿Puede alguien explicarme esto?

PD. Para aquellos que tienen el libro, es la página 86 (3ª edición).