BFS, чтобы проверить, является ли граф двудольным в C ++ - PullRequest
Новая
       39

BFS, чтобы проверить, является ли граф двудольным в C ++

3 голосов
/ 27 марта 2012

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

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

#define MAX 1000

int numberVertex, numberEdges;
int particion[MAX], visited[MAX];
vector< int > adjacencyMatrix[MAX];

bool bfs()
{
    int i, origin, destination, begin;
    queue< int > queueVertex;
    begin = 0;
    queueVertex.push(begin);
    particion[begin] = 1; // 1 left,
    visited[begin] = 1; // set adjacencyMatrixray

    while(!queueVertex.empty())
    {
        origin = queueVertex.front(); queueVertex.pop();
        for(i=0; i < adjacencyMatrix[origin].size(); i++)
        {
            destination = adjacencyMatrix[origin][i];
            if(particion[origin] == particion[destination])
            {
                return false;
            }
            if(visited[destination] == 0)
            {
                visited[destination] = 1;
                particion[destination] = 3 - particion[origin]; // alter 1 and 2 subsets
                queueVertex.push(destination);
            }
        }
    }
    return true;
}

int main()
{
 freopen("tarea2.in", "r", stdin);
    int i,j, nodeOrigin, nodeDestination;
    scanf("%d %d", &numberVertex, &numberEdges);
    for(i=0; i<numberEdges; i++)
    {
        scanf("%d %d", &nodeOrigin, &nodeDestination);
        adjacencyMatrix[nodeOrigin].push_back(nodeDestination);
        adjacencyMatrix[nodeDestination].push_back(nodeOrigin);
    }
    if(bfs()) {

        printf("Is bipartite\n");
          for (j=0; j<numberVertex; j++){
        cout<<j<<" "<<particion[j]<<endl;
        }

    }
    else {printf("Is not bipartite\n");}





    return 0;
}

Например, для этого ввода 

6 4
3 0
1 0
2 5
5 4

вывод должен быть: 

Is bipartite
0 1
1 2
2 1
3 2
4 1
5 2

Вместо этого выдает мне вывод: 

0 1
1 2
2 0
3 2
4 0
5 0

Это происходит потому, что граф не является связным графом, т. Е. Имеет два связанных компонента. Я надеюсь, что вы можете мне помочь, потому что я застрял с этим в течение нескольких дней.

Ответы [ 3 ]

7 голосов
/ 27 марта 2012

Вы должны запускать bfs на каждом подключенном компоненте. Самый простой способ сделать это - перебрать все вершины, и если они не были посещены, просто вызовите для них bfs. 

bool is_bipartite()
{
    for(int i = 0; i < numberVertex; i++)
    {
       if (visited[i] == 0 && !bfs(i)) {
           return false;
       }
    } 
    return true;
}

Это все еще линейно, потому что вы запускаете bfs для каждого подключенного компонента один раз. 

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

#define MAX 1000

int numberVertex, numberEdges;
int particion[MAX], visited[MAX];
vector< int > adjacencyMatrix[MAX];

bool bfs(int begin)
{
    int i, origin, destination;
    queue< int > queueVertex;
    queueVertex.push(begin);
    particion[begin] = 1; // 1 left,
    visited[begin] = 1; // set adjacencyMatrixray

    while(!queueVertex.empty())
    {
        origin = queueVertex.front(); queueVertex.pop();
        for(i=0; i < adjacencyMatrix[origin].size(); i++)
        {
            destination = adjacencyMatrix[origin][i];
            if(particion[origin] == particion[destination])
            {
                return false;
            }
            if(visited[destination] == 0)
            {
                visited[destination] = 1;
                particion[destination] = 3 - particion[origin]; // alter 1 and 2 subsets
                queueVertex.push(destination);
            }
        }
    }
    return true;
}

bool is_bipartite()
{
    for(int i=0; i< numberVertex; i++)
    {
       if (visited[i] == 0 && !bfs(i)) {
           return false;
       }
    } 
    return true;
}

int main()
{
    //freopen("tarea2.in", "r", stdin);
    int i,j, nodeOrigin, nodeDestination;
    scanf("%d %d", &numberVertex, &numberEdges);
    for(i=0; i<numberEdges; i++)
    {
        scanf("%d %d", &nodeOrigin, &nodeDestination);
        adjacencyMatrix[nodeOrigin].push_back(nodeDestination);
        adjacencyMatrix[nodeDestination].push_back(nodeOrigin);
    }
    if(is_bipartite()) {

        printf("Is bipartite\n");
          for (j=0; j<numberVertex; j++){
        cout<<j<<" "<<particion[j]<<endl;
        }

    }
    else {printf("Is not bipartite\n");}

    return 0;
}
2 голосов
/ 20 сентября 2013

Подробная реализация выглядит следующим образом (версия C ++). Он сможет обрабатывать несколько отдельных подключенных компонентов.

Предположим, что узел графа определен как: 

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

Затем вы можете проверить, является ли весь граф bipartite, вызвав bfs(). 

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

bool bfs(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;
}
0 голосов
/ 15 ноября 2016

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

  • Изначально пусть все вершины не имеют какого-либо цвета.

  • Начните с любой вершины и раскрасьте ее КРАСНЫМ. Затем раскрасьте все смежные вершины в цвет, отличный от КРАСНОГО, скажем, черного.

  • Продолжайте повторять это пока все узлы не окрашены. Если в какой-то момент вы нашли два смежных узел имеет одинаковый цвет. Тогда это не двудольный граф.

Реализация C ++

...