LeetCode: Is Graph Bipartite?

Posted on February 18, 2018July 26, 2020 by braindenny

Is Graph Bipartite?

Similar Problems:

Given a graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length – 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2

We cannot find a way to divide the set of nodes into two independent subsets.

Note:

graph will have length in range [1, 100].
graph[i] will contain integers in range [0, graph.length – 1].
graph[i] will not contain i or duplicate values.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution

## https://code.dennyzhang.com/is-graph-bipartite
## Basic Ideas: dfs
##
## Complexity: Time O(n), Space O(1)
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        if n == 0: return False
        s = collections.defaultdict(int)
        for i in range(n):
            if i not in s:
                s[i] = 0
                # dfs
                stack = [i]
                while stack:
                    n1 = stack.pop()
                    for n2 in graph[n1]:
                        if n2 not in s:
                            stack.append(n2)
                            s[n2] = s[n1]^1
                        elif s[n2] == s[n1]:
                            return False
        return True

Solution

## https://code.dennyzhang.com/is-graph-bipartite
class Solution:
    ## Basic Ideas: DFS
    ##
    ## Complexity: Time O(n), Space O(n)
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        length = len(graph)
        self.set_type = [0]*length
        for i in range(length):
            if self.set_type[i] == 0:
                # start dfs
                if self.dfs(graph, i, 1) is False:
                    return False
        return True

    def dfs(self, graph, node, type):
        # mark current node
        self.set_type[node] = type

        # check the neighbors of current node
        for edge in graph[node]:
            if self.set_type[edge] == 0:
                if self.dfs(graph, edge, -type) is False:
                    return False
            elif self.set_type[edge] == type:
                return False
        return True

    ## Basic Ideas: BFS
    ## 
    ##      With one BFS, all connected nodes in current forest will be visited
    ##      For two forests, we can put the first nodes into the same set.
    ##      This is a key improvement, compared to brutple force 
    ##
    ##      set_type[]: [0, 1, -1], [undecided, type1, type2]
    ##
    ## Complexity: Time O(n), Space O(n)
    def isBipartite_v1(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        import collections
        length = len(graph)
        set_type = [0]*length
        for i in range(length):
            # a new forest starts
            if set_type[i] == 0:
                set_type[i] = 1
                queue = collections.deque()
                queue.append((i, 1))
                # BFS
                while len(queue) != 0:
                    for k in range(len(queue)):
                        (node, node_type) = queue.popleft()
                        # find the neighbors
                        for edge in graph[node]:
                            if set_type[edge] == 0:
                                # get the candidates
                                set_type[edge] = -node_type
                                queue.append((edge, -node_type))
                            elif set_type[edge] == node_type:
                                # detect a conflict
                                return False
        return True

Post Views: 6