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

Question

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

#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 

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

Answer 1

Вы должны запускать 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; 
} 

Answer 2

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

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

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; 
} 

Answer 3

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

• Первоначально пусть все вершины не имеют цвета.

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

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

C++ Implementation