图的深度优先遍历（DFS）和广度优先遍历（BFS）

﹏ヽ暗。殇╰゛Y 2023-02-27 12:12 16阅读 0赞

# 一、题目描述 #

[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  
解释:   
无向图如下:  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70][]  
我们可以将节点分成两组: \{0, 2\} 和 \{1, 3\}。

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/is-graph-bipartite  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 二、题目解读 #

对于图中的任意两个节点 uu 和 vv，如果它们之间有一条边直接相连，那么 uu 和 vv 必须属于不同的集合。

如果给定的无向图连通，那么我们就可以任选一个节点开始，给它染成红色。随后我们对整个图进行遍历，将该节点直接相连的所有节点染成绿色，表示这些节点不能与起始节点属于同一个集合。我们再将这些绿色节点直接相连的所有节点染成红色，以此类推，直到无向图中的每个节点均被染色。

如果我们能够成功染色，那么红色和绿色的节点各属于一个集合，这个无向图就是一个二分图；如果我们未能成功染色，即在染色的过程中，某一时刻访问到了一个已经染色的节点，并且它的颜色与我们将要给它染上的颜色不相同，也就说明这个无向图不是一个二分图。

**把图中所有节点分成2个子集，且相邻节点不能在同一个子集中.输入是二维数组，代表了每个节点的相邻节点**

# **三、题目解答** #

## **1.广度优先遍历（用队列）** ##

class Solution {
        public boolean isBipartite(int[][] graph) {
            int n=graph.length;
            int[] visited=new int[n];
            for(int i=0;i<n;i++){
                if(visited[i]!=0)continue; //若已染色，说明已经处理过，直接跳过
                Queue <Integer> queue=new LinkedList<Integer>();
                queue.offer(i);
                visited[i]=1;// 0未染色，1染红色，-1染绿色
                while(!queue.isEmpty()){
                    int node=queue.poll();
                    for(int j=0;j<graph[node].length;j++){
                        int visiting=graph[node][j];
                        if(visited[visiting]==0){ //若相邻节点未染色，染相反颜色
                            visited[visiting]=-visited[node];
                            queue.offer(visiting);
                        }
                        if(visited[visiting]==visited[node]){ //若相邻节点染同色，则返回错误
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    }

## 2.深度优先遍历（栈 / 递归） ##

class Solution {
        int[][] graph;
        int[] visited;
    
        public boolean isBipartite(int[][] graph) {
            this.graph = graph;
            visited = new int[graph.length];
            for(int i=0;i<graph.length;i++)
                if(visited[i]==0 && !dfs(i)) return false;
            return true;  
        }
        //用栈的话，事实上，每个递归的传入参数都得给父亲保存起来（否则就得自己保存到栈里，儿子从栈中拿，要么天生带上，不能只利用栈给访问排序而不给保证传入的参数，这里是父亲的颜色）
        boolean dfs(int cur){
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(cur);
            visited[cur] = 1;
            while(!stack.isEmpty()){
                cur = stack.pop();     
                for(int i : graph[cur]){
                    if(visited[i] == 0){
                        stack.push(i);
                        visited[i] = -visited[cur];//老父亲也不能帮你保存，只能老父亲帮你设置好到外部
                    }else if(visited[i] == visited[cur])
                        return false;
                }  
            }
            return true;
        }
    }
    
    //图的深度优先用递归解就是最好的了，儿子管自己，别让老父亲帮你判断合法不，函数栈帧自己保存自己参数，有多少存多少，手动栈模拟的话最好只保存顺序，不要保存一堆参数，
    class Solution {
        int[][] graph;
        int[] visited;
    
        public boolean isBipartite(int[][] graph) {
            this.graph = graph;
            visited = new int[graph.length];
            for(int i=0;i<graph.length;i++)//非连通，只需要每个部分满足每一条边的两个节点一个来自A集合，一个来自B集合也算二分图
                if(visited[i]==0 && !dfs(i,1)) return false;//公用一个visited数组，已经访问过的就是已经上色的，也是就是连通的就跳过
            return true;
        }
        boolean dfs(int cur, int color){
            if(visited[cur] != 0) return visited[cur] == color;
    
            visited[cur] = color;
            for(int i: graph[cur]){
                if(!dfs(i, -color)) return false;
            }
            return true;
        }
    }

## 3.并查集 ##

class Solution {
        public boolean isBipartite(int[][] graph) {
            // 初始化并查集
            UnionFind uf = new UnionFind(graph.length);
            // 遍历每个顶点，将当前顶点的所有邻接点进行合并
            for (int i = 0; i < graph.length; i++) {
                int[] adjs = graph[i];
                for (int w: adjs) {
                    // 若某个邻接点与当前顶点已经在一个集合中了，说明不是二分图，返回 false。
                    if (uf.isConnected(i, w)) {
                        return false;
                    }
                    uf.union(adjs[0], w);
                }
            }
            return true;
        }
    }
    
    // 并查集
    class UnionFind {
        int[] roots;
        public UnionFind(int n) {
            roots = new int[n]; 
            for (int i = 0; i < n; i++) {
                roots[i] = i;
            }
        }
    
        public int find(int i) {
            if (roots[i] == i) {
                return i;
            }
            return roots[i] = find(roots[i]);
        }
    
        // 判断 p 和 q 是否在同一个集合中
        public boolean isConnected(int p, int q) {
            return find(q) == find(p);
        }
    
        // 合并 p 和 q 到一个集合中
        public void union(int p, int q) {
            roots[find(p)] = find(q);
        }
    }

[785.]: https://leetcode-cn.com/problems/is-graph-bipartite/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70]: /images/20230209/7f26bfdc81b64f9da625a814fb1d1f6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200717172000272.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvbmdodTE0NTg3MDA3,size_16,color_FFFFFF,t_70