PrevNext
Not Frequent
 0/12

Breadth First Search (BFS)

Authors: Benjamin Qi, Michael Cao

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)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)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 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.

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
CSAinteractive, implementation
PAPSgrid, 8-puzzle examples
cp-algocommon 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;
7
8vector<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.*;
3
4class Main {
5
6 static ArrayList<Integer> edges[];
7 static int dist[];
8 static boolean visited[];
9
10 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 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

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

straightforward example

Problems

StatusSourceProblem NameDifficultyTagsSolution
CSESEasy
Show Tags

BFS

CSESEasy
Show Tags

BFS

View Solution
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
GoldVery HardExternal Sol

Module Progress:

Give Us Feedback on Breadth First Search (BFS)!

PrevNext