Testing Bipartiteness

Testing Bipartiteness.py

Assume graph G is connected. Otherwise, we can run the algorithm for each connected component of G.
Let q be an empty queue

Pick any vertex s ∈ V and color it Red
q.enqueue(s)

while !q.empty()
  u = q.dequeue()
  foreach v in u.adjList:
    if v.color is nil:
      v.color = (u.color == Red) ? Black : Red
      q.enqueue(v)
    elif v.color == u.color:
      return "Not Bipartite"
return "Bipartite"