Обход графа

Обход графа (также известный как поиск по графу) — это процесс посещения (проверки и/или обновления) каждой вершины в графе. Такие обходы классифицируются порядком, в котором посещаются вершины. Обход дерева является частным случаем обхода графа.

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

Таким образом, обычно необходимо запоминать, какие вершины уже были исследованы алгоритмом, чтобы повторное посещение вершин происходило как можно реже (или, в худшем случае, чтобы предотвратить бесконечное продолжение обхода). Это может быть достигнуто путём связывания каждой вершины графа с «цветом» или состоянием «посещения» во время обхода, которое затем проверяется и обновляется по мере посещения алгоритмом каждой вершины. Если вершина уже была посещена, она игнорируется, и путь далее не исследуется; в противном случае алгоритм проверяет/обновляет вершину и продолжает движение по текущему пути.

В некоторых особых случаях графов посещение других вершин вытекает из структуры графа, а потому нет необходимости явно фиксировать посещение во время обхода. Важным примером является дерево — во время обхода можно считать, что все «родительские» вершины текущей (и другие, в зависимости от алгоритма) уже были посещены. Как поиск в глубину, так и поиск в ширину являются адаптациями алгоритмов, основанных на деревьях, отличаясь, главным образом, отсутствием структурно определённой «корневой» вершины и добавлением структуры данных для записи состояния посещения во время обхода.

Замечание. Если каждая вершина графа обходится алгоритмом на основе дерева (таким как поиск в глубину или в ширину), то алгоритм должен вызываться по меньшей мере один раз для каждой компоненты связности графа. Это легко достигается путём итерации по всем вершинам графа и выполнения алгоритма для каждой вершины, которая ещё не была посещена при её рассмотрении.

Поиск в глубину (англ. depth-first search, DFS) — это алгоритм для обхода конечного графа. Поиск посещает дочерние вершины до того, как посетит соседние. он проходит вглубь любого конкретного пути, прежде чем исследовать его ширину. При реализации алгоритма обычно используется стек (часто это стек вызовов через рекурсию).

Алгоритм начинается с выбранной «корневой» вершины. Затем он итеративно переходит от текущей вершины к смежной непосещённой вершине, пока не сможет найти больше неисследованных вершин для перехода из текущего положения. Алгоритм затем возвращается по ранее посещённым вершинам, пока не найдёт вершину, соединённую с ещё неисследованной территорией. После этого он будет продвигаться по новому пути, как и раньше, возвращаясь назад при встрече с тупиками, и завершится только тогда, когда алгоритм вернётся за пределы исходной «корневой» вершины из самого первого шага.

Поиск в глубину является основой для многих алгоритмов, связанных с графами, включая топологические сортировки и проверку планарности.

• Вход: Граф G и вершина v графа G.
• Выход: Разметка рёбер в связной компоненте v как обнаруженные и обратные.

процедура DFS(G, v) помечаем вершину v как посещённую для всех рёбер e из G.incidentEdges(v) выполнитьесли ребро e не посещено тогдаw ← G.adjacentVertex(v, e) если вершина w не посещена тогда помечаем e как обнаруженное ребро рекурсивно вызываем DFS(G, w) иначе помечаем e как обратное ребро 

Поиск в ширину (англ. breadth-first search, BFS) — это другая техника обхода конечного графа. Поиск в ширину посещает сначала соседние вершины, а затем дочерние, при этом в процессе поиска используется очередь. Этот алгоритм часто применяется для нахождения кратчайшего пути от одной вершины к другой.

• Ввод: Граф G и вершина v графа G.
• Выход: Ближайшая вершина v, удовлетворяющая некоторым условиям, или null, если такой вершины нет.

процедура BFS(G, v) создаём очередь Q помещаем v в очередь Q помечаем vпокаQ не пуста выполнитьw ← Q.dequeue() еслиw равна разыскиваемой то возвращаем wдля всех рёбер e из G.adjacentEdges(w) выполнитьx ← G.adjacentVertex(w, e) еслиx не помечена то помечаем x помещаем x в очередь Qвозвращаем null 

Поиск в ширину может быть использован для решения многих задач в теории графов, например:

• нахождение всех вершин, принадлежащих одной компоненте связности;
• алгоритм Чейни^{[англ.][1]};
• нахождение кратчайшего пути между вершинами;
• проверка двудольности графа;
• алгоритм Катхилл — Макки нумерации сетки;
• алгоритм Форда — Фалкерсона для вычисления максимального потока в транспортной сети;
• сериализация/десериализация бинарного дерева против сериализации в отсортированном порядке (позволяя восстановить дерево эффективно);
• алгоритм генерации лабиринтов^[англ.];
• алгоритм заливки для отметки непрерывных областей двумерного изображения или n-мерного массива;
• анализ сетей и связей.

Проблему исследования графов можно рассматривать как разновидность обхода графа. Это онлайн-задача^[англ.], что означает, что информация о графе раскрывается только во время выполнения алгоритма. Распространённая модель следующая: дан связный граф ${\displaystyle G=(V,E)}$ с неотрицательными весами рёбер. Алгоритм начинается с некоторой вершины и знает все исходящие из неё рёбра и вершины, к которым они ведут, но не более того. При посещении новой вершины снова становятся известны все исходящие из неё рёбра и вершины, к которым они ведут. Цель состоит в том, чтобы посетить все n вершин и вернуться к начальной вершине, но при этом сумма весов пути должна быть как можно меньше. Эту проблему также можно понимать как специфическую версию задачи коммивояжёра, где коммивояжёр должен открывать граф по ходу движения.

Для общих графов лучшими известными алгоритмами как для неориентированных, так и для ориентированных графов является простой жадный алгоритм:

• В случае неориентированного графа полученное решение максимум в ${\displaystyle O(\ln n)}$ раз длиннее оптимального маршрута^[2]. Лучшая известная граница для любого детерминированного онлайнового алгоритма равна 10/3^[3].
  • Единичные веса неориентированных графов могут быть исследованы с конкурентным соотношением 2 − ε^[4], что уже является точной границей для графов-головастиков^{[англ.][5]}.
• В ориентированном случае жадный обход не более чем в ${\displaystyle n-1}$ раз длиннее оптимального маршрута. Это соответствует нижней границе ${\displaystyle n-1}$^[6]. Аналогичная конкурентная нижняя граница^[a]${\displaystyle \Omega (n)}$ также справедлива для рандомизированных алгоритмов, знающих координаты каждого узла в геометрическом вложении. Если вместо посещения всех узлов нужно найти только один «ценный» узел, конкурентные границы составляют ${\displaystyle \Theta (n^{2})}$ для ориентированных графов с единичными весами как для детерминированных, так и для рандомизированных алгоритмов.

Универсальная последовательность обхода — это последовательность инструкций, составляющая обход графа для любого регулярного графа с заданным числом вершин и для любой начальной вершины. Вероятностное доказательство было использовано Алелиунасом и др. для демонстрации существования универсальной последовательности обхода с числом инструкций, пропорциональным ${\displaystyle O(n^{5})}$ для любого регулярного графа с n вершинами^[7]. Шаги, указанные в последовательности, относительны к текущему узлу, а не абсолютны. Например, если текущий узел — ${\displaystyle v_{j}}$, и ${\displaystyle v_{j}}$ имеет d соседей, то последовательность обхода укажет следующий узел для посещения, ${\displaystyle v_{j+1}}$, как i-го соседа вершины ${\displaystyle v_{j}}$, где ${\displaystyle 1\leqslant i\leqslant d}$.

• Обход графа внешней памяти^[англ.]

• Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis II. An Analysis of Several Heuristics for the Traveling Salesman Problem // SIAM Journal on Computing. — 1977. — Т. 6, вып. 3. — doi:10.1137/0206041.
• Alexander Birx, Yann Disser, Alexander V. Hopp, Christina Karousatou. An improved lower bound for competitive graph exploration // Theoretical Computer Science. — 2021. — Май (т. 868). — doi:10.1016/j.tcs.2021.04.003. — arXiv:2002.10958.
• Shuichi Miyazaki, Naoyuki Morimoto, Yasuo Okabe. The Online Graph Exploration Problem on Restricted Graphs // IEICE Transactions on Information and Systems. — 2009. — Т. E92-D, вып. 9. — doi:10.1587/transinf.E92.D.1620. — Bibcode:2009IEITI..92.1620M.
• Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, Roger Wattenhofer. Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs // Theoretical Computer Science. — 2020. — Ноябрь (т. 839). — doi:10.1016/j.tcs.2020.06.007. — arXiv:1903.00581.
• Klaus-Tycho Foerster, Roger Wattenhofer.Lower and upper competitive bounds for online directed graph exploration // Theoretical Computer Science. — 2016. — Декабрь (т. 655). — doi:10.1016/j.tcs.2015.11.017.
• Aleliunas R., Karp R., Lipton R., Lovász L., Rackoff C.Random walks, universal traversal sequences, and the complexity of maze problems // 20th Annual Symposium on Foundations of Computer Science (SFCS 1979). — 1979. — doi:10.1109/SFCS.1979.34.