Поиск в глубину - Как конечный граф может генерировать бесконечное дерево

Question

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

Может кто-нибудь объяснить или показать картину того, как конечный граф может генерировать бесконечное дерево.

Answer 1

Самый простой граф будет с одним узлом и одним ребром:

nodes: n
edges: (n, n)

Тогда у вас будет бесконечно глубокое дерево:

 n
 |
 n
 |
 n
 |
...

Чтобы избежать этого, вы должны "пометить" узлы, которые вы посетили. Правильный алгоритм будет обладать этим особым качеством, благодаря которому дерево будет иметь точно такое же количество узлов, что и остров, содержащий выбранный корневой узел. Это также называется связующим деревом.

В Википедии вы можете прочитать:

Каждый конечный связный граф имеет остовное дерево. (omissis)

Answer 2

Это то же самое, что и отношение между программой (конечным графом) и пространством вещей, которые она может писать или читать. Рассмотрим простой парсер рекурсивного спуска. Это конечно, но потоки, которые он может анализировать, не ограничены (включая бесконечные потоки).