Обход дерева легко, если дерево правильно сформировано.Вам не нужно отслеживать, собираетесь ли вы потенциально повторить какую-то работу в возможно бесконечном цикле, потому что есть ровно один путь для достижения каждого узла.
Но для обобщенного обхода графагде граф может содержать циклы, многие тривиальные алгоритмы будут заканчиваться бесконечным циклом, когда они сталкиваются с циклом.Чтобы гарантировать завершение таких алгоритмов, мы обычно хотим отслеживать, какие узлы мы посетили в течение всего обхода, а не повторно исследовать узел, который мы уже посетили.
Это цель visited collection (будь то массив, набор и т. Д. Не имеет значения).Альтернативы могут быть для каждого узла, чтобы иметь флаг посещения, который может быть сброшен перед обходом и установлен во время обхода.Это устраняет необходимость в глобальной коллекции, но накладывает свои собственные ограничения (одновременно может происходить только один обход).
Коллекция visited не обязательно должна быть "глобальной" 1 , но он должен находиться в общем объеме, который разделяют все части каждого обхода.
1 Если он "глобальный", то в любой области, которая имеет значение,снова возможен только один проход за раз.