Learn
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 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: because you visit each vertex and edge once.