Модуль: Поиск в глубину. DFS

Двудольный граф

Часто в контексте двудольных графов используется понятие цвета вершины. Разбитие графа на две доли называется покраской его вершин в два различных цвета. Каждое ребро должно соединять вершины различного цвета.

Для проверки графа на двудольность и разбития его на доли чаще всего используется DFS. 
 

Алгоритм

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