leetcode:判断二分图（图的遍历）

https://leetcode-cn.com/problems/is-graph-bipartite/

思路：根据分析可知，任意两个相邻的节点，一定是一个属于集合A，一个属于集合B。可以用一个标记的方式来判断，从任意一个点开始，先把他标记为红色，然后遍历整个图将与他直接相连的点标记为绿色，再继续遍历绿色的点，把他们直接相邻的点标为红色。如果在遍历的过程中，比如一个已经标为红色的点，他的相邻的点也为红色，那么这个就不符合二分图，直接返回false。直到所有点都被标记，那么就返回true。

图的遍历有两种方式，一个是深度，一个是广度。（顺便复习一下图的遍历）

DFS

class Solution {
    static final int NO = 0;
    static final int RED = 1;
    static final int GREEN = 2;
    static int[] color;//保存每个节点的颜色
    static boolean isOK;

    public static boolean isBipartite(int[][] graph) {
        int n = graph.length;//节点的个数
        isOK = true;
        color = new int[n];
        Arrays.fill(color, NO);//初始化为无色
        
        //图可能不是连通图，要全部遍历一遍
        for (int i = 0; i < n && isOK; ++i) {
            if (color[i] == NO) {
                dfs(i, RED, graph);
            }
        }
        return isOK;
    }

    /**
     * @param i         节点
     * @param c         该节点的颜色
     */
    public static void dfs(int i, int c, int[][] graph) {
        color[i] = c;
        int c2;//相邻节点的颜色
        if(c == RED) c2 = GREEN;
        else c2 = RED;
        
        for (int neighbor : graph[i]) {
            if (color[neighbor] == NO) {
                dfs(neighbor, c2, graph);
            } else if (color[neighbor] == c) {
                isOK = false;
                return;
            }
        }
    }
}

BFS

class Solution {
    static final int NO = 0;
    static final int RED = 1;
    static final int GREEN = 2;
    static int[] color;//保存每个节点的颜色

    public static boolean isBipartite(int[][] graph) {
        int n = graph.length;//节点的个数
        color = new int[n];
        Arrays.fill(color, NO);//初始化为无色
        for (int i = 0; i < n; i++) {
            if(color[i] == NO){
                Queue<Integer> queue = new LinkedList<Integer>();
                queue.offer(i);
                color[i] = RED;
                while (!queue.isEmpty()){
                    int node = queue.poll();
                    int c2;
                    if(color[node] == RED) c2 = GREEN;
                    else c2 = RED;
                    for (int neighbor:graph[node]) {
                        if(color[neighbor] == NO){
                            queue.offer(neighbor);
                            color[neighbor] = c2;
                        }else if(color[neighbor] != c2){
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

 

本文地址：https://blog.csdn.net/vv0606/article/details/107381513