Following java program implements BFS algorithm . The Graph for input/output is below
In order to traverse graph we need following data structures.
- Vertex object to store label and visited(true/false) .
- Adjacency Matrix to hold links between given vertices.
- Vertex list to keep hold given vertex.
- Queue to make traversal info tracked.
package com.abhishek.graph;
import java.util.PriorityQueue;
import java.util.Queue;
public class BFS {
public static void main(String ... args){
GraphBFS g = new GraphBFS();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addVertex('E');
g.addVertex('F');
g.addVertex('G');
g.addVertex('H');
g.addEdge(0,1);g.addEdge(0,5);g.addEdge(0,6);g.addEdge(0,3);g.addEdge(1,4);g.addEdge(1,5);g.addEdge(2,7);g.addEdge(3,5);
g.addEdge(4, 6);g.addEdge(2, 5);
g.bfs();
}
}
class VertexBFS {
public char label;
public boolean visited;
public VertexBFS(char pLabel){
label = pLabel;
visited = false;
}
}
class GraphBFS{
public VertexBFS vertexList[];
public int maxVertices = 20;
public int vertexCount;
public Queue<Integer> theQueue;
public int adjM[][];
public GraphBFS(){
vertexList = new VertexBFS[maxVertices];
vertexCount =0;
theQueue = new PriorityQueue<Integer>();
adjM = new int[maxVertices][maxVertices];
for(int i=0;i<maxVertices;i++)
for(int j=0;j<maxVertices;j++)
adjM[i][j]=0;
}
public void addVertex(char pLabel){
vertexList[vertexCount++]= new VertexBFS(pLabel);
}
public void addEdge(int start,int end){
adjM[start][end]=1;
adjM[end][start]=1;
}
public void displayVertex(int v){
System.out.print(vertexList[v].label+" ");
}
public void bfs(){
vertexList[0].visited=true;
displayVertex(0);
theQueue.add(0);
int v2;
while(!theQueue.isEmpty()){
int v1 = theQueue.remove();
while((v2=getUnVisitedVertex(v1))!=-1){
vertexList[v2].visited=true;
displayVertex(v2);
theQueue.add(v2);
}
}
for(int i=0;i<vertexCount;i++){
vertexList[i].visited=false;
}
}
public int getUnVisitedVertex(int v){
for(int i=0;i<vertexCount;i++){
if(adjM[v][i]==1&&vertexList[i].visited==false)
return i;
}
return -1;
}
}
The output will be
A B D F G E C H
To understand BFS/DFS better follow below video . A 10 minute video with very good explanation
Reference for code/theory used
Data Structures and Algorithms Made easy in Java by Narasimha Karumanchi
