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

具体实现如下（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; 
} 

Answer 3

二分图也被称为2色图表即我们可以颜色二分图中的所有节点仅具有2色，使得没有两个相邻的节点具有相同的颜色。

• 最初让所有的顶点都没有任何颜色。

• 从任何顶点开始，并用红色对它进行着色。然后使用除RED之外的其他颜色对所有相邻顶点进行着色，例如黑色。

• 继续重复这个 直到所有节点都着色。如果在任何时候发现有两个相邻的节点具有相同的颜色。那么它不是一个二部图。

C++ Implementation