What does breadth-first search (BFS) do?

Breadth-First Search (BFS) is an algorithm that gradually explores a graph "layer by layer", starting from a given vertex and moving first to all its neighbors, then to the neighbors of those neighbors, and so on.

---

#Idea

BFS looks for all vertices at the minimum distance from the starting one before moving further. It uses a queue (FIFO) to process vertices in the order they were discovered.

---

#Step by step

1. Put the starting vertex in the queue and mark it as visited.
2. While the queue is not empty:

• Remove a vertex from the queue.
• Add all its unvisited neighbors to the queue and mark them.

3. Repeat until all reachable vertices have been visited.

---

#Example

For the graph:

If you start from A, the traversal order is: A → B → D → C → E

---

#Applications

• Finding the shortest path in unweighted graphs.
• Checking a graph's connectivity.
• Determining the levels (depth) of vertices.
• Finding "wave-like" connections, for example, in signal-propagation problems.

---

Summary: BFS is a level-by-level graph traversal using a queue, which finds all vertices in order of their "closeness" to the starting one.