Checking Bipartite Property of a Graph

A bipartite graph is a graph where the vertices can be divided into two sets such that no two vertices in the same set are adjacent.

Steps to Check if a Graph is Bipartite

1. Define the Problem:

   • A graph G = (V, E) is bipartite if the nodes V can be split into two groups where every edge (u, v) in E connects nodes in different groups.

2. Choose a Method:

   • The problem can be solved using BFS or DFS by attempting to color the graph with two colors.

3. Algorithm Outline:

   • Start at any unvisited node and assign it one of the two colors (e.g., 0 or 1).
   • Traverse all its neighbors and assign them the opposite color.
   • If a neighbor is found with the same color as the current node, the graph is not bipartite.

Below is an implementation using Breadth-First Search (BFS):

function isBipartite(graph) {
    const color = new Array(graph.length).fill(-1); // Initialize colors as uncolored (-1)
    
    for (let i = 0; i < graph.length; i++) {
        if (color[i] === -1) {
            if (!bfsCheck(graph, i, color)) {
                return false;
            }
        }
    }
    return true;
}

function bfsCheck(graph, start, color) {
    const queue = [start];
    color[start] = 0; // Assign the first color
    
    while (queue.length) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
            if (color[neighbor] === -1) {
                color[neighbor] = 1 - color[node]; // Assign opposite color
                queue.push(neighbor);
            } else if (color[neighbor] === color[node]) {
                return false; // Found a conflict
            }
        }
    }
    return true;
}

// Example Usage
const graph = [
    [1, 3],    // Node 0 is connected to 1 and 3
    [0, 2],    // Node 1 is connected to 0 and 2
    [1, 3],    // Node 2 is connected to 1 and 3
    [0, 2]     // Node 3 is connected to 0 and 2
];

console.log(isBipartite(graph)); // Output: true