Is Graph Bipartite?

Approach: 

 

The idea is to try out all possible combinations of dividing the nodes into 2 Sets and try to find a combination that satisfies the condition of a bipartite graph.

 

For that, we will be using the concept of bit masking. Let’s take ‘N’ = 3 and an integer ‘X’ = 5.

The binary representation of 5 is “101” which implies that nodes 1,3 are in set A and node 2 is in set B, in “101”  node 1 is the LSB, and node 3 is MSB. Nodes that have their corresponding bits set are put in Set A and the remaining nodes in Set B. 

 

So, if a graph has ‘N’ nodes we need to have an integer that has its binary representation ‘n’ bits long, which is (2^n)-1. So, every integer from 0 to (2^n)-1 represents a different combination of dividing the nodes into 2 Sets.
 

Now, after dividing the nodes into two Sets we just have to check that for every given edge of the graph the two nodes are in different sets or not, for that we just have to look at their corresponding bits if they both are set or unset means that they are in the same set otherwise not.

 

Here is the algorithm:

• Run a loop from 0 to (2^n)-1 (say iterator ‘i’)
  • Initialize a variable “flag”=0, “flag” is equal to 0 means the graph is bipartite otherwise not.
    • Iterate over the edges of the given graph (say iterator ‘j’)  and check whether the 2 nodes lie in the same set or not.
      • If both lie in the same then set a flag to 1 and break from the loop as the graph is not bipartite.
  • If the flag is equal to 0 means the graph is bipartite so return True.
• Return False.

Approach: 
 

If we fix the Set of node ‘x’, let’s say it belongs to Set A then the nodes which are immediate neighbors of the node ‘x’ should belong to Set B as, if they belong to the Set A then the condition of bipartite fails. The same condition can be applied for the nodes which are immediate neighbors of the node ‘x’.  So, after fixing the Set of any node in the connected component of the graph, the Set of all the other nodes will be fixed.

 

Let's denote Set A by 0 and Set B by 1. For every node which is not been visited yet, we run a recursive function check(node, c, adj, color, vis),(where “node” is the current node we are at, ‘c’ either 0 or 1, denoting the set of the “node”, “adj” is the adjacency list of all the nodes, adjacency list stores all the nodes which are directly connected to the ith node,” color ” is the vector which tells the Set of the ith node, “vis” is the vector which keeps track of every node whether it has been traversed or not) and try to assign Set to every node in its connected component if 2 nodes that are immediate neighbors are in the same Set then we will return false.

 

Here is the algorithm:

• check function:
  • Assign color to node, color[node] = c.
  • Mark the node visited, vis[node] = 1.
  • Traverse the adjacency list of the current node “node” (say iterator ‘i’)
    • If adj[node][i] is not visited
      • if( ! check( adj [node][i], c^1, adj, color, vis) ) , graph is not bipartite
        • Return False.
    • Else
      • If color[adj[node][i]] is equal to ‘c’
        • Return False.
  • Return True.

• given function:
  • Declare a 2-d vector “adj” for storing the adjacency list of all the nodes.
  • Create an adjacency list. This can be done by running a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ push EDGES[i][0] in list ADJ[EDGES[i][1]] and EDGES[i][1] in list ADJ[EDGES[i][0]].
  • Declare a vector “color” for marking the Set each node corresponds to, “vis” for marking nodes visited.
  • For every node from 0 to ‘n’ -1 (say iterator ‘i’)
    • If node ‘i’ is not visited
      • If the condition of the bipartite graph fails
        • Return false.
• Return true.

Approach: 

 

The basic idea of this approach is similar to the idea of approach 2 the only difference is that in approach 1 we use a recursive approach to assign Set to every node here we will be doing this iteratively with the help of Bfs that is we will be doing level order traversal.
 

For the implementation of this approach we will be using a data-structure “queue” as we want level order traversal so if a node ‘x' enters before a node “y” in the queue then “x” will be processed before “y”.

 

The idea of this approach is to traverse the graph in level order starting from the “source” node and putting in node “source” in Set A and explore all the neighboring nodes, if the neighboring node is not visited yet then we will make it visited, put this node in Set B and put in into “queue” otherwise we have to check the Set of the node, let say “x”, which has been visited. If the “source” node has the same set as the node “x” then the graph is not bipartite and we will return false otherwise continue the above process until the “queue” is not empty.

 

As the graph may not be connected we have to do the above-discussed algorithm for every connected component of the graph.

 Here is the algorithm:

• Declare a 2-d vector “adj” for storing the adjacency list of all the nodes.
• Create an adjacency list. This can be done by running a loop where ‘i’ ranges from 0 to ‘M’-1 and for each ‘i’ push EDGES[i][0] in list ADJ[EDGES[i][1]] and EDGES[i][1] in list ADJ[EDGES[i][0]].
• Declare a vector “vis” for marking nodes visited.
• Declare a vector “color” for marking the Set of each node.
• Declare a queue to perform “Bfs”.
• For every node from 0 to ‘n’ -1 (say iterator ‘i’)
  • If node ‘i’ is not visited
    • Push the node ‘i’ in the queue, mark the node visited, and mark the set of node ‘i’ to 0.
    • while(queue is not empty)
      • Node = queue.front().
      • Pop node “node” from the queue.
      • Traverse the adjacency list of the current node “node” (say iterator ‘i’)
        • If adj[node][i] is not visited
          • Push adj[node][i] in the queue.
          • Mark adj[node][i] visited.
          • Make the set opposite to node “node”.
        • Else
          • If color[adj[node][i]] is equal to color[node]
            • Return False.
• Return True.