Breadth-First Search Algorithm for Graphs

Breadth-First Search (BFS) is an algorithm used for traversing or searching trees and graphs. In a breadth-first traversal, we start from a specific vertex to traverse the graph by first visiting that vertex, then all its adjacent vertices, followed by the neighbors of those adjacent vertices, continuing until all vertices connected to the starting vertex have been visited.

Breadth-First Search is typically implemented using a queue. Specifically, we can begin at any arbitrary vertex in the graph, mark it as visited, and add it to the queue. Then, we extract a vertex v from the queue, visit all its unvisited adjacent vertices, mark them as visited, and sequentially add them to the queue. This process is repeated until the queue is empty, indicating that the traversal has ended.

Breadth-First Search helps us find shortest paths in graphs, generate minimum spanning trees, and solve other problems like maze navigation or the Eight-Puzzle problem.

It should be noted that the time complexity of Breadth-First Search can also reach O(n + m), where n is the number of vertices and m is the number of edges in the graph. Therefore, when processing large-scale graphs, other algorithms may need to be considered.

Java Implementation

::: code-tabs
@tab BFS

public class BFS {
    public static String bfs(Graph g){
        String result = "";
        if (g.vertices < 1){
            return result;
        }
        boolean[] visited = new boolean[g.vertices];
        for(int i=0;i<g.vertices;i++) { 
            if(!visited[i]){ 
                result = result + bfsVisit(g, i, visited); 
            } 
        }
        return result;
    }
    public static String bfsVisit(Graph g, int source, boolean[] visited) {
        String result = "";
        Queue<Integer> queue = new Queue<>(g.vertices);
        queue.enqueue(source);
        visited[source] = true;
        while (!queue.isEmpty()) {
            int current_node = queue.dequeue();
            result += String.valueOf(current_node);
            DoublyLinkedList<Integer>.Node temp = null;
            if(g.adjacencyList[current_node] != null)
                temp = g.adjacencyList[current_node].headNode;
            while (temp != null) {
                if (!visited[temp.data]) {
                    queue.enqueue(temp.data);
                    visited[temp.data] = true; // Visit the current Node
                }
                temp = temp.nextNode;
            }
        }
        return result;
    }
}

@tab Graph

public class Graph{
    int vertices;
    DoublyLinkedList<Integer> adjacencyList[];
    
    @SuppressWarnings("unchecked")
    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new DoublyLinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new DoublyLinkedList<>();
        }
    }
    public void addEdge(int source, int destination){
        if (source < vertices && destination < vertices){
        this.adjacencyList[source].insertAtEnd(destination);
        }
    }
    public void printGraph(){
        System.out.println(">>Adjacency List of Directed Graph<<");
        for (int i = 0; i < vertices; i++){
            if(adjacencyList[i]!=null){
                System.out.print("|" + i + "| => ");
                DoublyLinkedList<Integer>.Node temp = adjacencyList[i].getHeadNode();
                while (temp != null){
                    System.out.print("[" + temp.data + "] -> ");
                    temp = temp.nextNode;
                }
                System.out.println("null");
            }else{
                System.out.println("|" + i + "| => "+ "null");
            }
        }
    }
}

@tab DoublyLinkedList

public class DoublyLinkedList<T> {
    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; 
        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--;
    }
}

@tab Queue

public class Queue<V> {
    private int maxSize;
    private V[] array;
    private int front;
    private int back;
    private int currentSize;
    @SuppressWarnings("unchecked")
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        array = (V[]) new Object[maxSize];
        front = 0;
        back = -1;
        currentSize = 0;
    }
    public int getMaxSize() {
        return maxSize;
    }
    public int getCurrentSize() {
        return currentSize;
    }
    public V top() {
        return array[front];
    }
    public boolean isEmpty() {
        return currentSize == 0;
    }
    public boolean isFull() {
        return currentSize == maxSize;
    }
    public void enqueue(V value) {
        if (isFull())
            return;
        back = (back + 1) % maxSize; 
        array[back] = value;
        currentSize++;
    }
    public V dequeue() {
        if (isEmpty())
            return null;
        V temp = array[front];
        front = (front + 1) % maxSize; 
        currentSize--;
        return temp;
    }
}

:::