> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/chapter1/bipartite-graph/check-bipartite-graph.md).

# Check Bipartite Graph

## Check Bipartite Graph

## 1. Idea

1. Assign RED color to the source vertex (putting into set U).
2. Color all the neighbors with BLUE color (putting into set V).
3. Color all neighbor’s neighbor with RED color (putting into set U).
4. This way, assign color to all vertices such that it satisfies all the constraints of m way coloring problem where m = 2.
5. While assigning colors, if we find a neighbor which is colored with same color as current vertex, then the graph cannot be colored with 2 vertices (or graph is not Bipartite)

## 2. Implementation

```java
public static boolean isBipartieGraph(int[][] graph, int start) {
        int n = graph.length;

        int[] colors = new int[n];
        Arrays.fill(colors, -1);

        colors[start] = 1;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int curVertex = queue.remove();

            for (int nextVertex = 0; nextVertex < n; nextVertex++) {
                if (graph[curVertex][nextVertex] == 1 && colors[nextVertex] == -1) {
                    colors[nextVertex] = 1 - colors[curVertex];
                    queue.add(nextVertex);
                }
                else if (graph[curVertex][nextVertex] == 1 && colors[curVertex] == colors[nextVertex]) {
                    return false;
                }
            }
        }
        return true;
    }
```

## 3. Time & Space Complexity

Time: O(V^2) for adjacent matrix and O(V + E) for adjacent list

Space: O(V^2) for adjacent matrix and O(V + E) for adjacent list