Check if a Graph is Bipartite Using DFS - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an undirected graph represented as an adjacency list with V vertices (0-indexed), determine if the graph is bipartite.

A graph is bipartite if we can split the set of vertices into two groups such that no two adjacent vertices belong to the same group. This is equivalent to checking if the graph can be coloured using two colours without any two adjacent nodes having the same colour.

Examples❯

Adjacency List Is Bipartite? Description
{ 0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2] }
Yes
Even cycle, can be coloured using two colours
{ 0: [1, 2], 1: [0, 2], 2: [0, 1] }
No
Triangle, odd cycle cannot be bipartite
{}
Yes Empty graph is trivially bipartite
{ 0: [] }
Yes
Single isolated node
{ 0: [1], 1: [0], 2: [3], 3: [2] }
Yes
Two separate components, both bipartite

Solution❯

Understanding the Problem

A graph is said to be bipartite if its set of vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set. In simpler words, no two adjacent vertices should belong to the same group.

This concept often comes up in real-world scenarios like assigning tasks to two teams such that no conflicting tasks are handled by the same team.

We are given a graph and we have to check if it is bipartite or not. We’ll solve it using Depth-First Search (DFS), by trying to color the graph using two colors and checking for any coloring conflicts.

Step-by-Step Solution with Example

Step 1: Understand the Input Format

The graph is typically represented as an adjacency list. Each key in the list is a node, and its value is an array of nodes it is directly connected to. Example:

{
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
}

This graph has 4 nodes (0 to 3) and edges between them. We will now try to determine if this graph can be divided into two groups as per bipartite rules.

Step 2: Initialize Color Map

We will use a map or array to keep track of the color assigned to each node. Let’s say color 0 for one group, and 1 for the other.

Initially, no node is colored.

Step 3: DFS Traversal with Coloring

We start DFS traversal from any unvisited node (say node 0), assign it color 0, and then try to assign its neighbors the opposite color (1).

If at any point, a neighbor already has the same color as the current node, we conclude the graph is not bipartite.

Step 4: Continue for All Components

Since the graph may be disconnected, we need to repeat the DFS traversal from every unvisited node to ensure all components are checked.

Step 5: Example Walkthrough

Let’s walk through the example:

{
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
}

Start from node 0 → color it 0

→ visit node 1 → color it 1

→ visit node 2 from node 1 → color it 0

→ visit node 3 from node 2 → color it 1

→ back to node 0, already colored 0 → no conflict

→ visit node 2 from node 3 → already colored 0 → no conflict

All nodes visited without conflict. So this graph is bipartite.

Edge Cases

Case 1: Disconnected Graph

Always check all nodes, not just the first component. Use a loop to start DFS from each unvisited node.

Case 2: Odd-Length Cycle

If the graph contains an odd-length cycle, it cannot be bipartite. For example:

{
  0: [1, 2],
  1: [0, 2],
  2: [0, 1]
}

This is a triangle (3-cycle). You cannot color it with two colors without conflict. Hence, not bipartite.

Case 3: Empty Graph

A graph with no edges is trivially bipartite since no adjacent nodes exist to cause conflicts.

Case 4: Self-Loop

If a node has an edge to itself, the graph is automatically not bipartite, since a node would need to have two different colors.

Finally

Checking whether a graph is bipartite using DFS is a classic and intuitive algorithm. By coloring nodes alternately and validating the coloring rules, we can confidently determine the bipartiteness of a graph.

Always remember to handle disconnected components and edge cases like odd cycles and self-loops to ensure your solution is robust.

Algorithm Steps❯

  1. Create a color array of size V initialized with -1 (unvisited).
  2. Define a recursive dfs function that takes current node and currentColor.
  3. Color the node and for each of its neighbors:
    1. If neighbor is not coloured, call dfs with opposite colour.
    2. If already coloured and same as current node, return false.
  4. If DFS completes without conflicts, return true.
  5. Check each unvisited node to ensure disconnected components are handled.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX 100

bool dfs(int node, int c, int color[], int adj[][MAX], int V) {
    color[node] = c;
    for (int i = 0; i < V; i++) {
        if (adj[node][i]) {
            if (color[i] == -1) {
                if (!dfs(i, 1 - c, color, adj, V)) return false;
            } else if (color[i] == color[node]) {
                return false;
            }
        }
    }
    return true;
}

bool isBipartite(int adj[][MAX], int V) {
    int color[MAX];
    memset(color, -1, sizeof(color));
    for (int i = 0; i < V; i++) {
        if (color[i] == -1 && !dfs(i, 0, color, adj, V)) {
            return false;
        }
    }
    return true;
}

int main() {
    int V = 4;
    int adj[MAX][MAX] = {0};
    adj[0][1] = adj[1][0] = 1;
    adj[0][3] = adj[3][0] = 1;
    adj[1][2] = adj[2][1] = 1;
    adj[2][3] = adj[3][2] = 1;

    if (isBipartite(adj, V))
        printf("Graph is bipartite\n");
    else
        printf("Graph is not bipartite\n");

    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(V + E)Even in the best case, we must traverse all vertices and their edges to ensure bipartite coloring without assumptions.
Average CaseO(V + E)Each vertex and edge is visited once during the DFS traversal.
Worst CaseO(V + E)In the worst case, the graph is fully connected and requires full traversal of all vertices and edges.

Space Complexity❯

O(V)

Explanation: We use a color array of size V and recursive call stack of maximum depth V in the worst case.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...