Be the first user to complete this post

  • 0
 Add to List
Hard

403. Check if Graph is Bipartite - Adjacency Matrix using Depth-First Search(DFS)

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

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, WHITE. Let's say two sets are RED and GREEN and for the graph to be bipartite, for each edge one end has to be RED and another end has to be GREEN.  

  1. Initially color all the vertices in WHITE. 
  2. Pick a vertex with color WHITE, now color it with RED. Now check all the neighbors of the vertex. If these neighbors are in WHITE color, color these in GREEN, after that check neighbors of neighbors, If these neighbors are in WHITE color, color them in RED and so on, color the neighbors in alternate of RED and GREEN colors. Use Depth-First Search for this traversal. 
  3. Do the step above until all the vertices are in either RED or GREEN color if that happens means graph is bipartite. 
  4. 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 find an edge where both vertices are in the same color, stop the further process since the graph is not bipartite. 
  5. In this problem graph is represented as an adjacency matrix, graph[][]. So for example, if traversing from vertex u the neighbor vertex v, check graph[u][v]=1 for the edge. 

Time Complexity- O(V2)

We will improve the complexity using the Adjacency List. Click here - coming soon

Output:

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

Related Problems: