Bipartite Graph Check

    DSA · Intermediate

    Definition

    A graph is bipartite if nodes can be colored with two colors so no edge joins same colors.

    Used in matching problems and 'possible bipartition'.

    Diagram

    0(red) – 1(blue)1(blue) – 2(red)

    Flowchart

    Color start 0BFS neighbors with opposite colorSame color neighbor → not bipartite

    Example: BFS coloring

    from collections import deque
g = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}
c = {0: 0}; q = deque([0]); ok = True
while q:
    u = q.popleft()
    for v in g[u]:
        if v not in c: c[v] = 1 - c[u]; q.append(v)
        elif c[v] == c[u]: ok = False
print(ok)

    Output: True

    Complexity

    O(V + E)

    Key points

    • Odd cycle → not bipartite
    • Run from every uncolored node

    Interview questions

    Is a triangle bipartite?

    No, it has an odd cycle.

    More DSA topics

    ArraysLinked ListStackQueue