Breadth-first search in java | using Adjacency list and Adjacency Matrix.

Dear Friends,

I am here with a famous traversal method for Graph : Breadth first search [BFS]

This method is based on the idea of visiting a graph by taking breadth wise approach. The method will become more clear as we see the diagram below and then go through the code for BFS.

We need three basic entities for implementation of BFS

1. Graph
2. Queue
3. State  : {NEW, IN_Q, VISITED} This represents the Graph-node's state, initially all the nodes are in NEW state and as it is added in the queue, its state is changed to IN_Q and as it is removed from the queue, its state is changed to VISITED.




State : {NEW,IN_Q,VISITED}
Queue : size = 0
Graph:
vertices = {1,2,3,4,5,6,7}
node1 : 
neighbourList = 2->3->4->null    
state : State.NEW
node2 : 
neighbourList = 1->5->null                                
state : State.NEW
node3 : 
neighbourList = 1->6->7->null                          
state : State.NEW
node4 : 
neighbourList = 1->null                                     
state : State.NEW
node5 : 
neighbourList = 2->null                                     
state : State.NEW
node6 :
neighbourList = 3->null                                     
state : State.NEW
node7 : 
neighbourList = 3->null                                     
state : State.NEW
node8 : 
neighbourList = null                                          
state : State.NEW
node9 : 
neighbourList = 10->11->12->13->null            
state : State.NEW
node10 : 
neighbourList = 9->11->null                           
state : State.NEW
node11 : 
neighbourList = 9->10->14->null                   
state : State.NEW
node12 : 
neighbourList = 9->14->null
state : State.NEW
node13 : 
neighbourList = 9->null
state : State.NEW
node14 : 
neighbourList = 11->12->null
state : State.NEW


Basic BFS Algorithm
1. Execute a loop for 'node-size' number of iterations.
2. for each node with state != State.VISITED call the bfs(Node currentNode)
3. queue.add(currentNode) and set the state of the current node :  currentNode.state = State.IN_Q
4. run a while loop until queue.isEmpty() != true
   Node visitedNode = queue.remove()
   visitedNode.state = State.VISITED
   print(visitedNode)
   queue.add(all the nodes with state = State.NEW from visitedNode.neighbourList and mark each node's state as State.IN_Q)

Lets Apply BFS to above graph

Adding in the queue,  the node1 , marked it as In_Q
Removing from queue, the node1 , marked it as VISITED and Printing it
Printing the Visited node1
Adding in the queue,  the node2 , marked it as In_Q
Adding in the queue,  the node3 , marked it as In_Q
Adding in the queue,  the node4 , marked it as In_Q
Removing from queue, the node2 , marked it as VISITED and Printing it
Printing the Visited node2
Adding in the queue,  the node5 , marked it as In_Q
Removing from queue, the node3 , marked it as VISITED and Printing it
Printing the Visited node3
Adding in the queue,  the node6 , marked it as In_Q
Adding in the queue,  the node7 , marked it as In_Q
Removing from queue, the node4 , marked it as VISITED and Printing it
Printing the Visited node4
Removing from queue, the node5 , marked it as VISITED and Printing it
Printing the Visited node5
Removing from queue, the node6 , marked it as VISITED and Printing it
Printing the Visited node6
Removing from queue, the node7 , marked it as VISITED and Printing it
Printing the Visited node7
Adding in the queue,  the node8 , marked it as In_Q
Removing from queue, the node8 , marked it as VISITED and Printing it
Printing the Visited node8
Adding in the queue,  the node9 , marked it as In_Q
Removing from queue, the node9 , marked it as VISITED and Printing it
Printing the Visited node9
Adding in the queue,  the node10 , marked it as In_Q
Adding in the queue,  the node11 , marked it as In_Q
Adding in the queue,  the node12 , marked it as In_Q
Adding in the queue,  the node13 , marked it as In_Q
Removing from queue, the node10 , marked it as VISITED and Printing it
Printing the Visited node10
Removing from queue, the node11 , marked it as VISITED and Printing it
Printing the Visited node11
Adding in the queue, the node14 , marked it as In_Q
Removing from queue, the node12 , marked it as VISITED and Printing it
Printing the Visited node12
Removing from queue, the node13 , marked it as VISITED and Printing it
Printing the Visited node13
Removing from queue, the node14 , marked it as VISITED and Printing it
Printing the Visited node14

Now Lets see as how we can implement it : Lets use Adjacency List. Friends Please find the code in java below:

/**
 * 
 * @author krishna kumar
 * 
 *         This is a basic implementation of BFS for Graph using Adjacency list.
 *
 */
public class Graph {

    private Node[] vertices; // stores the nodes of the graph
    private int size; // number of nodes in the graph
    private Queue queue;
    public Graph(int size) {
        this.size = size;
        vertices = new Node[size];
        addNodes();
        queue = new Queue(size);
    }

    public class Node {
        int name;
        Neighbour neighbourList;
        State state; 
        Node(int name) {
            this.name = name;
            state = State.NEW;
        }
    }

    public class Neighbour {
        int index;
        Neighbour next;

        public Neighbour(int index, Neighbour next) {
            this.index = index;
            this.next = next;
        }
    }
    private void addNodes(){
        for(int i = 1; i <= size ; i++){
            addNode(i);
        }
    }
    public void addNode(int name) {
        vertices[name - 1] = new Node(name);
    }

    public void addEdge(int sourceName, int destiName) {
        int srcIndex = sourceName - 1;
        int destiIndex = destiName - 1;
        Node srcNode = vertices[srcIndex];
        Node destiNode = vertices[destiIndex];
        srcNode.neighbourList = new Neighbour(destiIndex, srcNode.neighbourList);
        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        destiNode.neighbourList = new Neighbour(srcIndex, destiNode.neighbourList);
    }



    public void traverseGraph() {
        System.out.println("Using BFS Traversing the graph");

        for (int i = 0; i < size; i++) {
            if (vertices[i].state != State.VISITED) {
                bfs(vertices[i]);
            }
        }
    }

    private void bfs(Node currentNode) {
        queue.add(currentNode);
        currentNode.state = State.IN_Q;
        while(!queue.isEmpty()){
            Node visitedNode = queue.remove();
            visitedNode.state = State.VISITED;
            System.out.println(visitedNode.name);
            Neighbour temp = visitedNode.neighbourList;
            while(temp != null){
                Node neighbour = vertices[temp.index];
                if(neighbour.state == State.NEW){
                    queue.add(neighbour);
                    neighbour.state = State.IN_Q;
                }
                temp = temp.next;
            }
        }
    }

    public enum State {
        NEW, IN_Q, VISITED
    };

    /**
     * 
     * This is a simple queue implemented using array. Although ideally queue
     * should be implemented in circular style so as to use the empty area when
     * items are deleted from the front but for BFS implementation we each item
     * is added only once so if the size of the queue is taken as the size of
     * the items then there is no need for circular styled implementation.
     *
     */
    public class Queue {
        Node[] queue;
        int maxSize;
        int front = -1,rear = -1;

        Queue(int maxSize) {
            this.maxSize = maxSize;
            queue = new Node[maxSize];
        }

        public void add(Node node) {
            queue[++rear] = node;
        }

        public Node remove() {
            Node node = queue[++front];
            queue[front] = null;
            return node;
        }

        public boolean isEmpty() {
            return front == rear;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(14);
        graph.addEdge(1, 4);
        graph.addEdge(1, 3);
        graph.addEdge(1, 2);
        graph.addEdge(2, 5);
        graph.addEdge(3, 7);
        graph.addEdge(3, 6);
        graph.addEdge(9, 13);
        graph.addEdge(9, 12);
        graph.addEdge(9, 11);
        graph.addEdge(9, 10);
        graph.addEdge(10, 11);
        graph.addEdge(11, 14);
        graph.addEdge(12, 14);
        graph.traverseGraph();
    }
}

Below friends, please find the code for Implementation of BFS using Adjacency Matrix

/**
 * 
 * @author krishna kumar
 * 
 *         Below code shows basic implementation of DFS in a graph. Graph has
 *         been implemented using adjacency matrix
 *
 */
public class Graph {
    private int[][] adjacencyMatrix;
    private int size; // number of nodes in the graph
    private State[] states;
    private Queue queue;
    public Graph(int size) {
        this.size = size;
        adjacencyMatrix = new int[size][size];// Initialized with all 0s
        states = new State[size];
        for (int i = 0; i < size; i++) {
            states[i] = State.NEW;
        }
        queue = new Queue(size);
    }

    public void addEdge(int sourceName, int destinationName) {
        int sourceIndex = sourceName - 1;
        int destinationIndex = destinationName - 1;
        adjacencyMatrix[sourceIndex][destinationIndex] = 1;
        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        adjacencyMatrix[destinationIndex][sourceIndex] = 1;
    }

    public void traverseGraph() {
        System.out.println("Using BFS Traversing the graph");

        for (int i = 0; i < size; i++) {
            if (states[i] != State.VISITED) {
                bfs(i+1);
            }
        }
    }

    private void bfs(int currentNodeName) {
        queue.add(currentNodeName);
        states[currentNodeName-1] = State.IN_Q;
        while(!queue.isEmpty()){
            int visitedNodeName = queue.remove();
            states[visitedNodeName-1] = State.VISITED;
            System.out.println(visitedNodeName);
            for(int i = 0; i < size; i++){
                if(adjacencyMatrix[visitedNodeName-1][i] != 0){
                    if(states[i] == State.NEW){
                        queue.add((i+1));
                        states[i] = State.IN_Q;
                    }
                }
            }
        }
    }

    public enum State {
        NEW, IN_Q, VISITED
    };

    /**
     * 
     * This is a simple queue implemented using array. Although ideally queue
     * should be implemented in circular style so as to use the empty area when
     * items are deleted from the front but for BFS implementation we each item
     * is added only once so if the size of the queue is taken as the size of
     * the items then there is no need for circular styled implementation.
     *
     */
    public class Queue {
        Integer[] queue;
        int maxSize;
        int front = -1,rear = -1;

        Queue(int maxSize) {
            this.maxSize = maxSize;
            queue = new Integer[maxSize];
        }

        public void add(int node) {
            queue[++rear] = node;
        }

        public int remove() {
            int node = queue[++front];
            queue[front] = null;
            return node;
        }

        public boolean isEmpty() {
            return front == rear;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(14);
        
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);
        graph.addEdge(3, 7);
        graph.addEdge(9, 10);
        graph.addEdge(9, 11);
        graph.addEdge(9, 12);
        graph.addEdge(9, 13);
        graph.addEdge(10, 11);
        graph.addEdge(11, 14);
        graph.addEdge(12, 14);
        graph.traverseGraph();
    }

}