Search algorithm by width

What is a search algorithm in width?

The breadth search algorithm (Breadth First Search - BFS for short) walks through a wide graph and uses a queue to memorize adjacent vertices to start the search when no peak is found. adjacent in any loop.

Search algorithm by width Picture 1

As shown in the example above, the search algorithm broadcasts from A to B to E to F then to C , to G and finally to D. This algorithm follows the rule:

Rule 1 : Browse to the adjacent vertices without approval. Mark the vertex that has been approved. Show that peak and push into a queue (queue) .

Rule 2 : If no adjacent vertices are found, then delete the first vertex in the queue.

Rule 3 : Repeat Rule 1 and 2 until the queue is empty.

The following table illustrates how search-width algorithms work with a simple example:

Queue initialization (queue)

Search algorithm by width Picture 2

We start browsing vertex S (start vertex) and mark this vertex as approved.

Search algorithm by width Picture 3

Then we find the vertex adjacent to S that has not been approved. In this example we have 3 vertices, and in alphabetical order we select vertex A marked as approved and put A in the queue.

Search algorithm by width Picture 4

Continue to browse vertices adjacent to S as B. Mark as approved and place this vertex in the queue.

Search algorithm by width Picture 5

Continue to browse vertices adjacent to S as C. Mark as approved and place this vertex in the queue.

Search algorithm by width Picture 6

Now vertex S has no adjacent vertices that have not been approved yet. Now we draw A from the queue.

Search algorithm by width Picture 7

From vertex A we have an adjacent vertex of D and an unopened vertex. Marking vertex D is already browsing and queuing.

Search algorithm by width Picture 8

At this point, we see that no vertices are unmarked (not yet approved with the example in this table). But the algorithm continues, we continue to extract vertices from the queue in order to find all vertices that have not been approved. When the queue is empty, it is the end of the algorithm.

According to Tutorialspoint

Previous lesson: Deep search algorithm

Next lesson: Tree data structure