Полнота поиска в глубину

Я цитирую из Искусственный интеллект: современный подход :

Свойства поиска в глубину сильно зависят от того, поиск по графу или поиск по дереву версия используется. Версия с поиском по графу, которая избегает повторяющихся состояний и избыточных путей, завершена в пространствах конечных состояний, потому что в конечном итоге она расширяет каждый узел. Версия поиска по дереву, с другой стороны, не завершена [...].Поиск по дереву в глубину можно изменить без дополнительных затрат памяти, чтобы он сравнивал новые состояния с состояниями на пути от корня к текущему узлу; это позволяет избежать бесконечных циклов в пространствах конечных состояний, но не позволяет избежать увеличения числа избыточных путей.

Я не понимаю, как поиск по графу может быть полным, а поиск по дереву - нет, если дерево является конкретным графом.

Кроме того, я не совсем понимаю разницу между «бесконечными циклами» и «избыточными путями» ...

Может кто-нибудь мне это объяснит?

пс. Для тех, у кого есть книга, это 86-я страница (3-е издание).