# Breadth First Search (BFS)

## About

Is a Graph or Tree traversal algorithm used to explore nodes and edges. It can also be used as a Search algorithm.

It is widely used in numerous situations such as shortest-path calculations, network analysis, and more.

It doesn't preserve shape of the traversal.

It uses `Queue` to store nodes in order.

{% hint style="info" %}
Each node is visited once, and all its edges are traversed once.

For a Graph with `V` vertices and `E` edges, $$O(V+E)$$.

For a Tree with `N` nodes, $$O(N)$$.
{% endhint %}

## How it works

BFS explores all nodes at the current "depth" (or level) before moving to nodes at the next depth.

<img src="https://917734093-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F3cZYot05lrDVVoPkSu2L%2Fuploads%2FzAyhEiLw569nttI5jcwk%2Ffile.excalidraw.svg?alt=media&#x26;token=952306c5-6760-4c8c-95fc-4301a4fdf982" alt="" class="gitbook-drawing">

#### In more Detail

{% hint style="warning" %}
In **Graphs**, you must also **mark visited nodes**, so that they don't get pushed again to the `Queue`.
{% endhint %}

{% hint style="success" %}
In `BST` where you garantee order, you may add additional conditions to prioritize going left or right first, depending on the `needle` value.
{% endhint %}

1. At start node `N`:
   1. Push `N` to the `Queue`.
   2. Push `N's` children to the `Queue`.
   3. Process `N` and remove it from the `Queue`.
2. Go to next node `N` at `Queue`:
   1. Push its children to the `Queue`.
   2. Process node `N`, and remove it from `Queue`.
3. Repeat `2.` until all nodes were processed.

```typescript
// Considering a Binary Tree
function bfs(head: BinaryNode<T>, needle: T): boolean {
    // Using a TS ArrayList will make it run in O(n²), because of shift/unshift of ArrayLists
    const queue = [head];
    
    while (queue.length) {
        const node = queue.shift();
        // Needle found
        if (node.value === needle) return true;
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return false;
}
```