Почему при реализации обхода в глубину нужно проверять вершины на предмет повторных посещений?

При реализации обхода в глубину нужно проверять вершины на предмет повторных посещений, чтобы предотвратить бесконечную рекурсию. spravochnick.ru foxford.ru

Это происходит из-за того, что если из одной вершины можно перейти в другую, то и в обратную сторону, и рекурсия может стать бесконечной. spravochnick.ru Чтобы решить проблему, нужно не проходить в ту вершину, в которой уже был исследователь, то есть которая уже не представляет для него интерес. spravochnick.ru foxford.ru

Для реализации алгоритма необходимо отмечать, какие вершины уже посещал исследователь, а какие ещё нет. spravochnick.ru Это можно сделать при помощи списка visited, где visited[i] == True для посещённых вершин, и visited[i] == false для непосещённых. foxford.ru