分享一个自己写的二分图检测算法

Question

因为不确定二分图检测算法是否能运用在不连通的图上，所以这里假设图是连通的。我的实现思路是将开辟一个int型的颜色数组，所有值初始化为-1，代表没有访问过，之后从0开始，将1,2,3,4..传入数组。此时，如果偶数0,2,4,6代表一种颜色，则奇数1,3,5,7代表另一种颜色。此时判断两个顶点的颜色是否不同，只需要判断他们的差值是不是奇数即可。

public class SelfDoneBipartitionDetection {
   private Graph G;
   private int[] color; // 颜色数组
   private boolean isBinary;
   private int mark; // 标记颜色

   public SelfDoneBipartitionDetection(Graph G){
       this.G = G;
       isBinary = true;
       color = new int[G.V()];
       mark = 0;

       for(int i=0; i<color.length; i++){
           color[i] = -1;
       }

       dfs(0);
   }

   private void dfs(int v){
       //System.out.println("v is " + v + ". and mark is " + mark);
       color[v] = mark;
       for(int w: G.adj(v)){
           if(color[w] == -1){
               mark++;
               dfs(w);
           }
           else{
               if(Math.abs((color[v] - color[w]) % 2) != 1){
                   isBinary = false;
               }
           }
       }
   }

   public boolean isBinary(){
       return isBinary;
   }
}

Answer 1

仙女座舜 2019-08-15 00:19:34

   0

/     \

1     2        这个是一颗最简单的只有三个结点的二叉树(无环图) 可以把0看成一边 ，1和2看成一边。0和2差的是偶数但这个无环图也是一颗二分图。所以不能用相邻点差值的奇偶性判断一个图是不是二分图

• 提问者 软件工程小白菜 #1

  确实在理，我思考中出现了纰漏，还是要基于顶点来对邻边赋值，感谢1

• liuyubobobo #2

  大赞！感谢分享：）