Breadth First Traversal or BFS for a Graph
Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth First Traversal of the following graph is 2, 0, 3, 1.
First of all make a Queue class:-
class Queue{
public int SIZE=20,front,rear;
public int q[];
public Queue(){
q=new int[SIZE];
front=0;
rear=-1;
}
public void insert(int x){
if(rear==SIZE-1){//if queue is full
rear=-1;
}
q[++rear]=x;
}
public int remove(){
int temp=q[front++];
if(front==SIZE){
front=0;
}
return temp;
}
public boolean isEmpty(){
return (rear+1==front||front+SIZE-1==rear);
}
public void display(){
System.out.println("Queue Content:");
for(int i=front;i<rear;i++){
System.out.print("\t"+q[i]);
}
}
}Now Make the Vertex class:-
class Vertex{
public char node;
public boolean wasvisited;
public Vertex(char n){
node=n;
wasvisited=false;
}
}Now Make the bfs_graph class:-
class bfs_graph{
public int adMatrix[][];
public int MAX_NODE=20;
public Vertex vertexList[];
public int nNodes;
public Queue queue;
public bfs_graph(){
adMatrix= new int[MAX_NODE][MAX_NODE];
vertexList=new Vertex[MAX_NODE];
queue=new Queue();
nNodes=0;
for(int i=0;i<MAX_NODE;i++){
for(int j=0;j<MAX_NODE;j++){
adMatrix[i][j]=0;
}
}
}
public void addNode(char n){
vertexList[nNodes++]=new Vertex(n);
}
public void addEdge(int start,int end){
adMatrix[start][end]=1;
adMatrix[end][start]=1;
}
public void displayNode(int n){
System.out.print(vertexList[n].node+"->");
}
public int getAdjUnvidited(int v){
for(int i=0;i<nNodes;i++){
if(adMatrix[v][i]==1 && vertexList[i].wasvisited==false){
return i;
}
}
return -1;
}
public void bfs(){
vertexList[0].wasvisited=true;
displayNode(0);
queue.insert(0);
int v2;
while(!queue.isEmpty()){
int v1=queue.remove();
while((v2=getAdjUnvidited(v1))!= -1){
displayNode(v2);
queue.insert(v2);
vertexList[v2].wasvisited=true;
//queue.display();
}
}
for(int i=0;i<nNodes;i++){
vertexList[i].wasvisited=false;
}
}
public void displayMatrix(){
for(int i=0;i<nNodes;i++){
for(int j=0;j<nNodes;j++){
System.out.print("\t"+adMatrix[i][j]);
}
System.out.println("");
}
}
}
Now write the class contains the main function:-
class bfsApp{
public static void main(String[] args){
bfs_graph g= new bfs_graph();
g.addNode('A');
g.addNode('B');
g.addNode('C');
g.addNode('D');
g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);
g.displayMatrix();
System.out.println("A visits: ");
g.bfs();
}
}
Full Code:-
import java.util.*;
class Queue{
public int SIZE=20,front,rear;
public int q[];
public Queue(){
q=new int[SIZE];
front=0;
rear=-1;
}
public void insert(int x){
if(rear==SIZE-1){//if queue is full
rear=-1;
}
q[++rear]=x;
}
public int remove(){
int temp=q[front++];
if(front==SIZE){
front=0;
}
return temp;
}
public boolean isEmpty(){
return (rear+1==front||front+SIZE-1==rear);
}
public void display(){
System.out.println("Queue Content:");
for(int i=front;i<rear;i++){
System.out.print("\t"+q[i]);
}
}
}
class Vertex{
public char node;
public boolean wasvisited;
public Vertex(char n){
node=n;
wasvisited=false;
}
}
class bfs_graph{
public int adMatrix[][];
public int MAX_NODE=20;
public Vertex vertexList[];
public int nNodes;
public Queue queue;
public bfs_graph(){
adMatrix= new int[MAX_NODE][MAX_NODE];
vertexList=new Vertex[MAX_NODE];
queue=new Queue();
nNodes=0;
for(int i=0;i<MAX_NODE;i++){
for(int j=0;j<MAX_NODE;j++){
adMatrix[i][j]=0;
}
}
}
public void addNode(char n){
vertexList[nNodes++]=new Vertex(n);
}
public void addEdge(int start,int end){
adMatrix[start][end]=1;
adMatrix[end][start]=1;
}
public void displayNode(int n){
System.out.print(vertexList[n].node+"->");
}
public int getAdjUnvidited(int v){
for(int i=0;i<nNodes;i++){
if(adMatrix[v][i]==1 && vertexList[i].wasvisited==false){
return i;
}
}
return -1;
}
public void bfs(){
vertexList[0].wasvisited=true;
displayNode(0);
queue.insert(0);
int v2;
while(!queue.isEmpty()){
int v1=queue.remove();
while((v2=getAdjUnvidited(v1))!= -1){
displayNode(v2);
queue.insert(v2);
vertexList[v2].wasvisited=true;
//queue.display();
}
}
for(int i=0;i<nNodes;i++){
vertexList[i].wasvisited=false;
}
}
public void displayMatrix(){
for(int i=0;i<nNodes;i++){
for(int j=0;j<nNodes;j++){
System.out.print("\t"+adMatrix[i][j]);
}
System.out.println("");
}
}
}
class bfsApp{
public static void main(String[] args){
bfs_graph g= new bfs_graph();
g.addNode('A');g.addNode('B');g.displayMatrix();
g.addNode('C');
g.addNode('D');
g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);
System.out.println("A visits: ");
g.bfs();
}
}
.png)
Leave Your Comments here !!!