Possible Bipartite

Key words：判断一个undirected graph是不是二分图

如何解题：

二分图是这样一个图： 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！

判断二分图的常见方法是染色法： 开始对任意一未染色的顶点染色，之后判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色， 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断，bfs和dfs可以搞定！

易知：任何无回路的的图均是二分图。

Method 1: BFS

 //首先，我们用一个HashMap来存所有看过的点
 //用BFS来遍历整个Graph
public class Solution {
  public boolean isBipartite(List<GraphNode> graph) {
    Map<GraphNode, Integer> visited = new HashMap<>();
      for (GraphNode node : graph) {
        if (!bfs(node, visited)) {
          return false;
        }
      }
    return true;
  }

	// recursion
  private boolean bfs(GraphNode node, Map<GraphNode, Integer> visited) {
  // 说明这个点之前已经被traverse过了
    if (visited.containsKey(node)) {
      return true;
    }
    Queue<GraphNode> queue = new ArrayDeque<>();
    queue.offer(node);
    visited.put(node, 0);
    while (!queue.isEmpty()) {
      GraphNode cur = queue.poll();
  //当前正在遍历的node是curGroup
  //而正在遍历的node的邻居应该和我不同色
      int curGroup = visited.get(cur);
      int neiGroup = curGroup == 0 ? 1 : 0;
  // 看看我的邻居这个GraphNode在不在我的map里，如果不在我就把它放进去
  // 如果在，看看它的颜色是不是对的，如果不对，return false
      for (GraphNode nei : cur.neighbors) {
        if (!visited.containsKey(nei)) {
          visited.put(nei, neiGroup);
          queue.offer(nei);
        } else if (visited.get(nei) != neiGroup) {
          return false;
        }
      }
    }
    return true;
  }
}

TC: O(N + E); explore each node once when we transform it 
from uncolored to colored, traversing all its edges in the process.
SC: O(N); 每个节点都要存一遍

//BFS-iterative 做法
//用一个queue来确定我一层走完才走下一层
//还是需要一个map来确定我有没有走完
 
public class Solution {
  public boolean isBipartite(List<GraphNode> graph) {
    Map<GraphNode, Integer> visited = new HashMap<>();
    Deque<GraphNode> queue = new ArrayDeque<>();
    for (GraphNode node : graph) {
      if (!visited.containsKey(node)) {
        queue.offer(node);
        visited.put(node, 0);
      }
      while (!queue.isEmpty()) {
        GraphNode cur = queue.poll();
        for (GraphNode nei : cur.neighbors) {
          if (!visited.containsKey(nei)) {
            queue.offer(nei);
            visited.put(nei, visited.get(cur) ^ 1);
          } else if (visited.get(nei) == visited.get(cur)) {
            return false;
          }
        }
      }
    }
    return true;
  }
}
//对于这样要走完一整张图的问题来说，BFS和DFS没有任何优劣之分，不同的顺序走完而已。

<aside> 💡 BFS: it traverses in a level-wise manner. i.e, 所有当前层的node traverse结束才会进到下一层。BFS is implemented with a queue.

</aside>

Method 2: DFS

// 如何用stack实现dfs呢？
// 如果我碰到uncolored的node我就将它放进stack
// 直到当前结点所有uncolored的nei都放进stack，再开始pop
// 这点和recursion结合的dfs一样，dfs什么时候开始弹栈？当这一支走完时
// 在BFS里，我们如何确定我们已经遍历完所有结点？while queue.isEmpty()因为我们只要发现没看过，我们就把它put进queue里

class Solution {
    public boolean isBipartite(int[][] graph) {
        //我们需要maintain graph.length来确保遍历完所有元素
        // 并initiate 所有的值都没看过，和map的作用一样
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);
        Deque<Integer> stack = new ArrayDeque<>();
   
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                stack.offer(i);
                color[i] = 0;
            }
            while (!stack.isEmpty()) {
                //将当前结点弹出stack，并把它的uncolored nei拉进来
                Integer node = stack.poll();
                for(int nei : graph[node]) {
                    if (color[nei] == - 1) {
                        stack.offer(nei);
                        //并将它染成和当前结点不同的颜色
                        // bit operation
                        color[nei] = color[node] ^ 1;
                    } else if (color[nei] == color[node]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
TC: O(N + E); explore each node once when we transform it 
from uncolored to colored, traversing all its edges in the process.
SC: O(N); 每个节点都要存一遍

结合了lai code写的dfs版本

public class Solution {
  public boolean isBipartite(List<GraphNode> graph) {
    Map<GraphNode, Integer> visited = new HashMap<>();
    Deque<GraphNode> stack = new ArrayDeque<>();
		//遍历graph里的所有node
    for (GraphNode node : graph) {
      if (!visited.containsKey(node)) {
        stack.offer(node);
        visited.put(node, 0);
      }
      //把所有当前node的uncolored nei装进stack
      while (!stack.isEmpty()) {
        GraphNode cur = stack.pop();
        for (GraphNode nei : cur.neighbors) {
          if (!visited.containsKey(nei)) {
            stack.offer(nei);
            visited.put(nei, visited.get(cur) ^ 1);
          } else if (visited.get(nei) == visited.get(cur)) {
            return false;
          }
        }
      }
    }
    return true;
  }
}

<aside> 💡 写这题很有收获，它迫使我去思考为什么BFS要用queue，DFS要用stack？queue的特性是先进先出，stack是后进先出，所以queue会把最先放进来的同一层的元素先pop出去，而stack则会把同一支的最末端的元素先pop出去。这也是广度搜索和深度搜索的区别。

</aside>