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:

animated_bfs

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

  • 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s