Какие методы существуют для обхода вершин графа без повторений?

Некоторые методы обхода вершин графа:

• Обход в глубину (поиск в глубину, DFS). proglib.io education.yandex.ru Алгоритм заключается в систематическом просмотре вершин графа и прохождении его ветвями. education.yandex.ru Когда возможные пути по рёбрам, выходящим из вершин, разветвляются, нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными). education.yandex.ru

Алгоритм поиска в глубину: education.yandex.ru

1. Все вершины графа отмечают как не посещённые. education.yandex.ru Выбирается первая вершина и помечается как посещённая. education.yandex.ru
2. Для последней помеченной как посещённой вершины выбирается смежная вершина, которая первая помечена как не посещённая, и ей присваивается значение посещённой. education.yandex.ru Если таких вершин нет, то берётся предыдущая помеченная вершина. education.yandex.ru
3. Повторяют шаг 2 до тех пор, пока все вершины не будут помечены как посещённые. education.yandex.ru

• Обход в ширину (поиск в ширину, BFS). proglib.io education.yandex.ru Основное отличие этого способа обхода в том, что сначала исследуются смежные вершины, а уже потом вершины на следующем уровне. education.yandex.ru При этом для каждой вершины сразу находится длина кратчайшего маршрута от начальной вершины. education.yandex.ru

Алгоритм поиска в ширину: education.yandex.ru

1. Всем вершинам графа присваивается значение не посещённой. education.yandex.ru Выбирается первая вершина и помечается как посещённая и заносится в очередь. education.yandex.ru
2. Посещается первая вершина из очереди (если она не помечена как посещённая). education.yandex.ru Все её соседние вершины заносятся в очередь. education.yandex.ru После этого она удаляется из очереди. education.yandex.ru
3. Повторяется шаг 2 до тех пор, пока очередь не станет пустой. education.yandex.ru