Breadth First Search of a graph using Adjacency List

Breadth First Search of a graph using Adjacency List.



This post is an implementation of a breadth first search of a Graph using Adjacency List in Java. In this, we go level by level and add all the elements onto the queue and maintain a array of boolean values to mark them as visited. The boolean array is required just to make sure we do not get into a circular graph.

As said, the algorithms uses the FIFO, thus queue is required as a data structure in this implementation.

More details on it coming soon...

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Scanner;

@SuppressWarnings("unchecked")

class BreadthFirstSearch {

private int v;

private LinkedList<Integer> adj[];

public BreadthFirstSearch(int v) {

this.v = v;

adj = new LinkedList[v];

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

adj[i] = new LinkedList();

}

}

void addEdge(int v, int w) {

adj[v].add(w);

}

void breadthFirstSearch(int s) {

boolean[] visited = new boolean[v];

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

// Adding the first element to the queue

visited[s] = true;

queue.add(s);

// Adding its adjacent elements to the queue

while (queue.size() != 0) {

s = queue.poll();

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

Iterator<Integer> iterator = adj[s].listIterator();

while (iterator.hasNext()) {

int next = (int)iterator.next();

if(!visited[next]) {

visited[next] = true;

queue.add(next);

}

}

}

}

public static void main(String[] args) {

BreadthFirstSearch bfs = new BreadthFirstSearch(4);

bfs.addEdge(0, 1);

bfs.addEdge(0, 2);

bfs.addEdge(1, 2);

bfs.addEdge(2, 0);

bfs.addEdge(2, 3);

bfs.addEdge(3, 3);

System.out.print("BreadthFirstSearch starting at vertex 1: ");

bfs.breadthFirstSearch(1);

System.out.println();

}

}

Please leave your comments for any suggestion or query.