Data Structures, Algorithms, & Applications in Java
Chapter 17, Exercise 51

We may perform a breadth-first or depth-first search in each component of the graph. In each component, the first vertex that is visited may be assigned to either set. The assignment of the remaining vertices in the component is forced by the bipartite labeling requirement that the end points of an edge have different labels. The code below assigns the first vertex in each component the label 1. It is a modified version of the code for breadth first search. 
/** Label the vertices such that every edge connects
  * a vertex with label 1 to one with label 2
  * @return null iff there is no such labeling
  * @return an array of labels when the graph has such a labeling */
public int [] bipartite()
{
   // make sure this is an undirected graph
   verifyUndirected("bipartite");

   int n = vertices();

   // create label array, default initial values are 0
   int [] label = new int [n + 1];

   // do a breadth first search in each component
   ArrayQueue q = new ArrayQueue(10);
   for (int v = 1; v <= n; v++)
      if (label[v] == 0)
      {// new component, label the vertices in this component
         label[v] = 1;
         q.put(new Integer(v));
         while (!q.isEmpty())
         {    
            // remove a labeled vertex from the queue
            int w = ((Integer) q.remove()).intValue();
   
            // mark all unreached vertices adjacent from w
            Iterator iw = iterator(w);
            while (iw.hasNext())
            {// visit an adjacent vertex of w
               int u = ((EdgeNode) iw.next()).vertex; 
               if (label[u] == 0)
               {// u is an unreached vertex
                  q.put(new Integer(u));
                  label[u] = 3 - label[w]; // assign u the other label
               }
               else
                  // u already labeled
                  if (label[u] == label[w])
                     // both ends of edge assigned same label
                     return null;
            }
         }     
      }   

   // labeling successful
   return label;
}


When the graph is bipartite, each vertex of the graph is added to the queue exactly once. Each vertex is also deleted from the queue exactly once. When a vertex is deleted from the queue, all vertices adjacent to it are examined. It takes Theta(n) time to find and examine the vertices adjacent to vertex w when an adjacency matrix is used and Theta(dw) when adjacency lists are used. If the algorithm does not terminate early because of an exception or because the graph is not bipartite, all vertices in the graph get examined. The total examination time is Theta(n2) when adjacency matrices are used and Theta(e) when adjacency lists are used. The remainder of the algorithm takes O(n) time. Allowing for exceptions and the fact that the algorithm may terminate early because the graph is not bipartite, we see that the overall complexity is O(n2) when adjacency matrices are used and O(n+e) when adjacency lists are used.

A test program, input, and output appear in the files TestBipartite.*.