自己书写的二分图检测bfs方法出现了问题

Question

自己先书写的二分图检测，bfs 方法中对“将染颜色” color 的处理和老师的不太一样，不同之处用注释标出；
我是这样想的，是每一次 while 循环中就对一个点的相邻点进行操作，所以每一轮 while 循环中的操作染同一颜色，每完成一轮 while 循环将颜色调整就可以实现交替染色了，但是测试的结果却是错误的，为什么会这样呢？

bfs()部分代码：

private void bfs(int v,int color){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;
        colors[v]=color;
        while(!queue.isEmpty()) {
            int cur=queue.remove();
            //这里
            color = 1 - color;
            for (int w : graph.adj(cur)) {
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                    //这里
                    colors[w]=color;
                }else if(colors[w]==colors[cur]){
                    isBipartite =false;
                }
            }
        }
    }

全部代码：

import java.util.LinkedList;
import java.util.Queue;

public class BipartitionDetection {
    private Graph graph;
    private boolean[] visited;
    private int[] colors;
    private boolean isBipartite = true;

    public BipartitionDetection(Graph graph){
        this.graph = graph;
        visited = new boolean[graph.V()];
        colors = new int[graph.V()];
        for (int i = 0; i < graph.V(); i++) {
            colors[i] = -1;
        }
        for (int v = 0; v < graph.V(); v++) {
            if(!visited[v]){
                bfs(v,0);
            }
        }
    }

    private void bfs(int v,int color){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;
        colors[v]=color;
        while(!queue.isEmpty()) {
            int cur=queue.remove();
            color = 1 - color;
            for (int w : graph.adj(cur)) {
                if (!visited[w]) {
                    queue.add(w);
                    visited[w] = true;
                    colors[w]=color;
                }else if(colors[w]==colors[cur]){
                    isBipartite =false;
                }
            }
        }
    }

    public boolean isBipartite(){
        return isBipartite;
    }

    public static void main(String[] args){
        Graph g = new GraphImplement("GraphDFS/g.txt");
        BipartitionDetection bipartitionDetection = new BipartitionDetection(g);
        System.out.println(bipartitionDetection.isBipartite());
        // true

        Graph g2 = new GraphImplement("GraphDFS/g2.txt");
        BipartitionDetection bipartitionDetection2 = new BipartitionDetection(g2);
        System.out.println(bipartitionDetection2.isBipartite());
        // true

        Graph g3 = new GraphImplement("GraphDFS/g3.txt");
        BipartitionDetection bipartitionDetection3 = new BipartitionDetection(g3);
        System.out.println(bipartitionDetection3.isBipartite());
        //false
    }
}

Answer 1

liuyubobobo 2021-11-03 03:04:31

每轮要染的颜色不是 1 - color，而是 1 - colors[cur]。

1-2-4
| 
+-3-5

对于这张图，从 1 开始做 bfs，用你的逻辑染色，就会有错误。可以调试跟踪一下，看看为什么出错？（提示：队列中的连续两个顶点不一定是反色的，可能是同色的。）

继续加油！：）