Breadth First Search (BFS)

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

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

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]

C++

From the CSA article:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
const int MAX_N = 100005;

vector<int> graph[MAX_N];
int dist[MAX_N];
bool visited[MAX_N];

Java

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

class Main {

    static ArrayList<Integer> edges[];
    static int dist[];
    static boolean visited[];

    static void bfs(int startNode) {