Check if a graph is Bipartite or not.

Problem: A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V.

Given an undirected graph with no self edges, Check if the graph is bipartite or not. Please note that the graph may not be connected that mean there may be two nodes in the graph say u and v such that there is not path between them.

Example:

Input: graph = [[1,3],[0,2],[1,3],[0,2]] (Above image)
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Approach: For simplicity lets take the graph as a 2D array (like in the example). Where nodes are numbered from 0, 1, 2, ..., n-1 and graph[i] will be the list of connected nodes to i.

To solve this problem we can use graph coloring here. Say we want to color all the nodes using two colors Red and Blue. We just need to color all the neighbors of a node to the color other than the node. Say if a node is colored red then color all it's neighbors to blue. If we are able to color the whole graph in this way  successfully then we can say that this graph is bipartite.

We can use BFS or DFS to do it. However I am using BFS in my implementation.

Implementation in C#:

    public bool IsBipartite(int[][] graph) 

    {

        int[] color = new int[graph.Length];     

        for (int i = 0; i < graph.Length; ++i)

        {

            if (color[i] == 0)

            {

                if (!this.IsColoringPossible(i, graph, color))

                {

                    return false;

                }

            }

        }

        return true;

    }

    

    private bool IsColoringPossible(int startNode, int[][] graph, int[] color)

    {

        Queue<int> queue = new Queue<int>();

        queue.Enqueue(startNode);

        color[startNode] = 1;

        while (queue.Count != 0)

        {

            int currentNode = queue.Dequeue();

            foreach (int connectedNode in graph[currentNode])

            {

                if (color[connectedNode] == 0)

                {

                    color[connectedNode] = -color[currentNode];

                    queue.Enqueue(connectedNode);

                }

                else if (color[connectedNode] == color[currentNode])

                {

                    return false;

                }

            }

        }

        return true;

    }

Complexity: O(n)