В чем заключаются принципы работы алгоритмов обхода графа?

Принципы работы алгоритмов обхода графа заключаются в систематическом просмотре всех рёбер или вершин графа с целью отыскания рёбер или вершин, удовлетворяющих определённым условиям. intuit.ru education.yandex.ru

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

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