Bipartite Graph Algorithm Tutorial

Bipartite Graph Check

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects vertices in different sets. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles.

You use BFS or DFS to try coloring vertices with $2$ colors. If you can color all vertices so that no adjacent vertices share a color, the graph is bipartite.

function isBipartite(graph, n):
    color = array of size n, initialized to -1

    for start from 0 to n - 1:
        if color[start] == -1:
            queue = empty queue
            queue.enqueue(start)
            color[start] = 0

            while queue is not empty:
                u = queue.dequeue()
                for each neighbor v of u:
                    if color[v] == -1:
                        color[v] = 1 - color[u]
                        queue.enqueue(v)
                    else if color[v] == color[u]:
                        return false

    return true

Starting new BFS: You start a new BFS from each unvisited vertex to handle disconnected graphs.

Two-coloring: The alternating colors (0 and 1) ensure adjacent vertices have different colors. Finding same-colored neighbors proves a conflict.

Applications: You use bipartite checks for matching problems, scheduling, graph coloring, and detecting conflicts in assignment problems.

Time complexity: $O(V + E)$ because you visit each vertex and edge once.

Space complexity: $O(V)$ for the color array and queue.