Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Challenge: Implement Breadth First Search

Explore how to implement the breadth first search (BFS) algorithm in Java for both connected and unconnected graphs. Learn to traverse graphs level-by-level using adjacency lists, applying learned data structures to solve traversal challenges accurately.

We'll cover the following...

Problem statement

In this exercise, you have to implement the breadth first search traversal in Java. It is a level-by-level searching algorithm for the graph, so we are going to use our already-implemented graph class for this task (since we have already covered the implementation of graph).

Note: Your solution should work for both connected and unconnected graphs. For an unconnected graph, the order of output should depend upon indices in ascending order.

To solve this problem, all the previously implemented data structures will be available to us.

Input

The input is a graph in the form of an adjacency list.

Output

The output is a string containing the vertices of the graph listed in the correct order of traversal.

Sample input

Graph:

Vertex Edges
0 1, 2
1 3, 4
2 None
3 None
4 None

In the input column of test cases, this graph is represented as: |V|=5, E:[(0,1)(0,2)(1,3)(1,4)], where, |V| represents the number of vertices and E represents the edges.

Sample output

"01234"

Coding exercise

First, take a close look and design a step-by-step algorithm before jumping to the implementation. This problem is designed for your practice, so initially try to solve it on your own. If you get stuck, you can always refer to the solution provided in the solution section. Good Luck!

Java
public class DoublyLinkedList<T> {
    //Node inner class for DLL
    public class Node {
        public T data;
        public Node nextNode;
        public Node prevNode;
    }
    public Node headNode;
    public Node tailNode;
    public int size;
    public DoublyLinkedList() {
        this.headNode = null;
        this.tailNode = null;
    }
    public boolean isEmpty() {
        if (headNode == null && tailNode == null)
            return true;
        return false;
    }
    public Node getHeadNode() {
        return headNode;
    }
    public Node getTailNode() {
        return tailNode;
    }
    public int getSize() {
        return size;
    }
    public void insertAtHead(T data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = this.headNode; //Linking newNode to head's nextNode
        newNode.prevNode = null;
        if (headNode != null)
            headNode.prevNode = newNode;
        else
            tailNode = newNode;
        this.headNode = newNode;
        size++;
    }
    public void insertAtEnd(T data) {
        if(isEmpty()) {
            insertAtHead(data);
            return;
        }
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        newNode.prevNode = tailNode;
        tailNode.nextNode = newNode;
        tailNode = newNode;
        size++;
    }
    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = headNode;
        System.out.print("List : null <- ");
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.nextNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }
    public void printListReverse() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
        }
        Node temp = tailNode;
        System.out.print("List : null <- ");
        while (temp.prevNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.prevNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }
    public void deleteAtHead() {
        if (isEmpty())
            return;
        headNode = headNode.nextNode;
        if (headNode == null)
            tailNode = null;
        else
            headNode.prevNode = null;
        size--;
    }
    public void deleteAtTail() {
        if (isEmpty())
            return;
        tailNode = tailNode.prevNode;
        if (tailNode == null)
            headNode = null;
        else
            tailNode.nextNode = null;
        size--;
    }
}