# Algorithms Notes – Chapter 5

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)
if v.color == WHITE
v.color = GRAY
v.d = u.d + 1
v.π = u
ENQUEUE(Q, v)
u.color = BLACK


Notation

• $G$ – the graph
• $s$ – the root of the graph
• $v.\pi$ – predecessor (or parent) of vertex $v$.
• $v.d$ – distance between the vertex $v$ and the root $s$.
• $v.color$ – the color of the vertex $v$. It is white if $v$ is undiscovered, gray if it is discovered. A vertex is black if all vertices adjacent to it have also been discovered.
• $Q$ 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.