В информатике обход графа ( также известный как поиск по графу ) относится к процессу посещения (проверки и/или обновления) каждой вершины графа . Такие обходы классифицируются по порядку посещения вершин. Обход дерева — это частный случай обхода графа.
В отличие от обхода дерева, обход графа может потребовать посещения некоторых вершин более одного раза, поскольку до перехода к вершине не обязательно известно, что она уже исследована. По мере того как графы становятся более плотными , эта избыточность становится более распространенной, что приводит к увеличению времени вычислений; поскольку графики становятся более разреженными, справедливо обратное.
Таким образом, обычно необходимо помнить, какие вершины уже были исследованы алгоритмом, чтобы вершины посещались как можно реже (или, в худшем случае, чтобы обход не продолжался бесконечно). Этого можно достичь путем связывания каждой вершины графа с состоянием «цвета» или «посещения» во время обхода, которое затем проверяется и обновляется по мере посещения алгоритмом каждой вершины. Если вершина уже была посещена, она игнорируется и путь дальше не продолжается; в противном случае алгоритм проверяет/обновляет вершину и продолжает движение по текущему пути.
Некоторые частные случаи графов предполагают посещение других вершин в их структуре и, таким образом, не требуют явной записи посещения во время обхода. Важным примером этого является дерево: при обходе можно предположить, что все вершины-предки текущей вершины (и другие в зависимости от алгоритма) уже посещены. Поиск в графе как в глубину, так и в ширину представляет собой адаптацию древовидных алгоритмов, отличающихся, прежде всего, отсутствием структурно определенной «корневой» вершины и добавлением структуры данных для записи состояния посещения.
Примечание. — Если каждая вершина графа должна быть пройдена с помощью древовидного алгоритма (например, DFS или BFS), то этот алгоритм должен быть вызван хотя бы один раз для каждого связного компонента графа. Этого легко достичь, перебирая все вершины графа, выполняя алгоритм для каждой вершины, которая еще не посещена при проверке.
Поиск в глубину (DFS) — это алгоритм обхода конечного графа. DFS посещает дочерние вершины перед посещением родственных вершин; то есть он пересекает глубину любого конкретного пути, прежде чем исследовать его ширину. Стек (часто стек вызовов программы через рекурсию ) обычно используется при реализации алгоритма.
Алгоритм начинается с выбранной «корневой» вершины; Затем он итеративно переходит от текущей вершины к соседней, непосещенной вершине, пока не перестанет находить неисследованную вершину для перехода из ее текущего местоположения. Затем алгоритм возвращается к ранее посещенным вершинам, пока не найдет вершину, связанную с еще более неизведанной территорией. Затем он продолжит идти по новому пути, как и раньше, возвращаясь назад, когда сталкивается с тупиками, и заканчивая только тогда, когда алгоритм вернулся за исходную «корневую» вершину с самого первого шага.
DFS является основой для многих алгоритмов, связанных с графами, включая топологическую сортировку и проверку планарности .
Процедура DFS( G , v ) — это метка v как исследованная для всех ребер e в G .incidentEdges( v ) do , если ребро e не исследовано, то w ← G .adjacentVertex( v , e ) , если вершина w неисследована , то пометьте e как a обнаруженное преимущество рекурсивно вызвать DFS( G , w ) , иначе пометить e как заднее ребро
Поиск в ширину (BFS) — это еще один метод обхода конечного графа. BFS посещает одноуровневые вершины перед посещением дочерних вершин, и в процессе поиска используется очередь . Этот алгоритм часто используется для поиска кратчайшего пути от одной вершины к другой.
Процедура BFS( G , v ) создает очередь Q , ставит v в очередь на метку Q , пока Q не пуста, do w ← Q .dequeue(), если w - это то, что мы ищем , то возвращаем w для всех ребер e в G .adjacentEdges ( w ) do x ← G .adjacentVertex( w , e ) если x не отмечен , то отметьте x , поставьте x в очередь на Q , верните ноль
Поиск в ширину можно использовать для решения многих задач теории графов, например:
Задачу исследования графа можно рассматривать как вариант обхода графа. Это онлайн-задача , а это означает, что информация о графе раскрывается только во время выполнения алгоритма. Общая модель выглядит следующим образом: задан связный граф G = ( V , E ) с неотрицательными весами ребер. Алгоритм начинается с некоторой вершины и знает все инцидентные исходящие ребра и вершины на концах этих ребер, но не более того. При посещении новой вершины снова известны все инцидентные исходящие ребра и вершины в конце. Цель — посетить все n вершин и вернуться в начальную вершину, но сумма весов тура должна быть как можно меньше. Задачу также можно понимать как конкретную версию задачи о коммивояжере , где продавцу приходится на ходу находить граф.
Для общих графов наиболее известным алгоритмом как для неориентированных, так и для ориентированных графов является простой жадный алгоритм :
Универсальная последовательность обхода — это последовательность инструкций, содержащая обход любого регулярного графа с заданным количеством вершин и для любой начальной вершины. Вероятностное доказательство было использовано Алелиунасом и др. чтобы показать, что существует универсальная последовательность обхода с количеством инструкций, пропорциональным O ( n 5 ), для любого регулярного графа с n вершинами. [6] Шаги, указанные в последовательности, относятся к текущему узлу, а не являются абсолютными. Например, если текущий узел — v j , а v j имеет d соседей, то последовательность обхода укажет следующий узел для посещения, v j +1 , как i -го соседа v j , где 1 ≤ i ≤ d .