Основа проектирования алгоритма

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

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

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

Прежде всего следует заметить, что описанная процедура окрашивания по сути идентична описанию BFS: мы перемещаемся вперед от s, раскрашивая узлы, когда они впервые попадаются в процессе перебора. Более того, алгоритм окрашивания можно описать следующим образом: мы выполняем поиск BFS, узел s окрашивается в красный цвет, все узлы уровня L1 — в синий, все узлы уровня L2 в красный и так далее.

Нечетные уровни окрашиваются в синий цвет, а четные — в красный. Чтобы реализовать это описание на базе BFS, достаточно взять реализацию BFS и добавить дополнительный массив Color.

При каждом шаге BFS, на котором узел v добавляется в список L[i + 1], выполняется присваивание Color[v] = red, если i + 1 является четным числом, или Color[v] = blue, если i + 1 нечетное.

В конце этой процедуры остается перебрать все ребра и определить, не был ли присвоен обоим концам одинаковый цвет. Следовательно, общее время выполнения алгоритма окрашивания составляет O(m + n), как и для алгоритма BFS.