Обход графа - Graph traversal

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

Резервирование

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

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

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

Алгоритмы обхода графа

Примечание. - Если каждая вершина в графе должна быть пройдена древовидным алгоритмом (таким как DFS или BFS), то алгоритм должен быть вызван по крайней мере один раз для каждого связного компонента графа. Этого легко добиться, перебирая все вершины графа, выполняя алгоритм для каждой вершины, которая все еще не посещена при проверке.

Невербальное описание трех алгоритмов обхода графа: случайный, поиск в глубину и поиск в ширину.

Поиск в глубину

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

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

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

Псевдокод

  • Входные данные : Граф G и вершины v из G .
  • Результат : разметка ребер связного компонента v как ребер обнаружения и задних ребер.
procedure DFS(G, v) is
    label v as explored
    for all edges e in G.incidentEdges(v) do
        if edge e is unexplored then
            wG.adjacentVertex(v, e)
            if vertex w is unexplored then
                label e as a discovered edge
                recursively call DFS(G, w)
            else
               label e as a back edge

Поиск в ширину

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

Псевдокод

  • Входные данные : Граф G и вершины v из G .
  • Выход : ближайшая к v вершина, удовлетворяющая некоторым условиям, или ноль, если такой вершины не существует.
procedure BFS(G, v) is
    create a queue Q
    enqueue v onto Q
    mark v
    while Q is not empty do
        wQ.dequeue()
        if w is what we are looking for then
            return w
        for all edges e in G.adjacentEdges(w) do
            xG.adjacentVertex(w, e)
            if x is not marked then
                mark x
                enqueue x onto Q
    return null

Приложения

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

Исследование графа

Задачу исследования графа можно рассматривать как вариант обхода графа. Это онлайн-проблема , означающая, что информация о графике раскрывается только во время выполнения алгоритма. Общая модель выглядит следующим образом: дан связный граф G = ( V , E ) с неотрицательными весами ребер. Алгоритм начинается с некоторой вершины и знает все исходящие ребра и вершины на концах этих ребер, но не более того. Когда посещается новая вершина, снова становятся известны все инцидентные исходящие ребра и вершины в конце. Цель состоит в том, чтобы посетить все n вершин и вернуться в начальную вершину, но сумма весов тура должна быть как можно меньше. Проблему также можно понять как особую версию задачи коммивояжера , в которой продавец должен находить граф на ходу.

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

  • В неориентированном случае жадный тур не более чем в O (ln n ) раз длиннее оптимального маршрута. Лучшая нижняя граница, известная для любого детерминированного онлайн-алгоритма, составляет 10/3.
    • Ненаправленные графы с единичным весом можно исследовать с помощью конкурентного соотношения 2 - ε , что уже является жесткой границей для графов Tadpole .
  • В управляемом случае жадный тур не более чем в ( n - 1 ) раз длиннее оптимального тура. Это соответствует нижней границе n - 1 . Аналогичная конкурентная нижняя граница Ω ( n ) также верна для рандомизированных алгоритмов, которые знают координаты каждого узла в геометрическом вложении. Если вместо посещения всех узлов только один узел «клад» должен быть найден, конкурентные оценки являются thetas ; ( п 2 ) на единицу веса ориентированных графов, как для детерминированных и рандомизированных алгоритмов.

Универсальные последовательности обхода

Универсальная последовательность обхода представляет собой последовательность инструкций , содержащих обход графа для любого регулярного графа с установленным числом вершин и для любой начальной вершины. Вероятностное доказательство было использовано Aleliunas et al. показать, что существует универсальная последовательность обхода с числом инструкций, пропорциональным O ( n 5 ) для любого регулярного графа с n вершинами. Шаги, указанные в последовательности, относятся к текущему узлу, а не абсолютны. Например, если текущий узел - v j , а v j имеет d соседей, то последовательность обхода будет указывать следующий узел для посещения, v j +1 , в качестве i- го соседа v j , где 1 ≤ id .

использованная литература

Смотрите также