Написание программы для проверки двудольного графа

Question

Мне нужно написать программу, которая проверяет, является ли граф двудольным.

Я прочитал статьи в Википедии о раскраске графа и двудольном графе .В этих двух статьях предлагаются методы тестирования двудольности, такие как поиск BFS, но я не могу написать программу, реализующую эти методы.

Answer 1

Почему ты не можешь? Ваш вопрос мешает кому-то даже написать программу для вас, поскольку вы даже не упоминаете конкретный язык ...

Идея состоит в том, чтобы начать с помещения случайного узла в очередь FIFO (также здесь ). Цвет это синий. Затем повторите это, пока в очереди еще есть узлы: удалите элемент из очереди. Раскрасьте соседей другим цветом, отличным от извлеченного элемента, и вставьте (поставьте в очередь) каждого соседа в очередь FIFO. Например, если вы удаляете из очереди (извлекаете) элемент (узел), окрашенный в красный цвет, его соседи окрашиваются в синий цвет. Если вы извлекаете синий узел, раскрасьте его соседей красным. Если нет цветовых конфликтов, график является двудольным. Если в итоге вы раскрасите узел двумя разными цветами, это не будет двудольный.

Как сказал @Moron, то, что я описал, будет работать только для связанных графов. Однако вы можете применить один и тот же алгоритм к каждому подключенному компоненту, чтобы он работал на любом графике.

Answer 2

Подробная реализация выглядит следующим образом (версия C ++):

struct NODE
{
    int color;
    vector<int> neigh_list;
};

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index);

bool checkBigraph(NODE * graph, int numNodes)
{
    int start = 0;

    do 
    {
        queue<int> Myqueue;
        Myqueue.push(start);
        graph[start].color = 0;

        while(!Myqueue.empty())
        {
            int gid = Myqueue.front();
            for(int i=0; i<graph[gid].neigh_list.size(); i++)
            {
                int neighid = graph[gid].neigh_list[i];
                if(graph[neighid].color == -1)
                {
                    graph[neighid].color = (graph[gid].color+1)%2; // assign to another group
                    Myqueue.push(neighid);
                }
                else
                {
                    if(graph[neighid].color == graph[gid].color) // touble pair in the same group
                        return false;
                }
            }
            Myqueue.pop();
        }
    } while (!checkAllNodesVisited(graph, numNodes, start)); // make sure all nodes visited 
                                            // to be able to handle several separated graphs, IMPORTANT!!!

    return true;
}

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index)
{
    for (int i=0; i<numNodes; i++)
    {
        if (graph[i].color == -1)
        {
            index = i;
            return false;
        }
    }

    return true;
}

Answer 3

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm

Пожалуйста, прочитайте эту веб-страницу, используя поиск в ширину, чтобы проверить, когда вы обнаружите, что узел посещен, проверить текущий цикл нечетным или четным.

График является двудольным тогда и только тогда, когда он не содержит нечетного цикла.