Breadth-First Search

The algorithm likes to stay as close as possible to the starting point. It visits all the vertices adjacent to the starting vertex, and only then goes further afield. This kind of search is implemented using a queue instead of a stack.

RULE 1

Visit the next unvisited vertex (if there is one) that’s adjacent to the current vertex, mark it, and insert it into the queue.

RULE 2

If you can’t carry out Rule 1 because there are no more unvisited vertices, remove a vertex from the queue (if possible) and make it the current vertex.

RULE 3

If you can’t carry out Rule 2 because the queue is empty, you’re done.

Event	Queue (Front to Rear)
Visit A
Visit B	B
Visit C	BC
Visit D	BCD
Visit E	BCDE
Remove B	CDE
Visit F	CDEF
Remove C	DEF
Remove D	EF
Visit G	EFG
Remove E	FG
Remove F	G
Visit H	GH
Remove G	H
Visit I	HI
Remove H	I
Remove I
Done

At each moment, the queue contains the vertices that have been visited but whose neighbors have not yet been fully explored. (Contrast this breadth-first search with the depth-first search, where the contents of the stack is the route you took from the starting point to the current vertex.) The nodes are visited in the order ABCDEFGHI.

//****************************************************************

//* Copyright (c) 2015 . All Rights Reserved.

//****************************************************************

package com.ds.graph;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

class Vertex {

    public char label; // label (e.g. ‘A’)

    public boolean wasVisited;

    public Vertex(final char label) // constructor

    {

        this.label = label;

        this.wasVisited = false;

    }

}

public class Graph {

    private static final int MAX_VERTEX = 20;

    private int[][] adjacencyMatrix;

    private Vertex[] vertexList;

    private int noOfVertex;

    public Graph() {

        this.vertexList = new Vertex[MAX_VERTEX];

        this.noOfVertex = 0;

        this.adjacencyMatrix = new int[MAX_VERTEX][MAX_VERTEX];

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

            for (int j = 0; j < MAX_VERTEX; j++) {

                this.adjacencyMatrix[i][j] = 0;

            }

        }

    }

    public void bfs() // breadth-first search

    {

        final Queue<Integer> theQueue = new LinkedList<Integer>();

        // begin at vertex 0

        theQueue.add(0); // insert at tail

        this.vertexList[0].wasVisited = true; // mark it

        displayVertex(0); // display it

        int v2;

        while (!theQueue.isEmpty()) // until queue empty,

        {

            final int v1 = theQueue.remove(); // remove vertex at head

            // until it has no unvisited neighbors

            while ((v2 = getVisitedColumnByRowInAdjacencyMatrix(v1)) != -1) { // get

                                                                              // one,

                displayVertex(v2); // display it

                markVisited(v2); // mark it

                theQueue.add(v2); // insert it

            } // end while(unvisited neighbors)

        } // end while(queue not empty)

          // queue is empty, so we’re done

        markAllUnVisited();

    } // end bfs()

    private void markAllUnVisited() {

        for (int i = 0; i < this.noOfVertex; i++) {

            markUnvisited(i);

        }

    }

    private void markUnvisited(final int i) {

        this.vertexList[i].wasVisited = false;

    }

    private void markVisited(final int wasVisited) {

        this.vertexList[wasVisited].wasVisited = true;

    }

    private int getVisitedColumnByRowInAdjacencyMatrix(final Integer rowPosition) {

        for (int column = 0; column < this.noOfVertex; column++) {

            if (checkForVisited(rowPosition, column)) {

                return column;

            }

        }

        return -1;

    }

    private boolean checkForVisited(final Integer rowPosition,

            final int columnNo) {

        return this.adjacencyMatrix[rowPosition][columnNo] == 1

               && this.vertexList[columnNo].wasVisited == false;

    }

    private void addEdge(final int i, final int j) {

        this.adjacencyMatrix[i][j] = 1;

        this.adjacencyMatrix[j][i] = 1;

    }

    private void addVertex(final char label) {

        this.vertexList[this.noOfVertex++] = new Vertex(label);

    }

    public void displayVertex(final int value) {

        System.out.print(this.vertexList[value].label);

    }

    public static void main(final String[] args) {

        final Graph graph = new Graph();

        graph.addVertex('A');// 0

        graph.addVertex('B');// 1

        graph.addVertex('C');// 2

        graph.addVertex('D');// 3

        graph.addVertex('E');// 4

        graph.addVertex('F');// 5

        graph.addEdge(0, 1);

        graph.addEdge(1, 2);

        graph.addEdge(0, 3);

        graph.addEdge(3, 4);

        graph.addEdge(1, 5);

        System.out.print("Visit BFS: ");

        graph.bfs();

        System.out.println();

        

    }

}

Kindly provide your valuable feedback in comment box.