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