Problem

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

  • There are no self-edges (graph[u] does not contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

What is Bipartite Graph?

Bipartite Graph Definition

Examples

Example 1:

1
2
3

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

1
2
3

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Solution

Method 1 - Using BFS

To determine if a given undirected graph is bipartite, one effective approach is using a colouring algorithm, typically employing either Depth-First Search (DFS) or Breadth-First Search (BFS). Here, we’ll use BFS for clarity and consistency across disconnected components of the graph.

Here is the approach:

  • We employ BFS to check if the graph can be coloured using two colours such that no two adjacent nodes have the same colour.
  • By iterating through all nodes, we ensure we consider disconnected components.
  • We’ll attempt to colour each node one of two colours and ensure adjacent nodes receive different colours.
  • If any adjacent nodes receive the same colour, the graph is not bipartite.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                Queue<Integer> queue = new LinkedList<>();
                queue.add(i);
                color[i] = 0;

                while (!queue.isEmpty()) {
                    int u = queue.poll();
                    for (int v : graph[u]) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u];
                            queue.add(v);
                        } else if (color[v] == color[u]) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n

        for i in range(n):
            if color[i] == -1:
                queue = deque([i])
                color[i] = 0

                while queue:
                    u = queue.popleft()
                    for v in graph[u]:
                        if color[v] == -1:
                            color[v] = 1 - color[u]
                            queue.append(v)
                        elif color[v] == color[u]:
                            return False

        return True

Complexity

  • ⏰ Time complexity: - O(V + E) where V is the number of vertices and E is the number of edges as we need to traverse all vertices and edges.
  • 🧺 Space complexity: - O(V) for storing the colouring information and the queue used in BFS.

Method 2 - Using DFS

Here is the approach:

  • Colour the source node with one colour.
  • Recursively attempt to colour adjacent nodes with the opposite colour.
  • If at any point, an adjacent node has the same colour as the current node, the graph is not bipartite.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);
        
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfs(graph, color, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dfs(int[][] graph, int[] color, int node, int c) {
        color[node] = c;
        for (int neighbor : graph[node]) {
            if (color[neighbor] == -1) {
                if (!dfs(graph, color, neighbor, 1 - c)) {
                    return false;
                }
            } else if (color[neighbor] == color[node]) {
                return false;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n

        def dfs(node: int, c: int) -> bool:
            color[node] = c
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    if not dfs(neighbor, 1 - c):
                        return False
                elif color[neighbor] == color[node]:
                    return False
            return True

        for i in range(n):
            if color[i] == -1:
                if not dfs(i, 0):
                    return False

        return True

Complexity

  • ⏰ Time complexity: O(V + E) for traversing all vertices and edges.
  • 🧺 Space complexity: O(V) for storing colouring information and recursion stack.

Method 3 - Using BFS + OOPs

Here is the approach similar to method 1 - but with OOPs:

  1. Assign the RED colour to the source vertex (placing it in set U).
  2. Colour all adjacent nodes with BLUE (placing them in set V).
  3. Colour all nodes adjacent to those with RED (placing them in set U).
  4. Continue this process to ensure all vertices meet the constraints of the 2-colour problem.
  5. If any adjacent nodes share the same colour during this process, then it is impossible to colour the graph with 2 colours, indicating the graph is not bipartite.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

public boolean isBipartiteBfs() {
    // Create a color array to store colors assigned to all veritces.
    // Vertex number is used as index in this array.
    // The value '-1' of colorArr[i] is used to indicate that no color is assigned to vertex 'i'.
    // The value 1 is used to indicate first color is assigned and value 0 indicates second color is assigned.
    //initialize colors for all vertices
    Map<Vertex<T>, Color> colors = new HashMap<>();

    //color all the vertices with white color
    adjVertices.values().forEach(v -> colors.put(v, Color.WHITE));

    List<Vertex<T>> vertices = getVertices();

    for (Vertex<T> v: getVertices()) {
        // if vertex is yet not visited
        if (colors.get(v) == Color.WHITE) {
            colors.put(v, Color.RED);
            boolean result = isBipartiteBfsUtil(v, colors);
            if (!result) {
                return false;
            }
        }



    }
    // Assign first color to source




    // If we reach here, then all adjacent vertices can
    // be colored with alternate color
    return true;
}

private boolean isBipartiteBfsUtil(Vertex<T> p, Map<Vertex<T>, Color> colors) {
    // Create a queue (FIFO) of vertex numbers
    // and enqueue source vertex for BFS traversal
    Queue<Vertex<T>> q = new LinkedList<>();
    q.add(p);

    // Run while there are vertices in queue (Similar to BFS)
    while (q.size() != 0) {
        // Dequeue a vertex from queue
        Vertex<T> u = q.poll();

        //            // Return false if there is a self-loop
        //            if (G[u][u] == 1)
        //                return false;

        // Find all non-colored adjacent vertices
        for (Edge<T> e : u.getEdges()){
            Vertex<T> v = e.getTo();

            // v is not visited yet.
            if(colors.get(v) == Color.WHITE){
                //color is with the alternate color of vertex v compared to parent
                if (colors.get(u) == Color.RED) {
                    //if u is in red, make vertex v in green
                    //if u is in red, make vertex v in green
                    colors.put(v, Color.GREEN);
                } else if (colors.get(u) == Color.GREEN) {
                    //if u is in green, make vertex v in red
                    colors.put(v, Color.RED);
                }
                q.add(v);
            }else if (colors.get(u) == colors.get(v)) {
                return false;
            }
        }

    }
    return true;
}

Method 4 - Using DFS with adjacency matrix

Certainly! Let’s update the DFS approach to work with an adjacency matrix representation of the graph. The adjacency matrix graph will be a 2D array where graph[u][v] is 1 if there is an edge between nodes u and v and 0 otherwise.

Here is the approach:

  • Initialisation: Initialise a color array to keep track of each node’s colour, with -1 indicating uncoloured.
  • DFS Function:
    • Assign the current node a colour (c).
    • Loop through possible nodes (v) and check for adjacency (graph[node][v] == 1).
    • If an adjacent node is uncoloured, recursively apply DFS with the opposite colour.
    • If an adjacent node has the same colour, return false.
  • Iterate and Check: Iterate through each node and invoke DFS for uncoloured nodes to ensure all components are checked.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfs(graph, color, i, 0)) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean dfs(int[][] graph, int[] color, int node, int c) {
        color[node] = c;
        for (int v = 0; v < graph.length; v++) {
            if (graph[node][v] == 1) {  // Check adjacency
                if (color[v] == -1) {
                    if (!dfs(graph, color, v, 1 - c)) {
                        return false;
                    }
                } else if (color[v] == color[node]) {
                    return false;
                }
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n

        def dfs(node: int, c: int) -> bool:
            color[node] = c
            for v in range(n):
                if graph[node][v] == 1:  # Check adjacency
                    if color[v] == -1:
                        if not dfs(v, 1 - c):
                            return False
                    elif color[v] == color[node]:
                        return False
            return True

        for i in range(n):
            if color[i] == -1:
                if not dfs(i, 0):
                    return False

        return True

Complexity

  • ⏰ Time complexity: O(n^2). The time complexity is O(n^2) because for each of the n nodes, we might have to look at n edges due to the adjacency matrix representation.
  • 🧺 Space complexity: O(n^2). The space complexity is O(n^2) dominated by the adjacency matrix storage.

Method 5 - Using DFS + OOPs

Here is the approach: Select three colours: RED, GREEN, and WHITE. In a bipartite graph, each edge connects nodes from separate groups, here designated as RED and GREEN. For a graph to be bipartite, every edge must connect a RED node to a GREEN node.

  • Initially, colour all nodes WHITE. As the algorithm progresses, nodes will be coloured RED or GREEN.
  • Choose a WHITE node and colour it RED. Then, for each neighbour, if it is WHITE, colour it GREEN. Continue this process by colouring the neighbours’ neighbours RED if they are WHITE. Alternate the colours of adjacent nodes between RED and GREEN using Depth-First Search.
  • Repeat the above steps until all nodes are RED or GREEN. If successful, the graph is bipartite.
  • If, during the process, a node has a neighbour with the same colour, or an edge is found where both ends are the same colour, then the graph is not bipartite, and the process stops.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

public boolean isBipartite() {

    //check if graph is empty
    if (size() == 0) {
        return true;
    }


    //initialize colors for all vertices
    Map<Vertex<T>, Color> colors = new HashMap<>();
    //color all the vertices with white color
    for (Vertex<T> v : adjVertices.values()) {
        colors.put(v, Color.WHITE);
    }

    //start coloring vertices , this code will handle the disconnected graph as well
    //color the first vertex with RED
    int i = 0;
    for (Vertex<T> v : adjVertices.values()) {
        // If the vertex is not yet visited
        if (colors.get(v) == Color.WHITE) {
            //if is it first vertex, mark it RED i.e. visited
            colors.put(v, Color.RED);

            boolean result = isBipartiteUtil(v, colors);
            if (!result)
                return false;
        }
    }
    return true;
}

private boolean isBipartiteUtil(Vertex<T> u, Map<Vertex<T>, Color> colors) {
    //travel all adjacent vertices
    for (Edge<T> e : u.getEdges()) {
        Vertex<T> v = e.getTo();
        // v is not yet visited
        if (colors.get(v) == Color.WHITE) {
            //color is with the alternate color of vertex v compared to parent
            if (colors.get(u) == Color.RED) {
                //if u is in red, make vertex v in green
                colors.put(v, Color.GREEN);
            } else if (colors.get(u) == Color.GREEN) {
                //if u is in green, make vertex v in red
                colors.put(v, Color.RED);
            }

            //make recursive call
            boolean result = isBipartiteUtil(v, colors);
            if (!result){
                return false;
            }
        } else if (colors.get(u) == colors.get(v)) {
            return false;
        }

    }
    // if here means graph is successfully colored in 2 color, red and green
    //graph is bipartite
    return true;
}

Complexity

  • ⏰ Time complexity: O(V+E)
  • 🧺 Space complexity: O(V)