Компьютерный центр г. Светлогорска

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

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

На рисунке ниже показан порядок обработки вершин при поиске в глубину. Поиск может начинаться с любой вершины: в данном случае мы начали с вершины \(1\). Сначала исследуется путь \(1 → 2 → 3 → 5\), затем алгоритм возвращается к вершине \(1\) и посещает оставшуюся вершину \(4\).

Реализация

Поиск в глубину удобно реализовать рекурсивно. Показанная ниже функция dfs начинает поиск с заданной вершины. Предполагается, что граф представлен списками смежности, хранящимися в массиве g[n]. Кроме того, используется массив used[n], в котором запоминаются посещённые вершины. В начальный момент все элементы этого массива равны False, но когда алгоритм заходит в вершину u, в элемент used[u] записывается True. Функцию можно реализовать следующим образом:

def dfs(u):
    used[u] = True
    # Обработать вершину u
    for v in g[u]:
        if not used[v]:
            dfs(v)

Временная сложность поиска в глубину равна \(O(n + m)\), где \(n\) – число вершин, а \(m\) – число рёбер, поскольку алгоритм обрабатывает каждую вершину и каждое ребро ровно один раз.

Обнаружение циклов

Граф содержит цикл, если в процессе обхода мы встречаем такую вершину, что одна из соседних с ней (кроме той, что предшествует ей на текущем пути) уже посещалась. На рисунке ниже поиск в глубину из вершины \(1\) обнаруживает, что в графе имеется цикл. При переходе из вершины \(2\) в вершину \(5\) мы видим, что соседняя с \(5\) вершина \(3\) уже посещалась. Следовательно, граф содержит цикл, проходящий через вершину \(3\), например \(3 → 2 → 5 → 3.\)

Есть и другой способ узнать, содержит ли граф цикл: просто посчитать количество вершин и рёбер в каждой компоненте. Если компонента содержит \(c\) вершин и ни одного цикла, то в ней должно быть ровно \(c − 1\) рёбер (т. е. она должна быть деревом). Если число рёбер равно \(c\) или больше, то компонента обязательно содержит цикл.

Проверка на двудольность

Граф называется двудольным, если его вершины можно раскрасить двумя цветами, так что никакие две соседние вершины не будут окрашены одним цветом. Удивительно, как просто можно проверить граф на двудольность с помощью поиска в глубину.

Идея в том, чтобы выбрать два цвета \(X\) и \(Y\), окрасить начальную вершину цветом \(X\), всех её соседей – цветом \(Y\), всех их соседей – цветом \(X\) и т. д. Если в какой-то момент мы обнаруживаем, что две соседние вершины окрашены одним цветом, значит, граф не является двудольным. В противном случае граф двудольный, и мы нашли доказывающую это раскраску.

Поиск в глубину из вершины \(1\) показывает, что граф на рисунке ниже не является двудольным, т.  к. вершины \(2\) и \(5\) окрашены одним цветом, хотя и являются соседними.

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

Отметим, что в общем случае трудно определить, можно ли раскрасить вершины графа в \(k\) цветов, так чтобы никакие две соседние вершины не были окрашены одним цветом. Для \(k=3\) эта задача является \(NP\)-трудной.

Практические задания