# Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)

**Objective: **Given a graph represented by the adjacency List, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not.

Earlier we have solved the same problem using Adjacency Matrix (Check if Graph is Bipartite – Adjacency Matrix) with Time complexity: O(V^{2}) where V – No of vertices in the graph. In this article, we will solve it using the Adjacency List which will reduce the time complexity to O(V+E), where V – no of vertices and E – No of edges. Before we proceed, if you are new to Bipartite graphs, lets brief about it first

**Bipartite Graphs** OR **Bigraphs** is a graph whose vertices can be divided into two independent groups or sets so that for every edge in the graph, each end of the edge belongs to a separate group. There should not be any edge where both ends belong to the same set. Please read “Introduction to **Bipartite Graphs** OR **Bigraphs“.**

**Example:**

Please read the following recommended articles before continue

**Approach:** Coloring of vertices – Check if Graph Two-Colorable

Choose three colors- ** RED**,

**,**

*GREEN***. As you know in Bipartite graph, both ends of each edge belong to separate group, Let’s say here two groups are**

*WHITE***and**

*RED***and for a graph to be bipartite, for each edge- one end has to be**

*GREEN***and another end has to be**

*RED***.**

*GREEN*- Initially color all the vertices in
and as algorithm advances, these vertices will be colored as*WHITE*or**RED**.*GREEN* - Pick a vertex with color
, now color it with*WHITE*. Now check all the neighbors of vertex. If these neighbors are in*RED*color, color these in*WHITE*, after that check neighbors of neighbors, If these neighbors are in*GREEN*color, color them in*WHITE*and so on, color the neighbors in alternate of*RED*and*RED*colors. Use Depth-First Search for this traversal.*GREEN* - Do the step above until all the vertices are in either
or*RED*color if that happens means graph is bipartite.*GREEN* - During this process, if you find a neighbor vertex which is already colored in the same color as the current vertex or in other words you found an edge where both vertices are in the same color, stop the further process since the graph is not bipartite.

**Time Complexity**– O(V+E) where V – no of vertices and E – No of edges

**Code:**

**Output:**

Graph is Bipartite: false -------------------------- Graph is Bipartite: true