CC-3 : Implement Bi-Directional/ Undirectional graph Breadth First BFS traversal.

Description:

Create and test a Bi-directional/ undirectional Graph BFS Traversal program.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphBfs gph=new GraphBfs(5); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.addEdge(0, 4); gph.addEdge(1, 2); gph.addEdge(2, 3); gph.addEdge(3, 4); gph.displayGraph(); gph.bfsTraversal(0); System.out.println("Bfs Traversal: "+ gph.bfsTraversal);	vertex 0->1->2->3->4 vertex 1->0->2 vertex 2->0->1->3 vertex 3->0->2->4 vertex 4->0->3 Bfs Traversal: 0 1 2 3 4

Pseudocode:

Initialize an int variable named visited to store information whether a particular vertice in the graph has been visited.

Initialize a String variable named bfsTraversal to hold output of BFS traversal of the graph.

Method bfsTraversal(int vertex):

Set visited[vertex] to 0.

Initialize a Queue variable named queue to hold vertexes of the graph to be processed.

While queue size is not 0:

Remove top vertex from queue and store it in a variable named vertex.

Add vertex to bfsTraveral String as it has been traversed now.

Extract vertices connected to vertex from the adjacencyList.

Iterate through vertices connected to current vertex using iterator:

Set variable adjacentNode to point to current connected vertex.

If visited[adjacentNode] is not 1, then:

Set visited[adjacentNode] to 1.

Add adjacentNode to queue.

Code:

<code>
public class GraphBfs {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String bfsTraversal=new String();
 
 public void bfsTraversal(int vertex) {
	 visited[vertex]=1;
	 LinkedList<Integer> queue=new LinkedList<Integer>();
	 queue.add(vertex);
	 while (queue.size() !=0) {
		 vertex=queue.remove();
		 bfsTraversal+= vertex + " ";
		 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
		 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 visited[adjacentNode]=1;
			 queue.add(adjacentNode);			
		 }
		 }
	 }	
 } 
 }
 </code>

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;

public class GraphBfs {

 private int vertices;
  private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String bfsTraversal=new String();
 
 public GraphBfs(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public void bfsTraversal(int vertex) {
	 visited[vertex]=1;
	 LinkedList queue=new LinkedList();
	 queue.add(vertex);
	 while (queue.size() !=0) {
		 vertex=queue.remove();
		 bfsTraversal+= vertex + " ";
		 Iterator itr=adjacencyLists.get(vertex).iterator();
		 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 visited[adjacentNode]=1;
			 queue.add(adjacentNode);			
		 }
		 }
	 }
	
 } 
 
 public void displayGraph() {
	 for (int iIdx=0;iIdx< adjacencyLists.size();iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx);
		 for (int jIdx=0;jIdx< adjacencyLists.get(iIdx).size();jIdx++) {
			 System.out.print("->"+adjacencyLists.get(iIdx).get(jIdx));
		 }
	 }
 }

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	String retVal;
	try {
	GraphBfs gph=new GraphBfs(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 4);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	gph.bfsTraversal(0);
	System.out.println();
	System.out.println("Bfs Traversal: "+ gph.bfsTraversal);
	
	
	gph=new GraphBfs(7);
	gph.addEdge(1, 2);
	gph.addEdge(1, 5);
	gph.addEdge(2, 5);
	gph.addEdge(2, 3);
	gph.addEdge(5, 3);
	gph.addEdge(5, 4);
	gph.addEdge(3, 4);
	gph.displayGraph();
	gph.bfsTraversal(1);
	System.out.println();
	System.out.println("Bfs Traversal: "+ gph.bfsTraversal);
	
	
	gph=new GraphBfs(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(1, 2);
	gph.addEdge(2, 4);
	gph.displayGraph();
	gph.bfsTraversal(0);
	System.out.println();
	System.out.println("Bfs Traversal: "+ gph.bfsTraversal);
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}