Making Sense of Bipartite Graphs

Source: Dev.to

Introduction

Developing strength in graph algorithms sharpens your programming craft and has a ripple effect across many data structures such as queues, stacks, and priority queues. In this article we’ll briefly explore the concept of bipartite graphs and provide gentle implementations using both BFS and DFS in TypeScript.

What Is a Bipartite Graph?

A graph is bipartite if its vertices can be colored using two distinct colors such that no edge connects two vertices of the same color. In other words, the graph’s vertices can be split into two disjoint sets where every edge runs between the sets.

Checking Bipartiteness with BFS

Breadth‑First Search (BFS) explores a graph level by level. For bipartite checking the algorithm:

1. Enqueue the starting node and assign it a color (e.g., 0).
2. While the queue is not empty, dequeue a node.
3. For each neighbor:
   • If the neighbor already has the same color, the graph is not bipartite.
   • If the neighbor is uncolored, assign it the opposite color and enqueue it.
4. If the queue empties without conflicts, the graph is bipartite.

BFS Implementation (TypeScript)

enum COLORS {
  COLORED_RED = 0,
  COLORED_GREEN = 1,
  NOT_COLORED = -1,
}

/**
 * Checks whether a graph is bipartite using BFS.
 *
 * @param startingNode - Index of the node to start the BFS from.
 * @param adj          - Adjacency list where adj[i] is an array of neighbors of node i.
 * @param colors       - Array storing the color of each node (initialized with NOT_COLORED).
 * @returns true if the graph is bipartite, false otherwise.
 */
const checkBipartiteBFS = (
  startingNode: number,
  adj: number[][],
  colors: COLORS[]
): boolean => {
  const queue: number[] = [];

  // Color the starting node and enqueue it
  colors[startingNode] = COLORS.COLORED_RED;
  queue.push(startingNode);

  while (queue.length !== 0) {
    const node = queue.shift() as number;

    for (const neighbourNode of adj[node]) {
      // Same color on both ends → not bipartite
      if (colors[neighbourNode] === colors[node]) {
        return false;
      }

      // Uncolored neighbor → assign opposite color and enqueue
      if (colors[neighbourNode] === COLORS.NOT_COLORED) {
        colors[neighbourNode] = (colors[node] + 1) % 2; // toggle between 0 and 1
        queue.push(neighbourNode);
      }
    }
  }

  // No conflicts found
  return true;
};

Checking Bipartiteness with DFS

Depth‑First Search (DFS) explores as deep as possible along each branch before backtracking. The recursive nature of DFS makes the bipartite check straightforward:

1. Assign a color to the current node.
2. Recursively visit each neighbor:
   • If a neighbor already has the same color, the graph is not bipartite.
   • If a neighbor is uncolored, recurse with the opposite color.
3. If all recursive calls succeed, the graph is bipartite.

DFS Implementation (TypeScript)

/**
 * Recursively checks bipartiteness using DFS.
 *
 * @param node   - Current node index.
 * @param color  - Color to assign to the current node (0 or 1).
 * @param colors - Array storing colors of nodes (initialized with NOT_COLORED).
 * @param adj    - Adjacency list.
 * @returns true if the subgraph rooted at `node` is bipartite, false otherwise.
 */
const checkBipartiteDFS = (
  node: number,
  color: 0 | 1,
  colors: COLORS[],
  adj: number[][]
): boolean => {
  colors[node] = color;

  for (const neighbourNode of adj[node]) {
    // Conflict: same color on both ends
    if (colors[neighbourNode] === colors[node]) return false;

    // Uncolored neighbor → recurse with opposite color
    if (
      colors[neighbourNode] === COLORS.NOT_COLORED &&
      !checkBipartiteDFS(
        neighbourNode,
        color === 0 ? 1 : 0,
        colors,
        adj
      )
    ) {
      return false;
    }
  }

  // No conflicts in this branch
  return true;
};

Conclusion

Both BFS and DFS provide efficient ways to verify whether a graph is bipartite. BFS uses an explicit queue and iteratively colors nodes, while DFS leverages recursion to achieve the same goal. Choose the approach that best fits the surrounding codebase or personal preference.

Happy coding!