# Breadth First Search (BFS)

Authors: Benjamin Qi, Michael Cao, Andi Qu

### Prerequisites

Traversing a graph in a way such that vertices closer to the starting vertex are processed first.

## Queues & Deques

Resources | |||
---|---|---|---|

CPH | |||

PAPS |

### Queues

A queue is a First In First Out (FIFO) data structure that supports three operations, all in $\mathcal{O}(1)$ time.

C++

#### C++

`push`

: insertion at the back of the queue`pop`

: deletion from the front of the queue`front`

: which retrieves the element at the front without removing it.

queue<int> q;q.push(1); // [1]q.push(3); // [3, 1]q.push(4); // [4, 3, 1]q.pop(); // [4, 3]cout << q.front() << endl; // 3

Java

#### Java

`add`

: insertion at the back of the queue`poll`

: deletion from the front of the queue`peek`

: which retrieves the element at the front without removing it

Java doesn't actually have a `Queue`

class; it's only an interface. The most commonly used implementation is the `LinkedList`

, declared as follows:

Queue<Integer> q = new LinkedList<Integer>();q.add(1); // [1]q.add(3); // [3, 1]q.add(4); // [4, 3, 1]q.poll(); // [4, 3]System.out.println(q.peek()); // 3

### Deques

A **deque** (usually pronounced "deck") stands for double ended queue and is a combination of a stack and a queue, in that it supports $\mathcal{O}(1)$ insertions and deletions from both the front and the back of the deque. Not very common in Bronze / Silver.

C++

#### C++

The four methods for adding and removing are `push_back`

, `pop_back`

, `push_front`

, and `pop_front`

.

deque<int> d;d.push_front(3); // [3]d.push_front(4); // [4, 3]d.push_back(7); // [4, 3, 7]d.pop_front(); // [3, 7]d.push_front(1); // [1, 3, 7]d.pop_back(); // [1, 3]

You can also access deques in constant time like an array in constant time with the `[]`

operator. For example, to access the element $\texttt{i}$ for some deque $\texttt{dq}$, do $\texttt{dq[i]}$.

Java

#### Java

In Java, the deque class is called `ArrayDeque`

. The four methods for adding and removing are `addFirst`

, `removeFirst`

, `addLast`

, and `removeLast`

.

ArrayDeque<Integer> deque = new ArrayDeque<Integer>();deque.addFirst(3); // [3]deque.addFirst(4); // [4, 3]deque.addLast(7); // [4, 3, 7]deque.removeFirst(); // [3, 7]deque.addFirst(1); // [1, 3, 7]deque.removeLast(); // [1, 3]

## Breadth First Search

Focus Problem – read through this problem before continuing!

### Resources

Resources | |||
---|---|---|---|

CSA | interactive, implementation | ||

PAPS | grid, 8-puzzle examples | ||

cp-algo | common applications | ||

KA | |||

Youtube | If you prefer a video format |

### Solution - Message Route

C++

int n,m, dist[MX], pre[MX];vi adj[MX];int main() {setIO(); re(n,m);F0R(i,m) {int a,b; re(a,b);adj[a].pb(b), adj[b].pb(a);}FOR(i,2,n+1) dist[i] = MOD;

### Pro Tip

In the gold division, the problem statement will almost never directly be, "Given an unweighted graph, find the shortest path between node $u$ and $v$." Instead, the difficulty in many BFS problems are converting the problem into a graph on which we can run BFS and get the answer.

## 0/1 BFS

A 0/1 BFS finds the shortest path in a graph where the weights on the edges can only be 0 or 1, and runs in $\mathcal{O}(V + E)$ using a deque. Read the resource below for an explanation of how the algorithm works.

Resources | |||
---|---|---|---|

cp-algo | common applications |

Focus Problem – read through this problem before continuing!

Consider the graph with an edge between each pair of adjacent cells with tracks, where the weight is 0 if the tracks are the same and 1 otherwise. The answer is simply the longest shortest-path from the top left cell.

Since the weight of each edge is either 0 or 1 and we want the shortest paths from the top left cell to each other cell, we can apply 0/1 BFS. The time complexity of this solution is $\mathcal O(NM)$.

C++

#include <bits/stdc++.h>using namespace std;int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};int n, m, depth[4000][4000], ans = 1;string snow[4000];bool inside(int x, int y) {return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CSES | Easy | ## Show TagsBFS | ||||

CSES | Easy | ## Show TagsBFS | ||||

CSES | Normal | ## Show TagsCycle | ||||

CSA | Normal | ## Show TagsBFS, DFS | Check CSA | |||

Silver | Easy | ## Show TagsBFS | External Sol | |||

Gold | Normal | ## Show TagsBFS | External Sol | |||

Gold | Normal | External Sol | ||||

Old Silver | Normal | ## Show TagsBFS | External Sol | |||

Gold | Hard | ## Show TagsBFS | ||||

Gold | Hard | ## Show TagsBFS | External Sol | |||

Gold | Hard | ## Show TagsBFS | External Sol | |||

Gold | Very Hard | External Sol |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Breadth First Search (BFS)!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.