# Review 4: Paths in graphs

*printable version*

### Problem R4.1

Recall the breadth-first search algorithm.

**def** `bfs`(`vertices`, `source`):

**for** `v` **in** `vertices`: `v`.`dist` = `INFINITY`

` source`.`dist` = `0`

`q` = `new queue`()

`q`.`add`(`source`)

**while not** `q`.`isEmpty`():

`u` = `q`.`remove`()

**for** `v` **in** `u`.`neighbors`:

**if** `v`.`dist` == `INFINITY`:

`v`.`dist` = `u`.`dist` + `1`

`q`.`add`(`v`)

A graph is said to be **bipartite** if the
vertices can be divided into two groups, and every edge connects
one group to another. Assuming we're given a graph where all
vertices are reachable from each other, how can we modify our breath-first
search code in order to determine whether our graph is
bipartite?

The crucial change in the below implementation is the
addition of the

and of the two **elif**

lines. (Other changes are to the function parameters and
the addition of the assignment to **return**

.)`source`

**def** `is_bipartite`(`vertices`):

`source` = `vertices`[`0`]

**for** `v` **in** `vertices`: `v`.`dist` = `INFINITY`

` source`.`dist` = `0`

`q` = `new queue`()

`q`.`add`(`source`)

**while not** `q`.`isEmpty`():

`u` = `q`.`remove`()

**for** `v` **in** `u`.`neighbors`:

**if** `v`.`dist` == `INFINITY`:

`v`.`dist` = `u`.`dist` + `1`

`q`.`add`(`v`)

**elif** `v`.`dist` % `2` == `u`.`dist` % `2`:

**return False**

** return True**</`b`>

(Actually, the

condition can be just
“**elif**

”, since when BFS
discovers a previously-discovered vertex, the vertex's distance
will either be at the same distance from the source, or it will
be one link farther from the source.)`v`.`dist` == `u`.`dist`