LeetCode/785. 判断二分图

785. 判断二分图

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i]中不存在i，并且graph[i]中没有重复的值。

示例1 ：

输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例2：

输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题思想不难，但是细节要命。基本思想就是染色法，通过广度优先搜索遍历(BFS)，随机选择一个结点上色，比如说染上黑色，然后找到与该结点相连的所有邻接结点，给他们染上不同的颜色，比如说白色。这样，通过广度优先搜索遍历，如果发现某两个相邻结点染色一致，那么就不是二分图，直接返回false就好，反之，当整个图遍历完后，条件依然满足，那么就是二分图，返回true。

具体代码如下：

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;   //存放数组长度

        //用来存放颜色
        //染色状态，0表示未染色，1表示染成黑色，2表示染成白色
        int[] color = new int[n];
        //初始化颜色数组
        Arrays.fill(color, 0);

        for (int i = 0; i < n; i++) {
            if (color[i] == 0) { //如果没有这个判断的话，会增加时间复杂度
                Queue<Integer> list = new LinkedList<>();   //初始化队列
                list.offer(i);  //BFS理论上讲可以随机选择一个开始结点
                color[i] = 1;   //将初始结点染色，你可以染黑色，也可以染白色
                while (!list.isEmpty()) {   //下面就是标准的BFS框架了，将一个结点的所有邻接结点全部入队，然后执行相应的染色操作
                    int index = list.poll();    //将当前结点取出
                    int colorFlags = color[index] == 1 ? 2 : 1; //判断当前结点的染色情况，如果当前结点染色为黑色，那么就要给邻接结点染上白色
                    for (int neighbor : graph[index]) { //遍历当前结点所有的邻接结点
                        if (color[neighbor] == 0) { //若邻接结点没染色，那么给它们染上相反的颜色，并将邻接结点入队
                            color[neighbor] = colorFlags;
                            list.offer(neighbor);
                        } else if (color[neighbor] != colorFlags) { 
                            //到这一步就是，如果邻接结点染色了，并且和当前结点颜色一致，那么就不是二分图，直接返回false
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

这里我们不妨回顾一下Java中队列的基本知识，在Java中，队列一般用LinkedList来实现，主要的API有add、offer、poll、remove、peek和element，我们来看一下这些方法的区别在哪里，直接上源码：

• add方法

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

add方法就是在队尾添加一个新的结点。

• offer方法

/**
 * Adds the specified element as the tail (last element) of this list.
 *
 * @param e the element to add
 * @return {@code true} (as specified by {@link Queue#offer})
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}

offer方法就是add实现的，惊不惊喜，意不意外？

• poll方法

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * Unlinks non-null first node f.
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

poll方法检索并移除队列第一个元素，如果队列为空，则返回空。

• remove方法

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E remove() {
    return removeFirst();
}

/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

remove方法也是返回并移除队列第一个元素，不过如果队列为空则会抛出NoSuchElementException异常。

• peek方法

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

peek方法，只是检索队列的第一个元素，并不会移除元素，如果队列为空，则返回null。

• element方法

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list
 * @throws NoSuchElementException if this list is empty
 * @since 1.5
 */
public E element() {
    return getFirst();
}

/**
 * Returns the first element in this list.
 *
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

element方法，和peek方法一样，只不过在队列为空时会抛出NoSuchElementException异常。