Developing strength in the area of graph is a great outlet to sharpen your programming craft. It also has a ripple effect. You wander with a queue, a stack, a priority queue, and whatnot, while dealing with a graph. Developing strength in the area of graph is a great outlet to sharpen your programming craft. To get a glimpse of it, in today’s issue, I’d like to communicate briefly the idea of a Bipartite Graph and its implementation in a very gentle manner. Let’s go. The whole idea with graph is that we make connections between things, which form a network along its perimeter. A connection sets a bond between two nodes. And if it is possible for two distinct colors to be exhausted on each edge, then we wind up calling it a Bipartite. connections between things if it is possible for two distinct colors to be exhausted on each edge, then we wind up calling it a Bipartite Since the structure of a graph can be as broad as the ocean and simultaneously it can be as high as mountains, we can either traverse broadly by exploiting neighbor nodes before descendants, or can go deep by striking descendants first. These two are the most common techniques to lean into when information is organized like this. The first one is BFS (Breadth First Search), and the latter one is DFS (Depth First Search). Let’s lay out what steps the BFS Algorithm takes internally for the Bipartite check: Let’s lay out what steps the BFS Algorithm takes internally for the Bipartite check: entering the function with a starting node, the first thing it does is enqueue the starting node into the queue data structure
gives the starting node a color (0 | 1, model as 2 distinct colors) in the colors[] array
runs a loop until the queue is empty, and on each iteration:

dequeues a node
fires yet another loop to see all of its neighbors and look for the following things for each neighbor:

If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards
else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue.




Finally, the queue becomes empty here, which means it didn’t fall into the identical color consequences. Sure thing, we can safely say the given graph conforms to the bipartite rules. entering the function with a starting node, the first thing it does is enqueue the starting node into the queue data structure entering the function with a starting node, the first thing it does is enqueue the starting node into the queue data structure gives the starting node a color (0 | 1, model as 2 distinct colors) in the colors[] array gives the starting node a color (0 | 1, model as 2 distinct colors) in the colors[] array runs a loop until the queue is empty, and on each iteration:

dequeues a node
fires yet another loop to see all of its neighbors and look for the following things for each neighbor:

If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards
else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue. runs a loop until the queue is empty, and on each iteration: dequeues a node
fires yet another loop to see all of its neighbors and look for the following things for each neighbor:

If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards
else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue. dequeues a node dequeues a node fires yet another loop to see all of its neighbors and look for the following things for each neighbor:

If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards
else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue. fires yet another loop to see all of its neighbors and look for the following things for each neighbor: If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards
else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue. If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards If the neighbor node is not yet colored, it gives a color opposed to the dequeued node’s color and enqueues that afterwards else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue. else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away, but if it has the opposite color, then continue. Finally, the queue becomes empty here, which means it didn’t fall into the identical color consequences. Sure thing, we can safely say the given graph conforms to the bipartite rules. Finally, the queue becomes empty here, which means it didn’t fall into the identical color consequences. Sure thing, we can safely say the given graph conforms to the bipartite rules. Here’s the BFS implementation in TypeScript: Here’s the BFS implementation in TypeScript: Here’s the BFS implementation in TypeScript: enum COLORS = {
  COLORED_RED: 0,
  COLORED_GREEN: 1,
  NOT_COLORED: -1
}

const checkBipartiteBFS = function (
  startingNode: number,
  adj: number[][],
  colors: COLORS[]
): boolean {
  // define a queue and give starting node a color and enqueue it
  const queue: number[] = [];
  colors[startingNode] = 0;
  queue.push(startingNode);

  // run a loop until queue becomes empty
  while (queue.length !== 0) {
    // dequeues a node
    const node = queue.shift() as number;

    // look for its neighbour nodes and do those checking stuffs and all
    for (let j = 0; j < adj[node].length; j++) {
      const neighbourNode = adj[node][j];

      // both the neighbour and dequeued node are having same color, not a bipartite
      if (colors[neighbourNode] === colors[node]) {
        return false;
      }

      // neighbour node is not colored,so color and enqueue it in turn
      if (colors[neighbourNode] === -1) {
        colors[neighbourNode] = (colors[node] + 1) % 2; // 0 becomes 1 and 1 becomes 0
        queue.push(neighbourNode);
      }
    }
  }

  // queue becomes empty here, it is a bipartite graph surely
  return true;
}; enum COLORS = {
  COLORED_RED: 0,
  COLORED_GREEN: 1,
  NOT_COLORED: -1
}

const checkBipartiteBFS = function (
  startingNode: number,
  adj: number[][],
  colors: COLORS[]
): boolean {
  // define a queue and give starting node a color and enqueue it
  const queue: number[] = [];
  colors[startingNode] = 0;
  queue.push(startingNode);

  // run a loop until queue becomes empty
  while (queue.length !== 0) {
    // dequeues a node
    const node = queue.shift() as number;

    // look for its neighbour nodes and do those checking stuffs and all
    for (let j = 0; j < adj[node].length; j++) {
      const neighbourNode = adj[node][j];

      // both the neighbour and dequeued node are having same color, not a bipartite
      if (colors[neighbourNode] === colors[node]) {
        return false;
      }

      // neighbour node is not colored,so color and enqueue it in turn
      if (colors[neighbourNode] === -1) {
        colors[neighbourNode] = (colors[node] + 1) % 2; // 0 becomes 1 and 1 becomes 0
        queue.push(neighbourNode);
      }
    }
  }

  // queue becomes empty here, it is a bipartite graph surely
  return true;
}; A quick Primer on Recursion — A quick Primer on Recursion — Since DFS is recursive by nature, we don’t push a node into the queue every time we discover an un-colored node. Instead, we invoke the function again with the un-colored node. That’s it. That’s the only major difference to observe. We are repeating the same thing on each iteration if we look closely at BFS. So why not call the function itself from within itself, but with a different node, otherwise the pitfall of recursion pops up, business as usual (shoutout to Stack Overflow). With that in mind, let’s look at the steps of the DFS Algorithm for Bipartite: With that in mind, let’s look at the steps of the DFS Algorithm for Bipartite: entering the function with a node and a color, it starts by giving the node that color in the colors[] array


fires a loop to see all of its neighbors and look for the following:


If the neighbor node is not yet colored, it calls the DFS function again with the neighbor node and a color opposed to the dequeued node’s color. If the call comes back with a “false” value, then there is no need to iterate further; return “false” here as well. Because a rule broken by one node in the graph is enough to call it not a bipartite.


else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away with return “false”, but if it has the opposite color, then it continues.




Lastly, the queue becomes empty here; this node didn’t fall into the identical color consequences. So it returns “true” here, which simply means this node is not the one that breaks the bipartiteness and exits this execution to go back to where the function came from. entering the function with a node and a color, it starts by giving the node that color in the colors[] array entering the function with a node and a color, it starts by giving the node that color in the colors[] array entering the function with a node and a color, it starts by giving the node that color in the colors[] array fires a loop to see all of its neighbors and look for the following:


If the neighbor node is not yet colored, it calls the DFS function again with the neighbor node and a color opposed to the dequeued node’s color. If the call comes back with a “false” value, then there is no need to iterate further; return “false” here as well. Because a rule broken by one node in the graph is enough to call it not a bipartite.


else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away with return “false”, but if it has the opposite color, then it continues. fires a loop to see all of its neighbors and look for the following: fires a loop to see all of its neighbors and look for the following: If the neighbor node is not yet colored, it calls the DFS function again with the neighbor node and a color opposed to the dequeued node’s color. If the call comes back with a “false” value, then there is no need to iterate further; return “false” here as well. Because a rule broken by one node in the graph is enough to call it not a bipartite.


else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away with return “false”, but if it has the opposite color, then it continues. If the neighbor node is not yet colored, it calls the DFS function again with the neighbor node and a color opposed to the dequeued node’s color. If the call comes back with a “false” value, then there is no need to iterate further; return “false” here as well. Because a rule broken by one node in the graph is enough to call it not a bipartite. If the neighbor node is not yet colored, it calls the DFS function again with the neighbor node and a color opposed to the dequeued node’s color. If the call comes back with a “false” value, then there is no need to iterate further; return “false” here as well. Because a rule broken by one node in the graph is enough to call it not a bipartite. If the neighbor node is not yet colored, it calls the DFS function again with the neighbor node and a color opposed to the dequeued node’s color. If the call comes back with a “false” value, then there is no need to iterate further; return “false” here as well. Because a rule broken by one node in the graph is enough to call it not a bipartite. else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away with return “false”, but if it has the opposite color, then it continues. else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away with return “false”, but if it has the opposite color, then it continues. else if the neighbor is already colored and its color got blended in with the dequeued node, then it is not a bipartite graph; it then terminates the function straight away with return “false”, but if it has the opposite color, then it continues. Lastly, the queue becomes empty here; this node didn’t fall into the identical color consequences. So it returns “true” here, which simply means this node is not the one that breaks the bipartiteness and exits this execution to go back to where the function came from. Lastly, the queue becomes empty here; this node didn’t fall into the identical color consequences. So it returns “true” here, which simply means this node is not the one that breaks the bipartiteness and exits this execution to go back to where the function came from. Lastly, the queue becomes empty here; this node didn’t fall into the identical color consequences. So it returns “true” here, which simply means this node is not the one that breaks the bipartiteness and exits this execution to go back to where the function came from. Here’s the DFS implementation in TypeScript: Here’s the DFS implementation in TypeScript: Here’s the DFS implementation in TypeScript: enum COLORS = {
  COLORED_RED: 0,
  COLORED_GREEN: 1,
  NOT_COLORED: -1,
}

const checkBipartiteDFS = function (
  node: number,
  color: 0 | 1,
  colors: COLORS[],
  adjList: number[][]
) {
  // give that node a color
  colors[node] = color;

  // look for its neighbours and do the checking and call the function recursively if needed
  for (const neighbourNode of adjList[node]) {
    // both having the same color, return false right away
    if (colors[neighbourNode] === colors[node]) return false;

    // neighbour node is not yet been colored, so call the function again with the opposite color  
    if (colors[neighbourNode] === -1 && 
        !checkBipartiteDFS(neighbourNode, color === 0 ? 1 : 0, colors, adjList)
     ){      
          return false;    
     }  
   }
  
   // the iteration has been done and this node did not break the bipertiteness, so we return true  
   return true;
}; enum COLORS = {
  COLORED_RED: 0,
  COLORED_GREEN: 1,
  NOT_COLORED: -1,
}

const checkBipartiteDFS = function (
  node: number,
  color: 0 | 1,
  colors: COLORS[],
  adjList: number[][]
) {
  // give that node a color
  colors[node] = color;

  // look for its neighbours and do the checking and call the function recursively if needed
  for (const neighbourNode of adjList[node]) {
    // both having the same color, return false right away
    if (colors[neighbourNode] === colors[node]) return false;

    // neighbour node is not yet been colored, so call the function again with the opposite color  
    if (colors[neighbourNode] === -1 && 
        !checkBipartiteDFS(neighbourNode, color === 0 ? 1 : 0, colors, adjList)
     ){      
          return false;    
     }  
   }
  
   // the iteration has been done and this node did not break the bipertiteness, so we return true  
   return true;
}; There you have it. I hope it was helpful. Thanks so much for reading. You can connect with me on LinkedIn.  There, I share programming-related things just like this one as I learn them. connect with me on LinkedIn

How to Make Sense of the Bipartite Graph

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

How Browsers Turn Web Requests Into Pixels on Your Screen

The “Why” Behind React Suspense: Understanding the Original Vision

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

How Browsers Turn Web Requests Into Pixels on Your Screen

The “Why” Behind React Suspense: Understanding the Original Vision

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps