Breadth-first Search

 Breadth-first Search

Breadth-first search(BFS) is an algorithm for traversing graph data structures. Apart from the graph it can be applied to a tree data structure for both traversal and searching.

Properties of Breadth-first Search :

1. The time complexity of BFS to traverse an entire graph takes time O(|V| + |E| ) where V refers to vertices and E for Edges in a graph.
2. This traversal algorithm takes a total of O(|V|) space for a complete traversal.
3. BFS internally uses a queue to explore the level of the node by level.
4. Instead of exploring node branches as far as possible like in BFS, it explores neighbour nodes at the depth level.

How BFS Works?

Breadth-first traversal (or Search) for a graph is similar to traversal in a tree and the approach here is to start from the root node and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

In the above figure, it is an example of a directed graph with the vertices [A, B, C, D, E] with the edges:

• A to B and A to C
• B to D
• D to E

So, the approach is to select any one of the vertexes as a root node and mark it as visited. Then push the vertex which are adjacent that is at same depth to a queue and pop the first element from queue and repeat the same process.

• Iterate over the array list of vertexes through the BFS helper function and push unvisited vertexes to the queue.
• Explore all the unvisited vertexes at the same depth with the help of queue.

Algorithm:

1. Create a multidimensional array list of integer types.
2. Add the vertices with their respective edges to the list.
3. Create a boolean array to keep track of visited vertices.
4. Create a queue of Integer type and push the root vertex.
5. Print the current vertex and mark it as visited.
6. Iterate through the adjacent unvisited vertices present in the list till the queue is empty.

Implementation of Breadth-first Search  in java:

The following  function requires an index of node and array as parameters.

class bfs {

    public static void main(String[] args) {

        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

        int vertex = 5;

        for (int i = 0; i < vertex; i++) {

            ArrayList<Integer> l = new ArrayList<Integer>();

            list.add(l);

        }

        // Here as from the above graph consider A,B,C,D,E as 0,1,2,3,4

        // These are following edges: 0->1 & 0->2

        // 1->3 & 2->4 & 3->4

        list.get(0).add(1);

        list.get(1).add(0);

        list.get(0).add(2);

        list.get(2).add(0);

        list.get(1).add(3);

        list.get(3).add(1);

        list.get(3).add(4);

        list.get(4).add(3);

        // set every vertex value as unvisited

        boolean[] visited = new boolean[vertex];

        for (int i = 0; i < vertex; i++) {

            visited[i] = false;

        }

        // pass the parameters to BFS function

        BFS(list, visited, vertex);

    }

    public static void BFS(ArrayList<ArrayList<Integer>> list, boolean visited[], int vertex) {

        BFS(list, vertex, visited);

    }

    public static void BFS(ArrayList<ArrayList<Integer>> list, int vertex, boolean visited[]) {

        LinkedList<Integer> queue = new LinkedList<>();

        queue.push(0);

        while (!queue.isEmpty()) {

            int temp = queue.poll();

            System.out.print(temp + " ");

            visited[temp] = true;

            Iterator<Integer> i = list.get(temp).listIterator();

            while (i.hasNext()) {

                int n = i.next();

                if (!visited[n]) {

                    visited[n] = true;

                    queue.add(n);

                }

            }

        }

    }

}

 

This program prints the vertex by visiting every vertex in the graph. As compared to depth-first search instead of backtracking it explores the level of the node by level.

I hope you guys liked this article and here are some articles you may like:

• Depth-first Search
  
• Queue in java
  
• Stack in java
  
• Circular Queue in java