1

Хочу проверить граф на двудольность путём окраски вершин одной доли в красный цвет, а другой в чёрный. Рёбер между вершинами одной доли нет.

Граф задаётся списком смежности: 
    5
    2 3
    2 3 4
    0 1
    0 1
    1 

Первая строка - кол-во вершин, ну а дальше, думаю, понятно.

Запускаю обход в глубину. Сам код вот он:

void dfs_visit(int v)
{
    used[v] = true;
    color[v] = "red";
        
    for (vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++)
    {
        if (!used[*it])
        {
            dfs_visit(*it);
            color[*it] = "black";
        }
    }
}

Ответ выдаёт неверный:

1-я доля графа: 0

2-я доля графа: 1 2 3 4

Правильный ответ:

1-я доля графа: 0 1

2-я доля графа: 2 3 4

В чём проблема?

1 ответ 1

1

Не, неправильно. Вы ж каждую вершину после обхода перекрашиваете в чёрный.

Попробуйте передавать цвет как параметр:

void dfs_visit(int v, bool red)
{
    used[v] = true;
    color[v] = red ? "red" : "black";

    for (vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++)
    {
        if (!used[*it])
            dfs_visit(*it, !red);
    }
}

Update: вероятно, надо воспользоваться следующим:

bool is_bipartite()
{
    std::set<int> painted;
    std::map<int, bool> color;
    int start_vertex = 0;
    while (graph.size() != painted.size())
    {
        // find a non-painted vertex
        while (painted[start_vertex])
            start_vertex++;
        if (!dfs_visit(start_vertex, true, painted, color))
            return false;
    }
    // found no problems =>
    return true;
}

bool dfs_visit(int v, bool color, std::set& painted, std::map<int, bool>& colors)
{
    painted.insert(v);
    colors[v] = color;

    for (int next_vertex : graph[v])
    {
        if (painted.find(next_vertex) != painted.end()) // already painted
        {
            if (colors[next_vertex] == color) // adjacent vertices, same color
                return false;
        }
        else
        {
            if (!dfs_visit(next_vertex, !color)) // paint recursively
                return false;
        }
    }
    return true;
}

Преимущества: вам не нужно добавлять цвет и флаг прохождения в граф.

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


Update: Обновил код, должен работать и для несвязных графов

3
  • Вы спрашивали про числа в списке смежности? Вершины нумеруются с нуля. Список можно записать так: 0: 2 3; 1: 2 3 4; 2: 0 1; 3: 0 1; 4: 1; Вершина "0" смежна с вершинами "2" и "3", "1" смежна с вершинами "2", "3", "4" и т.д. Спасибо за ответ!
    – rekrut
    30 янв 2014 в 12:41
  • @rekrut1: угу, я понял, когда внимательнее перечитал вопрос.
    – VladD
    30 янв 2014 в 13:03
  • Спасибо, Влад!
    – rekrut
    30 янв 2014 в 13:25

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.