What is the meaning of 'breadth' in breadth first search?

Question

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this:

Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.

However, I'm not able to understand the meaning of this statement. I'm confused about this word "frontier" and breadth of that frontier.

So, can someone please answer this question in a way which is easy to understand for a beginner like me?

Answer 1

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the deepest part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here

Answer 2

The quote you gives says "the frontier between discovered and undiscovered vertices". So that's the frontier the author is talking about: the frontier between discovered and undiscovered vertices. You have some vertices that you haven't seen anything at all yet. You also have some vertices for which you've seen everything for. And then you have vertices in between. These are vertices that you've looked at, but you haven't loaded all of their children yet. This is the frontier.

The discusses this further on:

To keep track of progress BFS colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. The vertex is discovered the first time it is encountered during the search, at which time it becomes non-white. Gray and black vertices, therefore, have been discovered, but BFS distinguishes between them to ensure that the search proceeds in a BF manner.
...
each vertex is initially white, is grayed when it is discovered in the search, and is blacked when it is finished, that is, when its adjacency list has been examined completely.

So all vertices start out white (undiscovered). When a node is discovered, it's colored gray (frontier). When everything it points to has been discovered, it's colored black (completely discovered). The frontier is the set of points that have been discovered, but have undiscovered children.

Suppose you are looking for something on website. You first go to the main page. Suppose that's labelled "animals". The frontier is currently {"animals"}. You look through the main page and don't see what you are looking for. But you notice that it has links to two more pages, "quadrupeds" and "worms". So you click on the link to "quadrupeds". Now the frontier is {"animals","quadrupeds"}. You look through "quadrupeds" and don't find what you're look for. What do you do next? You can either look for links on "quadrupeds" and follow those, or go back to "animals" and click on the link to "worms". The first is a depth-first search, and the second is a breadth-first search.

"depth" refers to how many links from the root node it takes to get to a node, while "breadth" refers to nodes as the same depth. In the example above, BFS starts at "animals" and first looks at all the nodes of depth one, so it looks at "quadrupeds" and "worms" first. After it has looked at all the depth-1 nodes, its expands the frontier across all of those nodes; that is, it looks at the children of all of the depth-1 nodes before looking at any of the children of depth-2 nodes. So, for instance, if one of the links on the "quadrupeds" page is "primates", it will look at all of the links on the "worms" page before it looks at any of the links on the "primates" page.

Answer 3

Suppose the BFS algorithm is executed starting from vertex $a$. Imagine a wave that is sent out from $a$ (like a water-wave or tsunami). After one time step, the wave would have reached all the neighbors of $a$. After two time steps, the wave would have reached (or "visited") all the vertices which are at distance at most $2$ from $a$. And so on.

At any given time, the frontier of the wave is exactly the vertices that are stored in the queue data structure (these vertices have been visited but not yet explored further).

Thus, the wave initially reaches the entire "breadth" of all vertices which are at distance 1 from $a$. After some time steps, the wave would have covered the entire breadth up to some distance from the starting point $a$.

The set of vertices at distance $k$ from $a$ is called the $k$th layer in the distance partition of the graph with respect to vertex $a$. The vertex set is the disjoint union of these layers $(k \ge 0)$. The $0$th layer is $\{a\}$, the first layer is the set of neighbors of $a$, the second layer is the set of vertices whose distance to $a$ is two, and so on. The BFS algorithm visits the vertices of the graph in a particular order - layer by layer. Each layer covers the entire breadth, but the different layers are at different depth.

On the other hand, the DFS algorithm would explore as deep as possible in one direction (i.e. visit $a$'s first neighbor, then its neighbor, then its neighbor, and so on) before returning back to $a$ and visiting the next unexplored neighbor of $a$. This algorithm goes deep first, instead of visiting neighbors breadth-wise.

Thus, DFS and BFS differ in the order in which they visit the vertices.