Overview

Introduction

Before I dive into what BFS is and how to perform a BFS, I will state the prerequisites to this post. First, I hope you are familiar with Binary Trees and 2D arrays. Second(not that necessary as I will go over this), you need to know different ways to represent graphs. For example: Adjacent Lists and Adjacent Matrices. That's about it, in this post, I'll walk you through how to do different types of BFS which is more formally known as Breadth-First Search.

Background

When you google BFS or hear other programmers talk about BFS, you see that it's usually used on graphs. However, BFS has many uses, including on Arrays. You can tell from it's name that BFS is performing a level search(Breadth-First), so this type of search algorithm is especially helpful if you know that your answer is near the root. BFS, however, is harder to implement than other search algorithms such as DFS. Some common uses of BFS are: shortest paths implementations and many other modifications of BFS on 2D arrays. In short, BFS is an elegant search algorithm and has many practical use.

BFS on Binary Trees

We are now going to get started on how to perform a BFS. We'll start off simple with a Binary Tree. If you don't know what a Binary Tree is yet, then check this out! A BFS algorithm does level search(this is very important, keep this in mind). Therefore, doing BFS on a Binary Tree requires us to take use of the child nodes and the data that they contain. Before we continue, I'll put the implementation of a Binary Tree below for future reference.

class Node {
    int val; //Value of the node
    Node left, right;  //Child nodes

    //Constructor
    public Node(int value) {
        val = value;
        left = right = null;
    }
}

class BinaryTree {
    // Root of Binary Tree
    Node root;

    // Constructors
    BinaryTree(int val) {
        root = new Node(val);
    }

    BinaryTree() {
        root = null;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        //Creates the root
        tree.root = new Node(1);  //Root with a value of 1

        //Child nodes of the root with values 2 and 3
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);

        //Child node of the node with value 2
        tree.root.left.left = new Node(4);
        //Child node of the node with value 3
        tree.root.right.left = new Node(5);
        tree.root.right.right = new Node(6);
        /*
               Resulting tree
                    1
                /       \
               2          3
             /   \       /  \
            4   null    5    6
        */
    }
}

Hopefully, you understand how the Binary Tree structure works. If you didn't, all you need to know is that node.left refers to the left subchild, node.right refers to the right subchild, and node.val refers to the values of the current node. Now we can get started! Remember when I mentioned BFS is level search? Well, if you forgot, I'll remind you one more time. This is the core concept for BFS. You simply cannot understand BFS without knowing that. Now, to perform a level search, you obviously need data from the previous level to the next level. In this case, it's the child nodes inside of the parent nodes that holds this. Starting from the root, root.left and root.right goes to the next level. We make root.left and root.right a Node by themselves called a and b respectively and the next level would be a.left, a.right, b.left, and b.right. You should now be getting a sense of how this should be done. With that, we can now talk about the data structure used for BFS. Obviously, once we've traversed a level, we want to delete the node so the level doesn't get deleted. The Queue is the perfect data structure for BFS. A Queue is first in, first out. Therefore, it maintains the relative ordering of the nodes. For example, I can push root.left and root.right in. Then when I pop from the queue, root.left comes out. Therefore, I can go to the next level with the information that I got from popping root.left out. Of course, we can't just pile on the .left and .right like root.left.left.left.right. So we will store these as nodes, every child is a node themselves, and we can call node.left to get its child data. At this point, I will show the implementation for this algorithm and will provide the data in the queues right besides it. If you don't understand now, you will once you visualize it.

Above is the Binary Tree built from the Binary Tree Class code from above. It also shows the values in the queue as the algorithm goes from one level to the next. Below is the BFS traversal algorithm for a Binary Tree. By looking at the code and the illustration above, you should be able to get a better sense of how to perform a BFS algorithm and how it works. With that, we can go into BFS in a 2D array.

public static void BFS(BinaryTree tree){
    Queue<Node> q = new LinkedList<>(); //Instantiates a Queue
    q.add(tree.root); //Adds root into the queue, MUST do
    while (!q.isEmpty()){ //if the queue becomes then the traversal is over
        int s = q.size(); //Gets the size of the queue
        for (int i = 0; i < s; i++) {
            Node cur = q.poll(); //Gets the current node to traverse, .poll() returns the Node and pops it
            System.out.print(cur.val + " "); //Prints the current node, notice that it is not println because the level might not have finished yet
            if(cur.left != null){
                q.add(cur.left); //adds cur.left if it's not null
            }
            if(cur.right != null){
                q.add(cur.right); //adds cur.right if it's not null
            }
        }
        System.out.println(); //prints a new line because the level is finished
    }
}

BFS on 2D Arrays

The reason I explained BFS on Binary Trees first was because a Binary Tree Node only has 2 child nodes and it is very easy to visualize BFS on a tree as well. Now that you all have a sense of what BFS is, we can get into a more modified use of BFS. What I want to talk about in this section is just doing a simple BFS on a 2D array. More formally, we will use a $5\times5$ array and start the search at cell $(2, 2)$($0$-indexed). We also want our BFS to search the surrounding 8 cells instead of the surround 4 cells. However, you will soon realize a problem. The problem is that there might be repeats as you move outwards. To solve this, we can sacrifice some memory and create a boolean visited 2D array. This way, when we visit a cell, we can mark that same cell in the boolean array as true and when we are adding cells into the queue, we can check $!\texttt{visited}[i][j]$ to make sure that it haven't been visited yet. These are the types of modifications that are prominent in BFS algorithms. Feel free to try this problem on your own, the implementation with comments are provided below in case you got stuck. If you would like to see BFS on an N-ary tree, check out this video (Embeded below)! I talk about adjacency list and adjacency matrix in that video as well.

import java.util.LinkedList;
import java.util.Queue;
import static java.lang.System.out;

class Point{
    //point class to store the i and j values
    public int i;
    public int j;
    public Point(int x, int y){
        i = x;
        j = y;
    }
}

public class BFSExample{
    static int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};  //Arrays for up, down, right, left movement
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    public static void main(String[] args) {
        int[][] traverse = {
            {1,  2,  3,  4,  5},
            {6,  7,  8,  9,  10},
            {11, 12, 13, 14, 15},
            {16, 17, 18, 19, 20},
            {21, 22, 23, 24 ,25}
        }; //The array to traverse

        boolean[][] visited = new boolean[5][5]; //Visited boolean array
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(2, 2));
        visited[2][2] = true; //setting the start cell as visited
        while (!q.isEmpty()){
            int s = q.size();
            for (int i = 0; i < s; i++) {
                Point cur = q.poll(); //getting the current point from the queue
                out.print(traverse[cur.i][cur.j] + " "); //printing out the current value
                for (int j = 0; j < 8; j++) {
                    int newi = cur.i + dx[j];
                    int newj = cur.j + dy[j];
                    if(newi < 0 || newi >= traverse.length || newj < 0 || newj >= traverse[0].length){
                        //Checking if the newi and newj are out of bounds
                        continue;
                    }

                    if(visited[newi][newj]){ //Checking to see if it has already been visited
                        continue;
                    }
                    q.add(new Point(newi, newj)); //adding the new points into the queue
                    visited[newi][newj] = true; //setting the next cells as visited
                }
            }
            out.println();
        }
    }
}