Bipartite Graph Check

Bipartite Graph Check is quite easy and can be implemented using BFS or DFS. I am assuming you already know what is Bipartite Graph. There is one critical case that comes in my mind right now is following one:

Now I will show a DFS based implemention of bipartite check. You might already know checking bipartite graph is to coloring the nodes with alternative color when two nodes are adjacent. One choice while implementng bipartite check is to -

A. stop when any color conflict happen or

B. keep coloring rest of the nodes.


static final char WHITE = 0;
static final char GRAY = 1;
static final char BLACK = 2;

// Using DFS
// Stop when any color conflict happen
static boolean isBipartite1(int u, char c) {
    color[u] = c;
    c = (c == GRAY) ? BLACK : GRAY;

    boolean ret = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u].get(i);
        if (color[v] == color[u]) return false;
        if (color[v] == WHITE) ret = ret && isBipartite1(v, c);
    }
    return ret;
}

Keep coloring all nodes of the connected component:

// Using DFS
// Keep coloring the nodes until connected component ends
static boolean isBipartite2(int u, char c) {
    color[u] = c;
    c = (c == GRAY) ? BLACK : GRAY;

    boolean ret = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u].get(i);
        if (color[v] == WHITE) ret = isBipartite2(v, c) && ret;
        else if (color[v] == color[u]) ret = false;
    }
    return ret;
}

Count left and right side nodes:

// Using DFS.
// Stop when any color conflict happen.
// Count nodes in left and right sides.
static boolean isBipartite3(int u, char c) {
    color[u] = c;
    if (c == GRAY) leftCount++;
    else rightCount++;
    c = (c == GRAY) ? BLACK : GRAY;

    boolean ret = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u].get(i);
        if (color[v] == color[u]) return false;
        if (color[v] == WHITE) ret = ret && isBipartite1(v, c);
    }
    return ret;
}

Using BFS:

// Using BFS.
// Stop when any color conflict happen.
// Count nodes in left and right sides.
static boolean isBipartite4(int s) {
    boolean ret = true;

    Queue<Integer> Q = new LinkedList<>();
    Q.offer(s);
    color[s] = GRAY;
    leftCount++;

    while (!Q.isEmpty()) {
        int u = Q.poll();
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u].get(i);
            if (color[v] == WHITE) {
                color[v] = (color[u] == GRAY) ? BLACK : GRAY;
                Q.offer(v);
                if (color[v] == GRAY) leftCount++;
                else rightCount++;
            } else if (color[v] == color[u])
                return false;
        }
    }

    return ret;
}

Full Code: BipartiteCheck_Demo.java

Blog Comments powered by Disqus.

Next Post Previous Post