Breadth First Search

Breadth-First Search algorithm for graphs (nonlinear data structures) is based on the idea of searching for an element across all the adjacent nodes of the current node before traversing their respective neighboring nodes discovered along the way.

Consider the following illustration:

Assuming the start node to be the one with value 1, the nodes that the algorithm will next traverse will be 2 and 4 (in any order) before their respective adjacent nodes, like 3 or 5, can be traversed.

An additional data structure (Queue) is required to temporarily hold intermediate nodes to block their processing until all the prior nodes in the sequence are processed. On a high level, BFS the algorithm can be represented as a sequence of the following steps:

1. Initialize discovered queue Q with the start node. This will hold all the discovered but not visited nodes.
2. Initialize visited array V as a boolean array of size equal to the number of vertices.
3. While the Q is not empty, dequeue its head element.
4. Return if element is equal to the key we are looking for.
5. Else, mark element as visited in the V array.
6. For all the neighbors adj of element:
   1. if adj is not visited already in the V and is not discovered in Q, add it to Q.
   2. return to step 3.

Let’s try this algorithm for the given input for key 3:

1. Discovered: [1]; Visited: [] - We start with a blank visited array, and the discovered queue is initialized with element 1.
2. Discovered: [2,4]; Visited: [1] - Next, we dequeue the head of the queue, and as it does not match with the key, we mark it visited. Its neighbors, ‘2’ and ‘4’, are added to the discovered queue.
3. Discovered: [4,3]; Visited: [1,2] - In the next iteration, we dequeue ‘2’ from the head of the queue, which fails the comparison test and ends up as visited. Its neighbor ‘3’ is added to the end of the discovered queue.
4. Discovered: [3,5]; Visited: [1,2,4] - Similar to the previous step, ‘4’ is dequeued from the queue and is marked visited for failing the comparison test. Its neighbor ‘5’ is added to the end of the queue.

In the next step, when we dequeue 3 from the head of the discovered queue, it will pass the comparison test and is returned to denote the presence.

public int search(int[][] graph, int start, int key){
    boolean[] visited = new boolean[graph.length];
    Queue<Integer> discovered = new LinkedList<>();
    discovered.add(start);
    
    while(!discovered.isEmpty()){
        Integer visitedNode = discovered.poll();
        if(visitedNode == key){
            return visitedNode;
        }
        visited[visitedNode] = true;
        
        // for each neighbor, check if the two vertices are connected
        // if yes, and the neighbor is not visited already
        // add it to the discovered list
        for(int neighbor = 0; neighbor < graph.length; neighbor++){
            // graph[visitedNode][neighbor] != 0 is neighbor check
            // !visited[neighbor] - is not be visited already
            // !discovered.contains(neighbor) - is not discovered already via some other node
            if(graph[visitedNode][neighbor] != 0 && !visited[neighbor] && !discovered.contains(neighbor){
                discovered.add(neighbor);
            }
        }
    }
    // return -1 to denote absence
    return -1;
}

The overall complexity of this algorithm is dependent on the underlying data structure used to represent the graph:

1. For an adjacency matrix representation, we will have to traverse an entire row of size equal to the number of vertices to discover all the adjacent nodes, so the complexity for V nodes will be \(O(V^2)\).
2. For an adjacency list representation, each node will only have a list of its adjacent elements of size E, and hence the overall complexity becomes \(O(E) + O(V) = O(E+V)\).