The problem of determining whether a graph is or not is very significant not just for interviews, it also helps in solving real-life problems. For example, we use it when football leagues are being hosted to see which player has played for what organizations and various other examples can be stated. This discussion focuses on the problem of determining whether a graph is bipartite or not. bipartite We need an in-depth understanding of the bipartite graph and graph coloring to solve this problem along with the knowledge of BFS, DFS, and cyclic-acyclic graphs. So, let’s first check out some definitions related to it: A graph that has even 1 cycle i.e. it is closed in a cyclic way is called a whereas if there is no closed shape in a circular fashion in a graph then it is called an acyclic graph. If there is a closed shape in an undirected graph, it will definitely be a cycle whereas, for a directed graph, this might not be true. This is also shown in the images below: Cyclic and Acyclic Graphs: cyclic graph The image shows that an undirected graph with a closed shape will be cyclic but a directed graph may or may not be cyclic. For a directed graph to be cyclic, the directions of the edges should enclose in a cyclic manner. If we have only 2 colors (say Red and Blue) and we can color every vertex of the graph such that both the vertices of every edge of the graph are not the same colored then the graph is 2-colorable. In simple words, we can say that the alternate vertices should have the same color or 2 adjacent vertices should not have the same color. Colorable Graph: In the above image, the first graph is 2-colorable as no 2 adjacent vertices are colored the same. In the second graph, the adjacent vertices V1 and V5 have the same color, hence the Graph is not 2-colorable. From the above image, we can see that the Cyclic graph with an even number of edges is 2-colorable and the cyclic graph with an odd number of edges is not 2-colorable. This is true for all the graphs having cycles because the vertices get divided into pairs (one vertex will be red-colored and the other will be blue colored) in case of Even Sized Cycle (Cycle with even edges/vertices) but one vertex is left off when we have an Odd-Sized Cycle (Cycle with odd edges/vertices). Also, for a graph with multiple cycles to be a 2-colorable graph, all the cycles must be Even Sized Cycles. This is shown in the image below: Non-bipartite graph because of the presence of an Odd Sized Cycle. So, we have understood the colorable nature of Cyclic Graphs. What about acyclic graphs? Let us look at some examples shown below: The images show various acyclic graphs and they are all 2-colorable. In general, all acyclic graphs are 2-colorable. The reason behind this is very simple. When a graph is cyclic, there are neighbors in both directions and when an odd-sized cycle is present, the neighbor of one of those sides happens to be of the same color. In an acyclic graph, there might be neighbors in 2 directions but the directions in an acyclic graph tend to be the same linearly. Hence, we can say that all acyclic graphs are always 2-colorable. So, finally, we can set some rules (from our observations) for a graph to be 2-colorable: If a graph is cyclic then for it to be a 2-colorable graph, all its cycles should be Even Sized Cycles. The extension of the above point is that all the Cyclic graphs that have even one Odd Sized cycle will be non-2-colorable. All the acyclic graphs are 2-colorable. Now, let us come to our question i.e. Bipartite Graphs. Bipartite Graph: If the vertices of a graph can be divided into 2 such subsets that are mutually exclusive (intersection should be null set) and mutually exhaustive (union is set of all vertices) and the edges are across the 2 sets, not within the same set, then it is said to be bipartite. Bipartite Graph Example Non-Bipartite Graph Example (As we can see, there is an edge V0-V4 for which the vertices lie in the same set. You may try to make any possible set but will always find an edge that is within the same set. Hence, the above graph is non-bipartite.) So, have you observed something from the above examples? It can be observed that the 1st graph that was bipartite was also 2 colorable. Also, the second graph is not bipartite and it is not 2-colorable also. Hence, we can say that a bipartite graph is nothing but a 2-colorable graph. Quick Observations: Since a graph with Odd-Sized Cycle is never 2-colorable, it is right to say that it will never be bipartite. Moreover, if there are multiple cycles in a graph, all have to be Even-Sized Cycles (number of edges should be even) for the graph to be bipartite. If a graph is acyclic (without a cycle), it will definitely be bipartite as it is always 2-colorable. If a graph has a self-loop i.e. a vertex of a graph has an edge to itself, it is non-bipartite because we cannot color the same vertex with 2 different colors. Approach 1: Assigning colors to each vertex (BFS) Problem Statement: We have to determine whether a graph given to us is bipartite or not. We have studied above that a 2-colorable graph is bipartite. So, let us try to color every vertex of the graph one by one by taking care that the neighbors should not have the same color. If we are able to color the graph successfully using 2-colors, the graph will be bipartite else not. Thought Process - Algorithm: Pick 2 numbers depicting 2 colors to be done on the vertices of the input graph. (Let us say the numbers are 1 and 2 and uncolored vertex will be depicted by number 0) Pick any vertex as a source vertex of the graph and color it using the first color i.e 1. Color all the adjacent vertices of the source vertex with the second color and color their adjacent vertices with the first color again and so on. (Use a color array of size equal to the number of vertices to maintain which vertex has what color). This is done to know the color of all the adjacent vertices when we are about to color one vertex. If all the vertices are colored successfully without violation of 2-colorable graph i.e. if we don’t have the situation of coloring 2 adjacent vertices with the same color, then it is bipartite otherwise, as soon as a vertex is found having the same color as adjacent vertex, return false that the graph is not bipartite. Also, don’t forget that the graph can be unconnected. So, do this procedure for every component of the graph. C++ Code Using Adjacency Matrix As the Input Input: The graph will be input to us in the form of an adjacency matrix of size V x V where V is the number of vertices in the graph. It will be a binary matrix depicting whether there is an edge from a vertex V1 to another vretx V2 or not. An example of the input is shown below:** ** The above image depicts an example of the input matrix. There is an edge from V0 to V1 hence we have Matrix[V0][V1] = 1 and so on. #include<bits/stdc++.h>
using namespace std;
// colors:
// red = 1 and blue = 2;
bool isBipartiteHelper(int graph[100][100],int vertices, int src, vector<int> colors) {
    //coloring the source vertex red 
    colors[src] = 1;

    // queue needed for BFS Traversal
    queue<int> que;
    que.push(src);

    while(!que.empty()) {
        int front = que.front();
        que.pop();

        // If self Loop exists, then adjacency matrix 
        // will have 1 in the diagonal element
        // and we have to return false in case of  adjacency matrix
        if(graph[front][front] == 1) return false;

        for(int i=0;i<vertices;i++) {

            // edge exists and the adjacent vertex i is uncolored
            if(graph[front][i] == 1 && colors[i] == 0) {
                if(colors[front] == 1) colors[i] = 2; //color     alternatively
                else colors[i] = 1;
                que.push(i);
            } else if(graph[front][i] == 1 && colors[i] == colors[front]) { //edge exists and same color of adj vertex
                return false;
            }
        }
    }

    return true; //all vertices of this component can be colored
    // as per the rule of 2-colorable graph 
}

bool isBiPartite(int Graph[100][100], int vertices) {
    vector<int> colors(vertices,0);

    // Assume i to be a source vertex of current component
    for(int i=0;i<vertices;i++) {
        // If i is uncolored
        if(colors[i] == 0) {
            // if any component is non bipartite, graph is also non bipartite
            if(isBipartiteHelper(Graph,vertices,i,colors) == false) return false;
        }
    }

    return true; //if all the components are bipartite then the entire graph is bipartite
}
int main() {
   
    int vertices;
    cin>>vertices;

    int Graph[100][100];

    for(int i=0;i<vertices;i++) {
        for(int j=0;j<vertices;j++) {
            cin >> Graph[i][j];
        }
    }

    cout<<"The given graph ";
    if(isBiPartite(Graph,vertices) == true) 
         cout<<"is bipartite\n";
    else cout<<"is not bipartite\n";
    return 0;
} Try the code with InterviewBit Output: Analysis of the approach: The code covers the corner case of a graph having a self-loop but the code does not cover the case of a graph having parallel edges i.e. multiple edges between the same pair of vertices as shown below: The case of a graph being divided into multiple unconnected components is covered. The time complexity is O(V2) because we are traversing an adjacency matrix of size V x V. Time Complexity: The graph is represented using O(V2) space using the adjacency matrix but this is not the space complexity. Other than that, O(V) space is the auxiliary space used for storing the colors on each vertex. Space Complexity: (V is the number of vertices in the above complexities.) Let us look at an optimized way to solve this problem using the same approach as above. To optimize the solution, we will use an adjacency list as input in place of a matrix. C++ Code Using Adjacency List Input: The input will be an adjacency list. Now, the user has to input all the edges in the form of source-destination vertex pairs. Also, we have considered the graph to be undirected in this case. So, if the user enters an edge V0-V1 thinking that there is an edge from V0 to V1, there will also be an edge from V1 to V0 that will be inserted automatically because of the consideration that the graph is undirected. #include <bits/stdc++.h>
using namespace std;

// colors: red = 1 and blue = 2
bool isGraphBipartite(vector<int> list[], int vertices) {
    
    // make a vector for storing
    //  colors of all the vertices
    // Since all the vertices are 
    // initially uncolored,
    // fill the vector with 0s
 
    vector<int> colors(vertices,0);

    // queue of pair will be made
    // as we will store the vertex
    // along with its color

    queue<pair<int,int> > que;
    
    // The same logic for non connected components
    // that we did using adjacency matrix
    // will be applied here

    for(int i=0;i<vertices;i++) {

        // check whether the taken
        // source vertex for current
        // component is not colored
        // If found uncolored
        // apply BFS on the component

        if(colors[i] == 0) {
            
            pair<int,int> srcVertex;
            srcVertex.first = i;
            srcVertex.second = 1;
            que.push(srcVertex);
            colors[i] = 1; //color the source vertex of current component red
            
            // BFS on current component of the graph
            while(!que.empty()) {
                pair<int,int> front = que.front();
                que.pop();

                int currVertex = front.first;
                int currVertexColor = front.second;

               // traversing adjacent vertices of current vertex
                for(int adjVtx: list[currVertex]) {
                    if(colors[adjVtx] == currVertexColor) return false;
                    else if(colors[adjVtx] == 0) {
                        if(currVertexColor == 1) colors[adjVtx] = 2; //coloring alternatively
                        else colors[adjVtx] = 1;
                        
                        pair<int,int> adjPair;  
                        adjPair.first = adjVtx;
                        adjPair.second = colors[adjVtx];
                        que.push(adjPair); 
                    }
                }
            }
        }
    }

    return true;
}
int main() {
   int vertices, edges;
   cin>>vertices>>edges;

   vector<int> list[vertices];

   for(int i=0;i<edges;i++) {
       int sv,av;
       cin>>sv>>av;

       list[sv].push_back(av);
       list[av].push_back(sv);
   }

   cout<<"The given graph is";
   if(isGraphBipartite(list,vertices) == true)       
        cout<<" bipartite\n";
   else cout<<" not bipartite\n";

   return 0;
} Output: Analysis of Approach: This code just uses an adjacency list instead of a matrix. The self-loop case is covered and the multiple unconnected components case is also covered in this code. However, the case of  a graph having parallel edges is not covered. As already discussed above, the time complexity is O(V+E). Time Complexity: Space Complexity: Used adjacency matrix to store the graph but the auxiliary space is O(V) i.e. storing the colors at each vertex. Try to solve this problem by the same approach i.e. coloring all the vertices but with DFS (Recursion) rather than BFS.  This means that you have to apply the same approach of coloring the graph but, we have used BFS to do so. You should try this out using recursion (DFS) now. Follow up for this approach: Approach 2: Visiting Levels Approach (BFS) Algorithm: The approach is based on checking the cycles in the graph. If the graph is acyclic, we will return true because acyclic graphs are 2-colorable and hence bipartite but if there is a cycle, we need to find whether it is of odd length or even. If the cycle is of odd length, the same vertex will be visited again on different levels in the Euler tree (recursion tree) whereas if the cycle is of even length, the same vertex will be visited again on the same level. As shown above, we are traveling using BFS and exploring all the unvisited adjacent vertices of a source vertex. In the case of the first graph i.e. a graph with Odd Sized Cycle, V4 is visited on Level 2 and Level 3 of the same BFS Tree whereas, in the case of a graph with Even Length Cycle, the vertex that is visited again (V3 in this case) is visited at the same level. So, in the case of an odd length cycle, the vertex that determines the cycle will be at two different levels whereas, in the case of an even length cycle, it will be at the same level. So, once we get a vertex that repeats itself (it will happen in a cyclic graph), we check when the vertex was last visited, was its level the same or not. Again, do not forget that the graph can be divided into multiple unconnected components. So, BFS will be applied to each component. C++ Code for Second Approach Input: The input will be an adjacency list. Now, the user has to input all the edges in the form of source-destination vertex pairs. Also, we have considered the graph to be undirected in this case. So, if the user enters an edge V0-V1 thinking that there is an edge from V0 to V1, there will also be an edge from V1 to V0 that will be inserted automatically because of the consideration that the graph is undirected. When applying BFS, we do not push just the vertex into the queue, we push it with the Level on which it is being visited, and also, it is marked visited. So, when we encounter the same vertex again, we will see what was the Level on which it was previously visited. If the Level is the same as that of the current visit, the component of the graph is Even Cycled and this component is bipartite but not the entire graph. For the entire graph to be bipartite, all the components should either be acyclic or of Even Length Cycles. Thought Process: #include<bits/stdc++.h>
using namespace std;

bool isComponentBipartite(vector<int> list[],int src,vector<int> &visited) {
    queue<pair<int,int> > que; //this pair corresponds to vertex -> level
                               // which means vertex and the level in which
                              //  it appeared in the recursion tree
                              // of BFS

    pair<int,int> srcPair;
    srcPair.first = src;
    srcPair.second = 0; //initially source is at 0 level in recursion tree
    que.push(srcPair);

    // Apply BFS
    while(!que.empty()) {
        pair<int,int> front = que.front();
        que.pop();

        if(visited[front.first] != -1) { //if the vertex (i.e. front.first) is already visited 
            //since the vertex is already visited, check if the levels are not same
            if(visited[front.first] != front.second) { 
                return false; //odd length cycle detected
            }
        } else {
            visited[front.first] = front.second;
        }

        //now visit all the adjacent vertices
        for(int adj : list[front.first]) {
            if(visited[adj] == -1) {
                pair<int,int> adjPair;
                adjPair.first = adj;
                adjPair.second = front.second + 1;
                que.push(adjPair);
            }
        }
    }

    return true; //either no cycle detected or all cycles were even length
}

int main() {
    int vertices,edges;
    cin>>vertices>>edges;

    vector<int> list[vertices];
    
    for(int i=0;i<edges;i++) {
        int sv;
        int dv;
        cin>>sv>>dv;

        //since non-directed graph, edges will be bi-directional
        list[sv].push_back(dv);
        list[dv].push_back(sv);
    }

    //initially no vertex is visited and hence all are at level -1
    vector<int> visited(vertices,-1);
  
  //for non connected components as we need to check whether every component is bipartite or not
  for(int i=0;i<vertices;i++){
    if(visited[i] == -1){
        bool ans=isComponentBipartite(list,i,visited);
        if(ans == false){
            cout<<"The graph is not bipartite";
                return 0;
        }
      }  
    }
      
    cout<<"Graph is bipartite";
    return 0;
} Output: This code does not cover the case of a graph being divided into multiple components. Quick Note: Since we have used an adjacency list for graph traversal (BFS), the time complexity is O(V + E). This is the same as the Coloring Approach i.e. if we would have used the adjacency matrix, the Complexity would have been O(V2). So, we used the adjacency list directly this time to optimize the solution. Time Complexity: In BFS, we are using a queue that can store at maximum all the V vertices. Hence the space complexity can be termed O(V). O(V + E) is the space of the adjacency list but not the space complexity as it was input space. Space Complexity: Conclusion So, we have learned 2 different methods of detecting whether a graph is bipartite or not. You may use any approach that you find intuitive as both are the same in terms of complexities (time and space). However, the Graph Coloring Approach is used more as it is easier to understand and explain and shows the relation of a bipartite graph with a 2-colorable graph more clearly.

How to Check if a Graph is Bipartite in C++

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

How to Reverse a Sentence Using Recursion in C++ and Java

Directed Acyclic Graphs — a Blockchain frenemy?

The Noonification: What is the InfiniteNature-Zero AI Model? (11/19/2022)

10 Most Popular Programming Languages | 2022

14 Big Ideas for 2023: Why Crypto is Here to Stay

How to Reverse a Sentence Using Recursion in C++ and Java

Directed Acyclic Graphs — a Blockchain frenemy?

The Noonification: What is the InfiniteNature-Zero AI Model? (11/19/2022)

10 Most Popular Programming Languages | 2022

14 Big Ideas for 2023: Why Crypto is Here to Stay

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps