自己书写的二分图检测bfs方法出现了问题
来源:5-7 使用 BFS 求解二分图检测问题

Wonwayshon
2021-11-02
自己先书写的二分图检测,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
}
}
写回答
1回答
-
每轮要染的颜色不是 1 - color,而是 1 - colors[cur]。
1-2-4 | +-3-5
对于这张图,从 1 开始做 bfs,用你的逻辑染色,就会有错误。可以调试跟踪一下,看看为什么出错?(提示:队列中的连续两个顶点不一定是反色的,可能是同色的。)
继续加油!:)
00
相似问题