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.

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

• In case some readers are not familiar with the meaning of the English word (outside of its usage as part of this technical term): merriam-webster.com/dictionary/breadth or dictionary.cambridge.org/dictionary/english/breadth . It's similar to "width", a different dimension than "depth" if you're talking about the size/shape of a physical object. And in the metaphorical sense like depth of knowledge (expert on one subject) vs. breadth of knowledge (lots of subjects). – Peter Cordes Apr 19 at 14:36

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

• I think the word frontier might refer to the edge of the discovered nodes. When you've only discovered a, the frontier is a. When you've discovered a, b, c, the frontier is b, c. When you've discovered a, b, c, d, e, f, g, the frontier is d, e, f, g. In other words, the nodes that have been discovered and that we haven't searched beyond yet. – Theodoros Chatzigiannakis Apr 20 at 6:32
• I think this is a fair point, but I think that “frontier” can be interpreted multiple ways, with the general explanation above still working. – Bryce Kille Apr 20 at 6:42

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.