Что такое двудольный граф
Двудольный граф — это граф, вершины которого можно разделить на два независимых множества, U и V, так что каждое ребро (u, v) либо соединяет вершину из U в V, либо вершину из V в U.
Проще говоря, граф называется двудольным графом, если мы можем раскрасить граф, используя 2 цвета, так что никакие соседние узлы не имеют одного и того же цвета.
Если граф имеет цикл нечетной длины, он не является двудольным графом.
Две вершины одного и того же множества будут соединены, что противоречит определению двудольности, в котором говорится, что **_есть два набора вершин, и ни одна вершина не будет соединена с какой-либо другой вершиной того же набора._**
Если граф имеет цикл четной длины, он называется двудольным графом.
Проверка двудольного графа с использованием алгоритма поиска в ширину
Поиск в ширину используется для определения того, является ли граф двудольным или нет.
Алгоритм
* Инициализировать очередь, целочисленный массив цветов со всеми значениями 0. Этот массив цветов хранит 3 значения. 0 означает не окрашенный и не посещенный, 1 означает посещенный и окрашенный с использованием цвета 1, 2 означает посещенный и окрашенный с использованием цвета 2.< br /> * Запустите цикл от начального узла к конечному узлу и запустите наш алгоритм BFS. (Полезно для несвязного графа).
* Добавляем текущий узел в очередь и окрашиваем узел цветом 1. Отмечаем его внутри целочисленного массива.
* Пока наша очередь не опустеет, делаем следующие шаги:
* Удалить верхний элемент из очереди.
* Пройтись по всем соседним узлам удаленного узла.
* Если узел не окрашен, проверить цвет удаленного узла. Раскрасьте дочерний узел таким образом, что color[removed] = 1 означает сохранение color[child] = 2, иначе color[child] = 1.
Добавьте дочерний узел в очередь.
* Если узел уже окрашен, убедитесь, что цвета обоих узлов разные.
* Если цвета узлов одинаковые, вернуть false, указывающее, что граф не является двудольным.
* Если наша очередь становится пустой, это означает, что мы можем раскрасить граф, используя 2 цвета, так что никакие соседние узлы не будут иметь одинаковый цвет. Таким образом, граф является двудольным графом.
Пример
1. Двудольный граф
2. Не двудольный граф
Сложность времени и пространства
* Проходим через все узлы и ребра. Таким образом, временная сложность будет O(V + E), где V = вершины или узлы, E = ребра.
* Мы используем цветной массив, очередь и список смежности для графа. Таким образом, пространственная сложность будет O(V) + O(V) + O(V + E).
Код
Первоначально опубликовано: