10.3. Обходы графа

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

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

Опишем алгоритм поиска в глубину:

• Шаг 1. Все вершины графа отмечаем, как не посещенные. Выбирается первая вершина и помечается как посещённая.
• Шаг 2. Для последней помеченной как посещённой вершины выбирается смежная вершина, которая первая помеченная как не посещенная, и ей присваивается значение посещённой. Если таких вершин нет, то берётся предыдущая помеченная вершина.
• Шаг 3. Повторяем шаг 2 до тех пор, пока все вершины не будут помечены как посещённые.

Пример реализации приведён ниже.

DFS(graph, v, used):
    used[v] = 1
    for (var u : graph[v])
        if (!used[u])
           DFS(graph, u, used)

✒️ Упражнение:
Попробуйте выполнить алгоритм поиска в глубину пошагово для графа.

Обратите внимание, сейчас мы посмотрели на рекурсивную реализацию. Конечно, преимущество использования рекурсивного подхода заключается в простоте его написания, однако, рекурсивный подход имеет свои ограничения.

Можно переписать алгоритм поиска в глубину с использованием особых структур данных. Например, стека.

Опишем алгоритм поиска в глубину в нерекурсивной форме:

• Шаг 1. Все вершины графа отмечаем, как не посещённые. Выбирается первая вершина и помечается как посещённая. Эту вершину кладем в контейнер — стек.
• Шаг 2. Пока стек не пустой:
  • Извлекаем последнюю добавленную вершину.
  • Просматриваем все смежные с ней не посещённые вершины и помещаем их в стек.
    Порядок выхода вершин из стека и будет порядком обхода вершин графа.

Пример работы не рекурсивного алгоритма можно посмотреть на анимации.

Пример реализации приведён ниже.

DFS(graph, v, used):
    stack q
    q.push(v)
    used[v] = 1
    while(!q.empty())
      v = q.front()
      q.pop()
      for (var to : graph[v]):
        if (!used[to]):
          used[to] = true
          q.push(to)

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

Опишем алгоритм поиска в ширину:

• Шаг 1. Всем вершинам графа присваивается значение не посещённой. Выбирается первая вершина и помечается как посещённая и заносится в очередь.
• Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещённая). Все её соседние вершины заносятся в очередь. После этого она удаляется из очереди.
• Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не станет пустой.

Пример реализации алгоритма можно посмотреть на анимации

Пример реализации приведён ниже.

BFS(graph, v, used):
    queue q
    q.push(v)
    used[v] = 1
    while(!q.empty())
      v = q.front()
      q.pop()
      for (var to : graph[v]):
        if (!used[to]):
          used[to] = true
          q.push(to)

✒️ Упражнение:
Подумайте, какое отличие алгоритма поиска в ширину от алгоритма поиска в глубину?

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

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