Breadth First Traversal(BFS) in Graph

Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree. The only thing here is, unlike trees, graphs may contain cycles, so we may come to the same vertex again. To avoid processing a vertex more than once, we use a integer visited array.

Here is the source code for the BFS Traversal using Java
 

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
    Queue<Integer> queue;

    public BFS() {
        // TODO Auto-generated constructor stub
        queue = new LinkedList<>();

    }

    void bfs(int[][] adjacencyMatrix, int source) {

        int numberOfNodes = adjacencyMatrix[source].length;

        int visited[] = new int[numberOfNodes];

        int i, element;

        queue.add(source);

        // checking the queue is empty or not
        while (!queue.isEmpty()) {

            // removing the vertex from queue otherwise it will be processed
            // again
            element = queue.remove();
            i = element;

            System.out.print(i + "\t");
            while (i < numberOfNodes) {

                // checking there is an edge between two vertex and the vertex
                // has been already visited
                if (adjacencyMatrix[element][i] == 1 && visited[i] == 0) {
                    // adding the vertex to the queue
                    queue.add(i);

                    // Marking the vertex visited
                    visited[i] = 1;

                }

                i++;
            }
        }
    }

    public static void main(String[] args) {
       // graph representation in adjacency matrix
        int[][] adjacencyMatrix = { { 0, 1, 0, 1 }, { 0, 0, 1, 0 },
                { 0, 1, 0, 1 }, { 0, 0, 0, 1 } };

        BFS bfs = new BFS();

        System.out.println("BFS traversal");

        bfs.bfs(adjacencyMatrix, 0);

    }
}

Output:

BFS traversal
0    1    3    2 


Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.