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

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

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

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

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

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

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