Start from some vertex $v$ and perform a breadth-first search. If there are any non-tree edges joining vertices on the same level, then the graph is not bipartite (for we would have just found an odd-length cycle). If, after performing this test, there is an unvisited vertex, $w$, we repeat this algorithm with $w$. We continue this process until we have determined that the graph is not bipartite or we have visited all its vertices. If we have visited all its vertices and found no odd-length cycles, then the graph is bipartite. The running time is $O(n+m)$, since we are performing a BFS on each connected component.