Bipartite Graph - BFS

A graph is said to be bipartite if it can be colored using two colors such that no two adjacent nodes have same color.

Graph should be undirected.

Practice Link

Sample 1#

output: BIPARTITE

Sample 2#

output: NOT BIPARTITE

Observations#

• Any linear graph with no cycle - always bipartite
• With Cycle
  1. Even Cycle Length - Bipartite
  2. odd cycle length - can NEVER be bipartite

Note#

Carefully handle the disconnected components.

BFS#

BFS is well-suited for 2-coloring because it naturally processes nodes level by level — all nodes at even distance from the source get one color and all nodes at odd distance get the other. We attempt to color the graph greedily: assign color 0 to the source, then alternately assign the opposite color to each neighbor discovered during BFS. If we ever try to assign a color to a node that already has the same color as its neighbor, the graph is not bipartite.

Use a colors array to maintain the color of each node (also acts as the visited tracker, initialized to -1 for unvisited).

Two cases possible:

1. color[adj_node] == -1 → not yet visited; assign the opposite color of the current node and enqueue it.
2. color[adj_node] == color[current_node] → same color conflict → not bipartite; return false immediately.

Implementation#

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int V  = graph.size();
        vector<int> colors(V, -1);
        queue<int> q;

        for(int i=0;i<V;i++)
        {
            if(colors[i]==-1)
            {
                q.push(i);
                colors[i]=0;

                while(!q.empty())
                {
                    int node = q.front();
                    q.pop();

                    for(auto next: graph[node])
                    {
                        if(colors[next]==-1)
                        {
                            colors[next]=1-colors[node];
                            q.push(next);
                        }

                        else if(colors[next]==colors[node])
                            return false;
                    }
                }

            }

        }
        return true;
    }
};

Complexities#

Time Complexity: O(N*(V+E)) -> to cover all disconnected components