PrevNext
Not Frequent
 0/12

Breadth First Search (BFS)

Authors: Benjamin Qi, Michael Cao, Andi Qu

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

Queues & Deques

Queues

A queue is a First In First Out (FIFO) data structure that supports three operations, all in O(1)\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 O(1)\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 i\texttt{i} for some deque dq\texttt{dq}, do dq[i]\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
CSAinteractive, implementation
PAPSgrid, 8-puzzle examples
cp-algocommon applications
KA
YoutubeIf 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 uu and vv." 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 O(V+E)\mathcal{O}(V + E) using a deque. Read the resource below for an explanation of how the algorithm works.

Resources
cp-algocommon 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 O(NM)\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

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasy
Show Tags

BFS

CSESEasy
Show Tags

BFS

CSESNormal
Show Tags

Cycle

CSANormal
Show Tags

BFS, DFS

Check CSA
SilverEasy
Show Tags

BFS

External Sol
GoldNormal
Show Tags

BFS

External Sol
GoldNormalExternal Sol
Old SilverNormal
Show Tags

BFS

External Sol
GoldHard
Show Tags

BFS

GoldHard
Show Tags

BFS

External Sol
GoldHard
Show Tags

BFS

External Sol
GoldVery HardExternal 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.

PrevNext