Breadth First Search – BFS

There are plethora of articles on the web explaining the breadth first search . But there aren’t implementations available especially in Java. Here is the java implementation of the breadth first search. Each vertex in the graph is represented by a struct Node.

	public class Node {

		public String data; // data element
		public boolean visited=false; // flag to track the already visited node
		public List adjacentNodes = new LinkedList(); // adjacency list

		public Node(String data){
			this.data = data;
		}

		public void addAdjacentNode(final Node node){
			adjacentNodes.add(node);
			node.adjacentNodes.add(this);
		}

	}

There are different ways to store graphs and the method used is this blog post is using adjacency list to store the neighboring vertices instead of adjacency matrix. You can read more about storing graphs here

the above shown Node is self-explanatory; data is the data element of the vertex, visited a boolean flag to track already visited node and the List as the adjacent list.

The breadth first search algo is very simple and is clearly explained in this article. Here goes the implementation

public class Graph {

	private List nodes = new ArrayList();

	public void breadthFirstTraversal(Node rootNode){

		Queue q = new LinkedList();
		q.add(rootNode);
		rootNode.visited=true;
		while(!q.isEmpty()){
			Node n = (Node)q.poll();
			System.out.print(n.data + " ");
			for(Node adj : n.adjacentNodes){
				if(!adj.visited){
					adj.visited=true;
					q.add(adj);
				}
			}
		}

	}

}

The graph class represent the graph of nodes with each node maintaining it’s own adjacent list; the breadth first search is one of the use cases of queue. the code is very simple and I guess there is no need for me to explain it, for some one who is not really familiar here goes the algorithm.

- enqueue the start node to a Queue
- make the start node as visited
- while queue is not empty
  - dequeue the node lets say u
  - print or whatever you want to
  - for every adjacent node v of u
      - if v is not already visited
          - mark v as visited
          - enqueue v to the Queue

You can easily test the graph using this test program (graph example straight from wikipedia)

	public static void main(String[] args) {

		Node frankfurt = new Node("frankfurt");
		Node mannheim = new Node("mannheim");
		Node wurzburg = new Node("wurzburg");
		Node stuttgard = new Node("stuttgard");
		Node kassel = new Node("kassel");
		Node karlsruhe = new Node("karlsruhe");
		Node erfurt = new Node("erfurt");
		Node numberg = new Node("numberg");
		Node augsburg = new Node("augsburg");
		Node munchen = new Node("munchen");

		Graph g = new Graph();

		g.nodes.add(frankfurt);
		g.nodes.add(mannheim);
		g.nodes.add(wurzburg);
		g.nodes.add(stuttgard);
		g.nodes.add(kassel);
		g.nodes.add(karlsruhe);
		g.nodes.add(erfurt);
		g.nodes.add(numberg);
		g.nodes.add(augsburg);
		g.nodes.add(munchen);

		frankfurt.addAdjacentNode(mannheim);
		frankfurt.addAdjacentNode(wurzburg);
		frankfurt.addAdjacentNode(kassel);

		mannheim.addAdjacentNode(karlsruhe);

		karlsruhe.addAdjacentNode(augsburg);

		augsburg.addAdjacentNode(munchen);

		munchen.addAdjacentNode(kassel);
		munchen.addAdjacentNode(numberg);

		wurzburg.addAdjacentNode(erfurt);
		wurzburg.addAdjacentNode(numberg);

		numberg.addAdjacentNode(stuttgard);

		g.breadthFirstTraversal(frankfurt);
	}

Next blog post would be for Depth First Search – DFS