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