785. Is Graph Bipartite

MediumDepth-First SearchBreadth-First SearchUnion FindGraph

Problem Description

In this problem, we are dealing with an undirected graph consisting of n nodes, labeled from 0 to n - 1. The graph is represented by a 2D array, where each entry graph[u] contains a list of nodes that are adjacent to node u. The graph has certain characteristics: no node is connected to itself, there are no multiple edges between the same set of nodes, the edges are bidirectional (if node v is in graph[u], then node u will be in graph[v]), and the graph may not be fully connected.

The task is to determine whether the graph is bipartite. A graph is considered bipartite if we can split all the nodes into two distinct sets such that no two nodes within the same set are connected by an edge. In other words, each edge should connect a node from one set to a node in the other set.

Flowchart Walkthrough

Let's analyze the problem using the Flowchart. Here’s how to arrive at using the Depth-First Search (DFS) pattern for solving LeetCode 785:

Is it a graph?

Yes: The problem given is explicitly about checking if a graph is bipartite, where each node and its edges form the given graph.

Is it a tree?

No: The structure may consist of cycles and doesn't necessarily fulfill the hierarchy or non-cyclic criteria of a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: The matter in hand is to determine if a graph can be two-colored (bipartite) not about directed or acyclicity.

Is the problem related to shortest paths?

No: This task doesn't require calculating distances or shortest paths but rather an assignment of two colors to nodes in a way that no two adjacent nodes share the same color.

Does the problem involve connectivity?

Yes: To check if a graph can be bipartite, one needs to verify each connected component of the graph.

Is the graph weighted?

No: The graph for the bipartiteness problem is unweighted, with edges only representing connections without any weights.

Conclusion: Following the flowchart leads to the recommendation to use DFS. Depth-First Search is suitable in this case as it effectively explores nodes and their relations (edges), which is crucial for trying to color the graph and verify adjacencies according to bipartite rules.

Intuition

To determine if a graph is bipartite, one well-known approach is to try to color the graph using two colors in such a way that no two adjacent nodes have the same color. If you can successfully color the graph this way, it is bipartite. Otherwise, it is not.

This solution follows a depth-first search (DFS) approach. Starting from any uncolored node, we assign it a color (say color 1), then all of its neighbors get the opposite color (color 2), their neighbors get color 1, and so on. If at any point we find a conflict (i.e., we try to assign a node a color different from what it has been assigned already), we know that the graph cannot be bipartite.

The dfs function in the solution plays a crucial role in this process. It tries to color a node u with a given color c and then recursively tries to color all of the adjacent nodes with the opposite color, 3-c, because if c is 1, then 3-c is 2, and if c is 2, then 3-c is 1. If it ever finds that it cannot color a node because it has already been colored with the same color as u, the function returns False.

The array color of size n keeps track of the colors of each node, with a 0 value meaning uncolored. The outer loop of the algorithm ensures that we start a DFS on each component of the graph since the graph may not be connected, and every node needs to be checked.

The algorithm returns False as soon as it finds a coloring conflict. If no conflict is found, it returns True after all nodes have been visited, indicating the graph is bipartite.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The solution to determine if an undirected graph is bipartite involves a graph traversal algorithm, specifically Depth-First Search (DFS). The DFS is chosen here because it allows us to go as deep as possible through each branch before backtracking, which is suitable for the coloring problem where adjacent nodes need to be considered closely and immediately.

Here are the key steps of the implementation using DFS:

Initialize an array color with length equal to the number of nodes n. This array will track the color of each node. A value of 0 in this array signifies that the node has not been colored yet.
Start a loop from i = 0 to n - 1 to initiate a DFS on each node if it is not colored already. We need to ensure that disconnected parts of the graph are also considered, which is why a loop is required instead of a single DFS call.
For the DFS, define a helper function named dfs that will attempt to color a node u with a given color c. The function follows these steps:
- Assign the color c to color[u].
- Iterate over all adjacent nodes v of u.
- If the neighbor v is not yet colored (color[v] is 0), recursively call dfs(v, 3 - c) to color v with the opposite color.
- If the neighbor v is already colored with the same color as u (color[v] is c), then we have found a conflict indicating that the graph is not bipartite. Return False in this case.
If the DFS is able to color the component starting from node i without conflicts (the dfs calls all return True), the function continues to the next component by advancing in the outer loop.
If any call to dfs returns False, the main function isBipartite immediately returns False as well, as a conflict has been detected.
If the loop completes without finding a conflict, return True, signaling that the graph is bipartite, since it was possible to color the graph using two colors according to the bipartite rules.

To summarize, the solution structure consists of a DFS helper function encapsulated within the main function that manages the loop through all nodes and the color array. The algorithm relies on the properties of the DFS and a simple coloring heuristic to solve the bipartite check efficiently.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have the following undirected graph represented with n = 4 nodes:

0 -- 1
|    |
3 -- 2

In graph representation, it would be:

graph[0] contains [1, 3]
graph[1] contains [0, 2]
graph[2] contains [1, 3]
graph[3] contains [0, 2]

Now let's walk through the steps:

Initialize the color array with length 4 (since we have 4 nodes). The array starts as [0, 0, 0, 0].
Start a loop from 0 to 3. We look at each node to determine if it needs to be colored.
When i = 0, the node is not colored. We call dfs(0, 1). For clarity, dfs(u, c) means we're trying to color node u with color c.
- color[0] becomes 1.
- We look at graph[0] which is [1, 3].
- For 1, since color[1] is 0, we call dfs(1, 3 - 1) which simplifies to dfs(1, 2).
  - color[1] becomes 2.
  - We look at graph[1] which is [0, 2].
  - Node 0 is already colored with a different color, so there's no conflict.
  - For node 2, since color[2] is 0, we call dfs(2, 3 - 2) simplifying to dfs(2, 1).
    - color[2] becomes 1.
    - We look at graph[2] which is [1, 3].
    - Node 1 is already colored with a different color, so there's no conflict.
    - For node 3, since color[3] is 0, we call dfs(3, 3 - 1) which is dfs(3, 2).
      - color[3] becomes 2.
      - We look at graph[3] which is [0, 2].
      - Both nodes 0 and 2 are already colored with different colors, so there's no conflict.
- The dfs call stack for node 0 completes successfully without conflicts.
As the outer loop continues, i advances but all nodes are already colored, so no further dfs calls are necessary.
Since none of the dfs calls returned False, the graph has been successfully colored with two colors without conflict—color array is [1, 2, 1, 2].
The loop completes without finding a conflict, so the function would return True. This indicates that the graph is bipartite since it's possible to color the graph using two colors, following the rules.

Solution Implementation

1from typing import List
2
3class Solution:
4    def isBipartite(self, graph: List[List[int]]) -> bool:
5        # Depth-First Search function to determine
6        # if we can color the graph using two colors
7        def dfs(node_index, color_value):
8            # Assign the color to the current node
9            node_colors[node_index] = color_value
10            # Traverse all adjacent nodes (neighbors)
11            for neighbor in graph[node_index]:
12                # If the neighbor hasn't been colored, color it with the alternate color
13                if node_colors[neighbor] == 0:
14                    if not dfs(neighbor, 3 - color_value):  # 1 -> 2 or 2 -> 1
15                        return False
16                # If the neighbor is already colored with the same color, graph is not bipartite
17                elif node_colors[neighbor] == color_value:
18                    return False
19            # If all neighbors are colored correctly, return True
20            return True
21
22        # Get the number of nodes in the graph
23        num_nodes = len(graph)
24        # Initialize the node_colors list to zero for all nodes; 0 means not yet colored
25        node_colors = [0] * num_nodes
26        # Iterate over all nodes
27        for i in range(num_nodes):
28            # If the node hasn't been colored, start DFS and try to color it with color 1
29            if node_colors[i] == 0 and not dfs(i, 1):
30                # If DFS returns False, the graph is not bipartite
31                return False
32        # If all nodes are colored without conflict, return True
33        return True
34

1class Solution {
2    // Array 'colors' will store the colors of nodes. If uncolored, it stores 0; otherwise 1 or 2. 
3    private int[] colors;
4    // The adjacency list representation of the graph.
5    private int[][] graph;
6
7    /**
8     * Function to check if a graph is bipartite or not.
9     * A graph is bipartite if we can split its set of nodes into two independent subsets A and B
10     * such that every edge in the graph connects a node in set A and a node in set B.
11     *
12     * @param graph The adjacency list representation of the graph.
13     * @return true if the graph is bipartite, false otherwise.
14     */
15    public boolean isBipartite(int[][] graph) {
16        int numNodes = graph.length; // Number of nodes in the graph.
17        colors = new int[numNodes]; // Initialize the colors array.
18        this.graph = graph; // Assign the graph to the instance variable.
19
20        // Process every node.
21        for (int node = 0; node < numNodes; ++node) {
22            // If the node is not colored and the depth-first search (DFS) returns false,
23            // then the graph is not bipartite.
24            if (colors[node] == 0 && !depthFirstSearch(node, 1)) {
25                return false;
26            }
27        }
28        // If all nodes are successfully colored with DFS, the graph is bipartite.
29        return true;
30    }
31
32    /**
33     * Depth First Search (DFS) method to assign colors to the nodes of the graph.
34     *
35     * @param node The current node to color.
36     * @param color The color to assign to the node. It can either be 1 or 2.
37     * @return true if successful, false if there's a conflict in coloring.
38     */
39    private boolean depthFirstSearch(int node, int color) {
40        // Color the current node.
41        colors[node] = color;
42        // Visit all adjacent nodes.
43        for (int adjacent : graph[node]) {
44            // If the adjacent node is not colored, color it with the opposite color.
45            if (colors[adjacent] == 0) {
46                if (!depthFirstSearch(adjacent, 3 - color)) { // 3 - color gives the opposite color.
47                    return false;
48                }
49            } else if (colors[adjacent] == color) { // If the adjacent node has the same color, return false.
50                return false;
51            }
52        }
53        // All adjacent nodes can be colored with opposite color, return true.
54        return true;
55    }
56}
57

1class Solution {
2public:
3    // Function to check if the graph is bipartite.
4    bool isBipartite(vector<vector<int>>& graph) {
5        int numNodes = graph.size(); // Get the number of nodes in the graph.
6        vector<int> colors(numNodes, 0); // Vector to store colors for each node, initialized to 0.
7
8        // Iterate through each node in the graph.
9        for (int node = 0; node < numNodes; ++node) {
10            // If the node is uncolored and the DFS coloring fails, the graph is not bipartite.
11            if (colors[node] == 0 && !dfsColorGraph(node, 1, colors, graph)) {
12                return false;
13            }
14        }
15        // All nodes have been successfully colored without conflicts, hence the graph is bipartite.
16        return true;
17    }
18
19    // Helper function to perform DFS and color the graph.
20    bool dfsColorGraph(int currentNode, int currentColor, vector<int>& colors, vector<vector<int>>& graph) {
21        colors[currentNode] = currentColor; // Color the current node.
22
23        // Iterate through all adjacent nodes of the current node.
24        for (int adjacentNode : graph[currentNode]) {
25            // If the adjacent node is uncolored, attempt to color it with the opposite color.
26            if (colors[adjacentNode] == 0) {
27                if (!dfsColorGraph(adjacentNode, 3 - currentColor, colors, graph)) {
28                    return false; // If coloring fails, the graph is not bipartite.
29                }
30            }
31            // If the adjacent node has the same color, the graph cannot be bipartite.
32            else if (colors[adjacentNode] == currentColor) {
33                return false;
34            }
35        }
36        // All adjacent nodes can be colored with the opposite color.
37        return true;
38    }
39};
40

1// Function to determine if a graph is bipartite
2// A graph is bipartite if the nodes can be divided into two sets such that
3// no two nodes in the same set are adjacent.
4function isBipartite(graph: number[][]): boolean {
5    // `n` stores the total number of nodes in the graph
6    const n: number = graph.length;
7    // `isValid` keeps track of whether the graph is bipartite
8    let isValid: boolean = true;
9    // `colors` array will store the colors assigned to each node,
10    // where 0 means uncolored, 1 is the first color, and 2 is the second color
11    let colors: number[] = new Array(n).fill(0);
12  
13    // Helper function to perform depth-first search and color the nodes
14    function dfs(nodeIndex: number, color: number, graph: number[][]): void {
15        // Color the current node
16        colors[nodeIndex] = color;
17        // Determine the color to be given to adjacent nodes (1 or 2)
18        const nextColor: number = 3 - color;
19      
20        // Iterate over all adjacent nodes
21        for (let adjacentNode of graph[nodeIndex]) {
22            // If the adjacent node is not yet colored, color it with nextColor
23            if (!colors[adjacentNode]) {
24                dfs(adjacentNode, nextColor, graph);
25                // If at any point, the graph is found not to be valid, exit early
26                if (!isValid) return;
27            } else if (colors[adjacentNode] !== nextColor) {
28                // If the adjacent node has been colored with the wrong color,
29                // the graph is not bipartite
30                isValid = false;
31                return;
32            }
33        }
34    }
35
36    // Iterate over each node, coloring them if not already colored,
37    // while the graph remains valid
38    for (let i = 0; i < n && isValid; i++) {
39        if (!colors[i]) {
40            // Start coloring nodes from the first color
41            dfs(i, 1, graph);
42        }
43    }
44    // Return whether the graph is bipartite
45    return isValid;
46}
47

Time and Space Complexity

The provided code defines a function isBipartite which checks if a given graph can be colored with two colors such that no two adjacent nodes have the same color, which is a characteristic of a bipartite graph.

Time Complexity

The time complexity of the code is O(V + E), where V is the number of vertices in the graph, and E is the number of edges. This is because the function uses a Depth-First Search (DFS) to traverse the graph. Each node is visited exactly once, and for each node, all its adjacent nodes are explored. Visiting each node takes O(V) time, and exploring adjacent nodes (edges) takes O(E) time in total.

Space Complexity

The space complexity is also O(V). The color array is used to store the color of each node and its size is proportional to the number of nodes (n), which is V. The space is also used by the call stack due to the recursive DFS calls, which in the worst case can go as deep as V levels, if the graph is a long path or a chain of nodes. Therefore the total space used by the algorithm is proportional to the number of nodes.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Contain cycles

There are multiple ways to traverse

Connected

Has no cycle

I don't know