Obligatory Algorithm Comic

**Graph Algorithms – Breadth First Search**

The following GIF I got off of wikipedia will give you a general idea of how a Breadth-First Search works:

Also, take a look at this animation.

Here is the pseudocode for the Breadth-First Search (BFS) algorithm:

BFS(G, s)
for each vertex u ϵ G.V - {s}
u.color = WHITE
u.d = ∞
u.π = NIL
s.color = GRAY
s.d = 0
s.π = NIL
Q = Ø
ENQUEUE(Q, s)
while Q ≠ Ø
u = DEQUEUE(Q)
for each v ϵ G.Adj[u]
if v.color == WHITE
v.color = GRAY
v.d = u.d + 1
v.π = u
ENQUEUE(Q, v)
u.color = BLACK

**Notation**

- – the graph
- – the root of the graph
- – predecessor (or parent) of vertex .
- – distance between the vertex and the root .
- – the color of the vertex . It is white if is undiscovered, gray if it is discovered. A vertex is black if all vertices adjacent to it have also been discovered.
- a queue that contains all the gray vertices.

A breadth-first search can correctly calculate the shortest path between two given vertices in a graph (assuming a path exists). We will prove this in the next chapter when we analyse the Breadth-First Search algorithm.

### Like this:

Like Loading...

*Related*