785. Is Graph Bipartite
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 nodesn
. This array will track the color of each node. A value of0
in this array signifies that the node has not been colored yet. -
Start a loop from
i = 0
ton - 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 nodeu
with a given colorc
. The function follows these steps:- Assign the color
c
tocolor[u]
. - Iterate over all adjacent nodes
v
ofu
. - If the neighbor
v
is not yet colored (color[v]
is0
), recursively calldfs(v, 3 - c)
to colorv
with the opposite color. - If the neighbor
v
is already colored with the same color asu
(color[v]
isc
), then we have found a conflict indicating that the graph is not bipartite. ReturnFalse
in this case.
- Assign the color
-
If the DFS is able to color the component starting from node
i
without conflicts (thedfs
calls all returnTrue
), the function continues to the next component by advancing in the outer loop. -
If any call to
dfs
returnsFalse
, the main functionisBipartite
immediately returnsFalse
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 EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach. Suppose we have the following undirected graph represented with n = 4
nodes:
10 -- 1 2| | 33 -- 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 length4
(since we have4
nodes). The array starts as[0, 0, 0, 0]
. -
Start a loop from
0
to3
. We look at each node to determine if it needs to be colored. -
When
i = 0
, the node is not colored. We calldfs(0, 1)
. For clarity,dfs(u, c)
means we're trying to color nodeu
with colorc
.color[0]
becomes1
.- We look at
graph[0]
which is[1, 3]
. - For
1
, sincecolor[1]
is0
, we calldfs(1, 3 - 1)
which simplifies todfs(1, 2)
.color[1]
becomes2
.- 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
, sincecolor[2]
is0
, we calldfs(2, 3 - 2)
simplifying todfs(2, 1)
.color[2]
becomes1
.- 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
, sincecolor[3]
is0
, we calldfs(3, 3 - 1)
which isdfs(3, 2)
.color[3]
becomes2
.- We look at
graph[3]
which is[0, 2]
. - Both nodes
0
and2
are already colored with different colors, so there's no conflict.
- The
dfs
call stack for node0
completes successfully without conflicts.
-
As the outer loop continues,
i
advances but all nodes are already colored, so no furtherdfs
calls are necessary. -
Since none of the
dfs
calls returnedFalse
, 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.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.