Разделительная матрица смежности двудольного графа

Question

Допустим, у меня есть граф G с его матрицей смежности A. Я знаю, что G двудольный. Как разбить вершины в G на два множества, которые всегда образуют двудольный граф? Спасибо!

Answer 1

Объявите массив which размера, равного числу вершин, изначально устанавливающего каждый элемент на 0. Затем выполните поиск по глубине по графику, записав «номер уровня», на котором вы находитесь, когда идете. Это начинается с 1 и чередуется между 1 и 2 с каждым пройденным ребром. Для каждой достигнутой вершины присвойте текущему уровню соответствующей записи which и (если ранее было 0) рекурсия для обработки своих дочерних элементов. Впоследствии все элементы which будут либо 1, либо 2, а which[i] указывает, к какой заданной вершине относится i.

Интуитивно, вы можете себе представить, что каждый обход от родителя к ребенку в DFS приводит к «понижению» уровня, и каждый обход назад возвращает вас вверх. По двудольному свойству все вершины на четных уровнях могут быть связаны только с вершинами на нечетных уровнях и наоборот, поэтому для того, чтобы разделить их на два множества, достаточно обозначить узлы «четный» или «нечетный».

Если ваш график содержит более одного компонента, вам, разумеется, потребуется отдельная DFS для каждого компонента.