欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

leetcode:判断二分图(图的遍历)

程序员文章站 2022-06-21 13:31:32
https://leetcode-cn.com/problems/is-graph-bipartite/思路:根据分析可知,任意两个相邻的节点,一定是一个属于集合A,一个属于集合B。可以用一个标记的方式来判断,从任意一个点开始,先把他标记为红色,然后遍历整个图将与他直接相连的点标记为绿色,再继续遍历绿色的点,把他们直接相邻的点标为红色。如果在遍历的过程中,比如一个已经标为红色的点,他的相邻的点也为红色,那么这个就不符合二分图,直接返回false。直到所有点都被标记,那么就返回true。图的遍历有...

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

leetcode:判断二分图(图的遍历)

思路:根据分析可知,任意两个相邻的节点,一定是一个属于集合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

相关标签: 刷题 算法