PrevNext
Not Frequent
 0/17

Breadth First Search (BFS)

Authors: Benjamin Qi, Michael Cao, Andi Qu, Neo Wang

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
CSA

interactive, implementation

PAPS

grid, 8-puzzle examples

cp-algo

common applications

KA
Youtube

If you prefer a video format

Solution - Message Route

Time Complexity: O(V+E)\mathcal{O}(V+E)

We can observe is that there are many possible shortest paths to output. Fortunately, the problem states that we can print any valid solution. Notice that like every other BFS problem, the distance of each node increases by 11 when we travel to the next level of unvisited nodes. However, the problem requires that we add additional information - in this case, the path. When we traverse from node aa to bb, we can set the parent of bb to aa. After the BFS is complete, this allows us to backtrack through the parents which ultimately leads us to our starting node. We know to terminate at node 11 because it's the starting node. If there is no path to our end node, then its distance will remain at INT_MAX.

For the test input, we start with the following parent array.

Node 1 2 3 4 5
Parent 0 0 0 0 0
Distance 0 INT_MAX INT_MAX INT_MAX INT_MAX

After visiting children of node 11:

Node 1 2 3 4 5
Parent 0 1 1 1 0
Distance 0 1 1 1 INT_MAX

After visiting node 55 from node 44:

Node 1 2 3 4 5
Parent 0 1 1 1 4
Distance 0 1 1 1 2

To determine the path, we can backtrack from node n1n \rightarrow 1, in this case 515 \rightarrow 1, pushing each value that we backtrack into a vector. The path we take is 5parent[5]=4parent[4]=15 \rightarrow \texttt{parent}[5]=4 \rightarrow \texttt{parent}[4] =1 which corresponds to the vector [5,4,1][5, 4, 1]. We break at node 11 because it was the initial starting node. Finally, we reverse the vector and print out its length (in this case, 33).

C++

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
int main() {
int N, M; cin >> N >> M;
vi dist(N+1,INT_MAX), parent(N+1);
vector<vi> adj(N+1);

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

common applications

Focus Problem – read through this problem before continuing!

Complexity: O(NM)\mathcal O(NM)

We can use the following greedy strategy to find our answer:

  • Run flood fill to find each connected component with the same tracks.
  • Construct a graph where the nodes are the connected components and there are edges between adjacent connected components.
  • The answer is the maximum distance from the node containing (1,1)(1, 1) to another node. We can use BFS to find this distance.

For a detailed proof of why this works, see the official editorial.

Although this gives us an O(NM)\mathcal O(NM) solution, there is a simpler solution using 0/1 BFS!

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. This is because going from one track to another same one is like not leaving a node (hence the cost is 00), while going from one track to a different one is like traversing the edge between two nodes (hence the cost is 11).

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 NameDifficultyTags
CSESEasy
Show TagsBFS
CSESEasy
Show TagsBFS
SilverEasy
Show TagsBFS
CSESNormal
Show TagsCycle
CSANormal
Show TagsBFS, DFS
Old SilverNormal
Show TagsBFS
GoldNormal
Show TagsBFS
GoldNormal
Show TagsBFS
Old SilverNormal
Show TagsBFS
GoldNormal
Show TagsBFS
IOINormal
GoldHard
Show TagsBFS
GoldHard
Show TagsBFS
GoldHard
Show TagsBFS
GoldVery Hard
Show TagsBFS

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!

PrevNext