# Breadth First Search (BFS)

Authors: Benjamin Qi, Michael Cao

### 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 $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.

1queue<int> q;2q.push(1); // [1]3q.push(3); // [3, 1]4q.push(4); // [4, 3, 1]5q.pop(); // [4, 3]6cout << 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:

1Queue<Integer> q = new LinkedList<Integer>();2q.add(1); // [1]3q.add(3); // [3, 1]4q.add(4); // [4, 3, 1]5q.poll(); // [4, 3]6System.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 $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`

.

1deque<int> d;2d.push_front(3); // [3]3d.push_front(4); // [4, 3]4d.push_back(7); // [4, 3, 7]5d.pop_front(); // [3, 7]6d.push_front(1); // [1, 3, 7]7d.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`

.

1ArrayDeque<Integer> deque = new ArrayDeque<Integer>();2deque.addFirst(3); // [3]3deque.addFirst(4); // [4, 3]4deque.addLast(7); // [4, 3, 7]5deque.removeFirst(); // [3, 7]6deque.addFirst(1); // [1, 3, 7]7deque.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 |

### Implementation

C++

From the CSA article:

1#include <algorithm>2#include <fstream>3#include <iostream>4#include <queue>5using namespace std;6const int MAX_N = 100005;78vector<int> graph[MAX_N];9int dist[MAX_N];10bool visited[MAX_N];

Java

Implementation of the CSAcademy article's problem in Java:1import java.util.*;2import java.io.*;34class Main {56 static ArrayList<Integer> edges[];7 static int dist[];8 static boolean visited[];910 static void bfs(int startNode) {

### 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 |

### This section is not complete.

straightforward example

## Problems

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

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

CSES | Easy | ## Show TagsBFS | View Solution | ||

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 | Very Hard | External Sol |