Provide an implementation of the BFS algorithm that uses a FIFO queue, rather than a level-by-level formulation, to manage vertices that have been discovered until the time when their neighbors are...

Provide an implementation of the BFS algorithm that uses a FIFO queue,

rather than a level-by-level formulation, to manage vertices that have been

discovered until the time when their neighbors are considered.

A graph
G
is

bipartite

if its vertices can be partitioned into two sets
X
and

Y
such that every edge in
G
has one end vertex in
X
and the other in
Y.

Design and analyze an efficient algorithm for determining if an undirected

graph
G
is bipartite (without knowing the sets
X
and
Y
in advance).