# Breadth-First Search (BFS)

The opposite of Depth-First Search would be *breadth-first* search (*BFS*).

A *breadth-first* search algorithm will follow multiple directions at the same time, taking one step in each possible direction before taking the second step in each direction.

In this case, the frontier is managed as a Queue data structure.

- Pros
- This algorithm is guaranteed to find the optimal solution

- Cons
- almost guaranteed to take longer than the minimal time to run
- At worst, this algorithm takes the longest possible time to run

You can use BFS to solve shortest-path problems is it is an unweighted graph (edge weights = constant). If they are weighted, you need something like Dijkstra Algorithm.

### Implementation

### Clearing up confusion in implementation with DFS

Hmm the stuff I say below is kind of confusing, just my thoughts.

Confusion

Sometimes, when I am rusty, I forget whether I should put the

`visited[u]`

inside or outside the for loop. This is pretty important to get right.

Difference with DFS

- In DFS, we visit a node and process it at the
same time(within the same function call)- In BFS, we visit a node, add it to the queue, and then process it at a
later time(when we pop the node from the Queue)

- Mark neighbouring nodes as visited, add them to the queue, and process them as we pop the queue.

If this isn’t clear to you, just try it on the following graph:

Drawing-2023-05-18

BFS on trees: There are certain times when I need to keep track of the depth. For these distances, just look at your distance implementation, and do it for the tree. The distance will be equivalent to the “depth of a tree”.

- Oh, for example in this problem: https://leetcode.com/problems/binary-tree-level-order-traversal/

### Related

### Old Source Code

BFS is called **complete**, since it covers all possible cases:

- It will find the shortest path between the start and the goal if one exists.
- If no path exists that fact will be discovered.

### Runtime / Complexity

$V$ are nodes and $E$ are edges.

- Asymptotic running time of BFS is $O(∣V∣+∣E∣)$
- The computational complexity is $O(∣V∣)$ , which is not great in problems of higher dimensions, as the time to run the simulation increases exponentially with dimensionality.

### From CS341

This is a nice addition that enables us to keep track of parents and levels.