Неориентированный граф - это двудольный граф

Question

Как я могу написать код, чтобы определить, является ли данный неориентированный граф двудольным графом (сложность времени - линейное время)? Я не понимаю, я был бы признателен за небольшую помощь.

Answer 1

Чтобы проверить, является ли график двудольным, вы можете проверить, является ли он 2-окрашиваемым (эквивалентным).

Решение этой проблемы можно найти здесь . Я скопировал основные шаги, приведенные ниже, на случай, если ссылка перестает работать.

1. Покрасьте любую из ваших вершин красным.

2. Определите все неокрашенные вершины, смежные с красной вершиной. Раскрасьте их в синий цвет.

3. Определите все неокрашенные вершины, которые примыкают к синей вершине. Раскрасьте их в красный цвет.

4. Повторите шаги 2 и 3, пока все вершины не станут красными или синими.

5. Если есть две смежные вершины одного цвета, то ваш граф не двудольный, иначе он двудольный.

6. Если граф двудольный, алгоритм раскраски создаст два требуемых набора точек (одна красная и один синий).

Этот алгоритм не является оптимальным, так как он не работает в линейном времени. У вас может быть алгоритм линейного времени (O(E) с E количеством ребер в графе), жадно раскрашивая вершины вашего графа в DFS или BFS.