Теория:

Существует ряд задач, где нужно обойти некоторый граф в глубину или в ширину, так, чтобы посетить каждую вершину один раз. При этом посетить вершины дерева означает выполнить какую-то операцию. Обход графа — это поэтапное исследование всех вершин графа.
Для решения таких задач используются два основных алгоритма: поиск в глубину (depth-first search или DFS) и поиск в ширину (breadth-first search или BFS).
Алгоритм поиска в глубину
1. Двигаемся из начальной вершины.
2. Движемся в произвольную смежную вершину.
3. Из этой вершины обходим все возможные пути до смежных вершин.
4. Если таких путей нет или мы не достигли конечной вершины, то возвращаемся назад к вершине с несколькими исходящими ребрами и идем по другому пути.
5. Алгоритм повторяется, пока не будут исследованы все вершины и достигнута конечная вершина.
Пример:
Рассмотрим реализацию алгоритма поиска в глубину на следующем ориентированном графе на рисунке \(1\).
гл1.png
Рис. \(1\). Ориентированный граф
Реализация алгоритма на графе
Описание шагов алгоритма
гл2.pngНачальная вершина —\( 1\). Необходимо найти вершину \(5\). Применяя алгоритм, двигаемся по одному из возможных путей конца и, если не обнаружили вершину \(5\), возвращаемся и пробуем другой путь.
гл3.pngПроизвольно выбираем сначала движение к ближайшей вершине \(6\). Так как это не конец пути, движемся дальше.
гл4.pngДвижемся к вершине \(7\). Она является конечной, но не искомой вершиной\( 5\). Движемся дальше.
гл5.pngВозвращаемся в вершину \(6\). Она не содержит других путей, поэтому возвращаемся выше к исходной вершине \(1\). От нее исходит еще один не исследованный путь. Идём по нему к смежной вершине \(2\).
гл6.pngВершина \(2\) имеет три смежных вершины. Вершина \(7\) уже изучена, поэтому по этому пути не пойдем. Выбираем вершину \(4\). Она является конечной, но не искомой вершиной \(5\). Движемся дальше. 
гл7.pngВозвращаемся в вершину \(2\). Здесь неисследованной осталась вершина \(3\). Движемся к ней.
гл8.pngВершина \(3\) имеет два смежных узла. Вершина \(4\) уже исследована. Выбираем путь к вершине \(5\). Она и есть конечная искомая вершина. Алгоритм поиска в глубину закончен. Все вершины исследованы.
Алгоритм поиска в ширину
1. Двигаемся из начальной вершины.
2. Движемся по ребрам, исходящим из начальной вершины, и по очереди исследуем смежные с ней вершины.
3. Если эти вершины не являются конечными или целевыми, движемся по ребрам, которые исходят из вершин, смежных с начальной.
4. По очереди исследуем вершины этого "уровня". Если эти вершины не являются конечными или целевыми, движемся дальше на следующий уровень по ребрам, которые исходят из этих вершин.
5. Алгоритм повторяется, пока не будут исследованы все вершины и достигнута конечная целевая вершина.
Пример:
Рассмотрим реализацию алгоритма поиска в ширину для того же самого ориентированного графа на рисунке \(1\).
Реализация алгоритма на графе
Описание шагов алгоритма
шир1.pngНачальная вершина — \(1\). Необходимо найти вершину \(5\), исследовав все вершины
шир2.png
Из начальной вершины\( 1\) исходит два ребра к двум смежным вершинам \(2\) и \(6\).
Рассмотрим их по очереди. Вершина \(2\) не является конечной, так как из нее исходит три ребра. Вершина \(6\) не является конечной, так как из нее исходит одно ребро.
Вершины исследованы и не являются конечными. Движемся дальше
шир3.png
Из вершины \(2\) исходит три ребра к смежным вершинам \(3\), \(4\) и \(7\). Исследуем их. Вершина \(3\) не является конечной, так как из нее исходит одно ребро. Вершина \(4\) является конечной, но не целевой. Вершина \(7\) тоже является конечной, но не целевой.
Вершины исследованы и не являются целевыми, которые требовалось достичь. Движемся дальше
шир4.pngПереходим к вершине \(5\). Она является той самой конечной целевой вершиной, которую по условию мы должны были достичь. Алгоритм завершен