BFS implementation in java using Adjacency Matrix for Graph traversal

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