Mrthdrb

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?

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

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.