Breadth First Search (BFS)

C++

C++

• push: inserts at the back of the queue
• pop: deletes from the front of the queue
• front: retrieves the element at the front without removing it.

Copy
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:

Copy
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

Python

Python

Python has a queue built-in module.

• Queue.put(n): Inserts element to the back of the queue.
• Queue.get(): Gets and removes the front element. If the queue is empty, this will wait forever, creating a TLE error.
• Queue.queue[n]: Gets the nth element without removing it. Set n to 0 for the first element.

Copy
from queue import Queue

q = Queue()	  # []
q.put(1)		 # [1]
q.put(2)		 # [1, 2]
v = q.queue[0]   # v = 1, q = [1, 2]
v = q.get()	  # v = 1, q = [2]
v = q.get()	  # v = 2, q = []
v = q.get()	  # Code waits forever, creating TLE error.

C++

C++

The four methods for adding and removing are push_back, pop_back, push_front, and pop_front.

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

Copy
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]

Python

Python

In Python, collections.deque() is used for a deque data structure. The four methods for adding and removing are appendleft, popleft, append, and pop.

Copy
d = collections.deque()
d.appendleft(3)  # [3]
d.appendleft(4)  # [4, 3]
d.append(7)  # [4, 3, 7]
d.popleft()  # [3, 7]
d.appendleft(1)  # [1, 3, 7]
d.pop()  # [1, 3]

C++

Copy
#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);

Java

Copy
import java.io.*;

import java.util.*;


public class Solution {
 	Code Snippet: Kattio (Click to expand)

	private static Map<Integer, LinkedList<Integer>> adj = new HashMap<>();

C++

Copy
#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] != '.');

Java

Copy
import java.util.*;
import java.io.*;

public class tracks {
	static final int[] dx = {0, 0, -1, 1};
	static final int[] dy = {-1, 1, 0, 0};
	static int N = 1, H, W;
	static int[][] grid, count;
	public static void main(String[] args) {
		FastIO io = new FastIO();