Is Graph Bipartite?

本文主要是介绍Is Graph Bipartite?，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Code link: https://leetcode.com/problems/is-graph-bipartite/

Constraint:

    graph.length == n
    1 <= n <= 100
    0 <= graph[u].length < n
    0 <= graph[u][i] <= n - 1
    graph[u] does not contain u.
    All the values of graph[u] are unique.
    If graph[u] contains v, then graph[v] contains u.

Idea

The idea is to use 2 different colors to mark each node. If there's an edge between u and v, then the color of u and v must be different. Otherwise there's a color conflict and it couldn't be a Bipartite graph. We could use BFS/DFS to traverse the graph. Initially set the node being visited as blue. Then when visiting its neighbors, set them as different color (red). If any of the neighbor already has a color set that is conflicting with current node, the graph is not a Bipartie.

Code

• BFS solution:

// A node could have 3 stages: 0 (unvisited), 1(red), -1 (blue). All nodes do not have any color at the begining. 
class Solution {
    public boolean isBipartite(int[][] graph) {
        int[] color = new int[graph.length];
        for (int u = 0; u < graph.length; u++) {
            if (color[u] != 0) {
                continue;
            }
            
            color[u] = 1;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(u);
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int neighbor : graph[cur]) {
                    if (color[cur] == color[neighbor]) {
                        return false;
                    } else if (color[neighbor] == 0) {
                        color[neighbor] = -color[cur];
                        queue.offer(neighbor);
                    }
                }
            }
        }
        
        return true;
    }
}

• Time: O(V + E), where V is the number of nodes in the graph and E is the number of edges in the graph.

• Space: O(V). The size of array to keep track of colors is V. The queue is to store the adjacent nodes for a given node, which could be V - 1.

• DFS solution:

class Solution {
   public boolean isBipartite(int[][] graph) {
       int[] nodeColor = new int[graph.length];
       for (int i = 0; i < graph.length; i++) {
           if (nodeColor[i] == 0 && !isValid(graph, nodeColor, i, 1)) {
               return false;
           }
       }
       
       return true;
   }
   
   private boolean isValid(int[][] graph, int[] nodeColor, int node, int colorToMark) {
       if (nodeColor[node] != 0) {
           return nodeColor[node] == colorToMark;
       }
       
       nodeColor[node] = colorToMark;
       for (int neighbor : graph[node]) {
           if (!isValid(graph, nodeColor, neighbor, -colorToMark)) {
               return false;
           }
       }
       
       return true;
   }
}

• Time and space complexity should be the same as BFS.

• Union find solution:

这篇关于Is Graph Bipartite?的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！