Bipartite - BFS and DFS

Link : is graph Bipartite?

Definition

A graph is bipartite if you can split its set of vertices into two disjoint sets such that:

• Every edge connects a node from one set to the other (i.e., no two adjacent nodes belong to the same set).

Formally, a graph G(V, E) is bipartite if its vertices can be colored with 2 colors such that no two adjacent vertices share the same color.

Intuition

Imagine you're trying to seat people at two tables (Set A and Set B) such that no pair of friends sits at the same table.
If this is possible for all people (nodes), the graph is bipartite.

This is essentially a graph coloring problem:

• Use 2 colors (say 0 and 1)

• Assign a color to a node

• Ensure all its adjacent nodes have the opposite color

• If a conflict arises, the graph is not bipartite

Applications

• Matching problems (e.g., job allocation, dating sites)

• Scheduling where certain tasks can't be adjacent

• Detecting odd-length cycles:
  A graph is bipartite if and only if it does not contain any odd-length cycle

Approach #1: BFS (Breadth-First Search)

Idea

• Color the starting node with 0

• Traverse using BFS

• Color all adjacent nodes with the opposite color (1)

• If any neighbor already has the same color, return false

Java Code: Bipartite Check using BFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1); // -1 = unvisited

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!bfsCheck(i, graph, color)) return false;
            }
        }
        return true;
    }

    private boolean bfsCheck(int node, int[][] graph, int[] color) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(node);
        color[node] = 0;

        while (!q.isEmpty()) {
            int curr = q.poll();
            for (int neighbor : graph[curr]) {
                if (color[neighbor] == -1) {
                    color[neighbor] = 1 - color[curr];
                    q.offer(neighbor);
                } else if (color[neighbor] == color[curr]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Dry Run

Graph (adjacency list):

0 → 1, 3  
1 → 0, 2  
2 → 1, 3  
3 → 0, 2

BFS from node 0:

• color[0] = 0

• visit 1 → color[1] = 1

• visit 3 → color[3] = 1

• visit 2 → color[2] = 0

All neighbors colored correctly → Bipartite: True

Time Complexity

• O(V + E) — where V = vertices, E = edges

Space Complexity

• O(V) for color array and queue

Approach #2: DFS (Depth-First Search)

Idea

• Assign color 0 to a node

• Recursively call DFS on its neighbors with color 1

• If conflict arises (neighbor has the same color), return false

Java Code: Bipartite Check using DFS

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1); // uncolored

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfsCheck(i, 0, color, graph)) return false;
            }
        }
        return true;
    }

    private boolean dfsCheck(int node, int col, int[] color, int[][] graph) {
        color[node] = col;
        for (int neighbor : graph[node]) {
            if (color[neighbor] == -1) {
                if (!dfsCheck(neighbor, 1 - col, color, graph)) return false;
            } else if (color[neighbor] == col) {
                return false;
            }
        }
        return true;
    }
}

Dry Run

Graph:

0 → 1, 3  
1 → 0, 2  
2 → 1, 3  
3 → 0, 2

DFS:

• 0 colored 0
  → 1 → color 1
  → 2 → color 0
  → 3 → color 1

No color conflict → Bipartite: True

Time Complexity

• O(V + E) — recursive traversal

Space Complexity

• O(V) for color array

• O(V) recursion stack in worst case

How to Convert From Edge List to Adjacency List

If input is like:

int[][] edges = {
  {0, 1},
  {1, 2},
  {2, 3},
  {3, 0}
};

Convert to adjacency list:

List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
    adj.get(edge[0]).add(edge[1]);
    adj.get(edge[1]).add(edge[0]); // undirected
}

Detecting Non-Bipartite Graph

A graph is not bipartite if:

• It contains a cycle of odd length

Example:

0 — 1
 \  |
   2

Cycle: 0 → 1 → 2 → 0 (length 3) ⇒ odd ⇒ Not Bipartite

Final Notes