Breadth-First Search

jdanray

Now that I’ve written about queues, I’ll write about breadth-first search.

Breadth-first search is a graph search algorithm. In a breadth-first search, we explore all of a vertex’s adjacent vertices before proceeding to the adjacent vertices’ adjacent vertices. Here is an outline of the algorithm:

(1) Enqueue and mark the source vertex.

(2) Dequeue a vertex. If the vertex is a match, then return the vertex. If the vertex is not a match, then enqueue and mark all of its unmarked adjacent vertices.

(3) If the queue is empty, then return nil. If the queue is not empty, then go to (2).

Breadth-first search uses a mix of two data structures: a queue and an array.

Unlike arrays, graphs are not linear. Whereas an element of an array can have only one succeeding element, a vertex in a graph can have many adjacent vertices. Consequently, we store vertices…

View original post 170 mots de plus

Publicités

Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s