时间戳

首页 > 解决方案 > Testing graph bipartitness

java - Testing graph bipartitness

问题描述

I wrote an algorithms for testing graph bipartitness for Graph Algorithms course on edX (initially available on Coursera) and it fails on one of their test cases.

I gave it a thought and cannot find so far what might I be missing, I use BFS traversal to color nodes to test for bipartitness, it works on a few simple test cases and on 17 of 28 test cases on edX.

private static final int WHITE = -1;
private static final int BLACK = -2;
private static final int START_INDEX = 0;

static boolean isBipartite(ArrayList<Integer>[] adj) { // an array of lists of neighbors
    int[] colors = new int[adj.length];
    boolean[] visited = new boolean[adj.length];
    colors[START_INDEX] = WHITE;
    Queue<Integer> queue = new LinkedList<>();
    // start with some node
    queue.add(START_INDEX);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        ArrayList<Integer> neighbors = adj[node];
        for (int neighbor : neighbors) {
            if (!visited[neighbor]) {
                if (node != neighbor) {
                    // add for traversal and color with an opposite color
                    queue.add(neighbor);
                    colors[neighbor] = colors[node] == WHITE ? BLACK : WHITE;
                } else {
                    // self cycle will always be odd
                    return false;
                }
            } else {
                // return immediately if encountered an already colored node 
                // with the same color, there is an odd cycle
                if (colors[node] == colors[neighbor]) {
                    return false;
                }
            }
        }
        visited[node] = true;
    }


    // final check of u and v colors for all edges
    for (int u = 0; u < adj.length; u++) {
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u].get(i);
            if (colors[u] == colors[v]) {
                return false;
            }
        }
    }

    return true;
}

Any suggesting what could I be missing in my algorithm? Also without the final check my algorithm would fail on the 3rd test case out of 28 (I do not see the inputs), even though I don't understand why - I should already be finding the odd cycles in the main for loop.

Please help.

Some of the sample graphs I tested myself, the 1st is not bipartite, the 2nd is bipartite.

enter image description here

enter image description here

标签： javaalgorithmgraphbipartite

解决方案

正如评论中所指出的，您假设每个节点都可以从起始节点到达。好消息是这很容易解决。Colors定义三个值的枚举： NoColor、Black和White。伪代码如下：

输入：G带有节点整数的0图n - 1

Initialise array colors of length n with all values set to NoColor;
for each `i` from `0` to `n - 1`, do {
    if colors[i] = NoColor then {
        Initialise q to an empty queue (or stack - whatever floats your boat);
        push i onto queue;
        colors[i] <- Black;
        while q is not empty do {
            pop k off of q;
            for each neighbour i of k such that colors[i] = NoColor do
                colors[i] <- the opposite color of colors[k];
                push i onto q;
            }
        }
    }
}

如果存在着色，这将为您提供 2 着色。在这种情况下，您需要验证它实际上是 2-coloring 以检查图形是否是二分的。

推荐阅读