檢查圖形是否是二分的 (check if the graph is bipartite or not)

問題描述

檢查圖形是否是二分的 (check if the graph is bipartite or not)

我正在學習圖表，在我寫完關於 BFS 的代碼後，我確實有一個問題，我如何改進我的代碼以使其也可以檢查這個圖表是否是二分的？使用相同的功能。我想像這樣為代碼訪問的節點著色 int color;//‑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();
    }
}
}

參考解法

方法 1:

Code in 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();
}

方法 2:

Here is the code in C++.

#include <iostream>
#include <vector>
#include <list>
#include <queue>

struct Edge{
    int source;
    int destination;
};

void addEdge(std::vector<Edge> edges, std::vector<std::list<int>> &adjList){
    for(int i = 0; i < edges.size(); i++){
        int source = edges[i].source;
        int destination = edges[i].destination;
        adjList[source].push_back(destination);
        // And because it's an undirected grapgh
        adjList[destination].push_back(source);
    }
}

void printGraph(int nodes, std::vector<std::list<int>> adjList){
    for(int i = 0; i < nodes; i++){
        std::cout << i << ":";
        std::list<int>::iterator it;
        for(it = adjList[i].begin(); it != adjList[i].end(); it++)
            std::cout << *it << "‑>";
        std::cout << "NULL\n";
    }
}

bool check_bipartite(int nodes, int start, 
                            std::vector<std::list<int>> adjList){

    std::vector<bool> visited(nodes, false);
    std::queue<int> q;
    visited[start] = true;

    // ‑1 means no colour is assigned. 0 means red and 1 means blue
    std::vector<int> colours(nodes, ‑1);

    q.push(start);
    // Assign it red colour
    colours[start] = 0;

    while(!q.empty()){
        int a = q.front(); 
        q.pop();

        std::list<int>::iterator it;
        for(it = adjList[a].begin(); it != adjList[a].end(); it++){
            if(!visited[*it]){
                q.push(*it);
                // It won't have any colour assigned yet
                // Assign a colour opposite to the parent
                colours[*it] = ((colours[a] == 0) ? 1 : 0);
                std::cout << "Colour of " << *it << " = " << colours[*it] << std::endl;
                // Mark it as visited
                visited[*it] = true;
            }
            // If this vertex has already been visited
            // Check if the colour of the parent is different from this vertix
            else if(visited[*it]){
                if(colours[a] == colours[*it])
                    return false;
            }
        }
    }
    return true;
}

int main(){
    // Un‑directed graph
    // Vertex 0 is an un‑connected node
    int nodes1 = 10;
    std::vector<Edge> edges1 = {
        {1, 2},
        {2, 3},
        {2, 8},
        // Add this edge to make it non‑bipartite
        //{2, 4},
        {3, 4},
        {4, 6},
        {5, 7},
        {5, 9},
        {8, 9}
    };

    // Create an adjacency graph
    std::vector<std::list<int>> adjList(nodes1);

    // Add all nodes
    addEdge(edges1, adjList);

    // Print the adjacency graph
    printGraph(nodes1, adjList);

    if(check_bipartite(nodes1, 1, adjList))
        std::cout << "It's a bipartite grapgh.\n";
    else
        std::cout << "It's NOT a bipartite graph.\n";

    return 0;
}

(by user4585412、Fafore Tunde、Testing123)

參考文件

1. check if the graph is bipartite or not (CC BY‑SA 2.5/3.0/4.0)