檢查圖形是否是雙向的

Question

我在完成關於BFS的代碼編寫之後，我正在學習圖形我的腦海裏有一個問題，我該如何改進我的代碼以使它也能檢查這個圖形是不是二分？使用相同的功能。 我要的顏色，代碼訪問這樣
INT顏色的節點; // - 1（無色未訪問節點），1（紅色爲母），0（藍色兒童）

可能有人幫助我用它 ：） ？

struct node { 
int child_count; 
int child[max]; 
int color; 

};

void BFS(node*G[], int s){ 
int w, v; 
queue <int> q; 
bool visited[max]; 
for (int i = 0; i < s; i++){ 
    visited[i] = false; 
} 
for (int i = 0; i < s; i++){ 
    if (!visited[i]) 
     q.push(i); 
     while (!q.empty()) 
     { 
      v = q.front(); 
      if (!visited[v]) 
      { 
       visited[v] = true; 
       for (int i = 0; i < G[v]->child_count; i++) 
       { 
        w = G[v]->child[i]; 
        q.push(w); 
       } 
      } 
      q.pop(); 
    } 
} 
} 

Answer 1

在Java代碼中

void bfs(int adjacency_matrix[][], int source){ 
    Queue<Integer> queue = new LinkedList<>(); 
    int numNodes = adjacency_matrix[source].length - 1; 
    boolean [] visited = new boolean[numNodes + 1]; 
    int element; 
    HashMap<Integer, Integer> colors = new HashMap<>(); 
    visited[source] = true; // set source vertex/node as visited so we start from it 
    queue.add(source); // add source to the queue 
    colors.put(source, 0); // assign color 0 
    while(!queue.isEmpty()){ 
     element = queue.remove(); // remove head node.. this is parent 
     for(int i = 0; i < numNodes; i++){ 
      if(adjacency_matrix[element][i] == 1 && Objects.equals(colors.get(i), colors.get(element))){ // same set with different number 
       System.out.println("not bipartite here "+i+" and "+element); // this will give duplicate.. use set 
      } 
      if(adjacency_matrix[element][i] == 1 && visited[i] == false){ 
       queue.add(i); // child 
       visited[i] = true; 
       colors.put(i, 1 - colors.get(element)); // this will make it alternate 
      } 

     } 

    } 
    System.out.println(); 
}