Nerd For Tech
Published in

Nerd For Tech

Is Graph Bipartite? — Day 76(Python)

Photo by Benjamin Smith on Unsplash

Today’s question is from leetcode’s daily coding challenge. This question is frequently asked in Facebook interviews. Let us look into the problem statement.

785. Is Graph Bipartite?

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.

Example 1:

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:

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}.

Constraints:

  • 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.

Before we start with the algorithm, let us understand what is Bipartite.

According to Wikipedia,

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

Bipartite Graph

Let us take an example and see if we can convert it into a Bipartite Graph.

Example 1.

Since the above graph is a complete graph it is not possible to make it a Bipartite graph.

Example 2.

Bipartite Graph

To solve this problem, we need to assign colors to each node. For example, suppose we make use of two colors, Black and White. The node from which we start will be colored white. The neighbors of these nodes will be colored black, then the neighbors of the current node will be colored white. We will keep on doing this in a cycle until we have colored all the nodes.

How can we know if we can have a bipartite graph?

As we keep coloring the graphs, if at any point we reach a previously colored node, we need to check if the current color of the node is equal to the intended color of the node. If yes, we can continue with the coloring else the graph is not bipartite.

Let us take an example,

Example 1:

Let us start from node 0. We will be coloring it black.

Now, all the neighboring nodes of 0 are colored white. In this case, 1, 2, and 3 are colored white.

Next, the neighbors of 1 are colored black. Neighbors of 1 are 0 and 2. But we have already colored 2 with white which means there is a conflict. Therefore we need to return False.

Example 2.

Let us start from node 0. We will be coloring it black.

Next, we will color the neighbors of node 0 with white. Neighbors of node 0 will include 1 and 3.

Next, we will color the neighbors of 1 with black. Neighbors of node 1 will be colored black. Neighbors of 1 will include nodes 2 and 0.

Next, we will color the neighbors of 2 with white. Neighbors of 2 will include 3 and 1. Since we have already colored it we need not color it again. Similarly, we need to color neighbors of node 3. Since they are already colored and there is no conflict we need not color them again.

We can use BFS or DFS to solve this problem. We will be solving this problem using both BFS and DFS.

Solution using BFS.

Since we have solved BFS problems before, I would not be explaining the BFS algorithm in depth.

We need a dictionary that can keep track of colors for each node. One thing to keep in mind, in the problem statement it is mentioned that the graphs are not necessarily connected. Hence we will have to use a loop so that we traverse through all the nodes. Another point to keep in mind, if the current node is already visited, then we need to make sure the color of this node is what we intend to paint, else we will return False.

Let us look into the code snippet.

class BipartiteChecker:
def isBipartite(self, graph: List[List[int]]) -> bool:
#Dictionary
color = {}
for each_node in range(len(graph)):
#if not visited already
if each_node not in color:
neighbors = [each_node]
next_neighbors = []
curr_color = True
while neighbors:
out = neighbors.pop(0)
if out in color:
#Check if current color is intended color
if color[out] != curr_color:
return False
else:
color[out] = curr_color
for i in graph[out]:
next_neighbors.append(i)
if neighbors == []:
curr_color = not curr_color
neighbors, next_neighbors = next_neighbors,neighbors
return True

Complexity analysis.

Time Complexity

Since each time we are visiting nodes that are connected through the edges the time complexity is O(N+E) where N is the number of nodes and E is the number of edges.

Space Complexity.

Since we are using a dictionary to store the colored nodes, the space complexity is O(N) where N is the number of nodes.

Let us see the code snippet using DFS.

class BipartiteChecker:
def isBipartite(self, graph: List[List[int]]) -> bool:
color = {}
def dfs(curr_node, curr_color):

if curr_node in color:
if color[curr_node] != curr_color:
return False
else:
return True
else:
color[curr_node] = curr_color
for each_node in graph[curr_node]:
if not dfs(each_node, not curr_color):
return False
return True

for all_node in range(len(graph)):
if all_node not in color:
if not dfs(all_node, True):
return False
return True

Complexity analysis.

Time Complexity

Since each time we are visiting nodes that are connected through the edges the time complexity is O(N+E) where N is the number of nodes and E is the number of edges.

Space Complexity.

Since we are using a dictionary to store the colored nodes, the space complexity is O(N) where N is the number of nodes.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store