Breadth First Search Java Example

• 1) Overview
• 2) Breadth First Search (BFS) Algorithm
  • 2.a) Tree
    • Flow Diagram
    • Java Code Example
  • 2.b) Graph
    • Flow Diagram
    • Java Code Example
• 3) Conclusion

1) Overview

Article explore Breadth First Search (BFS) Algorithm on Tree and Graph with flow diagrams and Java code examples.

Before we understand Graph/Tree search algorithms, its very important to understand difference between visit and explore.

2) Breadth First Search (BFS) Algorithm

Idea of BFS is to start with one node and explore it completely before moving to its children. To maintain the sequence of visiting and exploring the nodes it utilizes Queue data structure.

Read more about Visit and Explore.

Implementation of BFS and Depth First Search (DFS) are exactly the same with one difference. BFS works on Queue where DFS on Stack.

Let's understand BFS Tree and Graph implementation, step by step.

2.a) Tree

Following are the steps, how it works on the Tree.

1. Create a Queue
2. Add root node to the Queue to start with
3. Run a loop until Queue is empty.
   • Each iteration
     • get a node from Queue and compare with search value
     • If matched return current node and end the loop.
     • otherwise add children of current node to Queue.
4. Repeat Steps 3 to 4.

Flow Diagram

Following is the flow diagram to make it easy to understand.

Java Code Example

Let's create Tree representation first.

package net.kheri;  import java.util.LinkedList; import java.util.List;  public class Tree<T> { 	private T value; 	private List<Tree<T>> chidren;  	public Tree(T value) { 		this.value = value; 		this.chidren = new LinkedList<Tree<T>>(); 	}  	public Tree<T> addChild(T child) { 		Tree<T> childNode = new Tree<T>(child); 		this.chidren.add(childNode); 		return childNode; 	}  	public T getValue() { 		return this.value; 	} 	 	public List<Tree<T>> getChildren(){ 		return this.chidren; 	}  	@Override 	public String toString() { 		return String.valueOf(this.value); 	} }        

Search method

Make sure to refer Java comments, explaining each step.

package net.kheri;  import java.util.ArrayDeque; import java.util.Optional; import java.util.Queue;  public class BreathFirstSearch<T> {  	public Optional<Tree<T>> search(Tree<T> startNode, Integer searchValue) {  		// STEP 1 : create queue to maintain the next node to be explored. 		Queue<Tree<T>> queue = new ArrayDeque<Tree<T>>();  		// STEP 2: add starting node to list to start the search. 		queue.add(startNode);  		// STEP 3: Iterate until queue is empty 		int counter =0; 		while (!queue.isEmpty()) { 			System.out.println("Iteration "+(++counter)+" Queue="+queue);  			// STEP 3.a: get the node from the Queue 			Tree<T> currentNode = queue.remove(); 			System.out.println("Get "+ currentNode);  			if (currentNode.getValue().equals(searchValue)) { 				// STEP 3.b: if current node matched with search value, return it. 				return Optional.of(currentNode); 			} else { 				// STEP 3.c: add current node's children to queue, search continues... 				queue.addAll(currentNode.getChildren()); 			} 		} 		// STEP 4: Queue is empty that means searchValue doesn't exist in the tree. 		return Optional.empty(); 	} }        

Let's take following example of tree to run a test on the program where we try to find node 7.

package net.kheri;  import java.util.Optional;  public class BreathFirstTreeSearchTest {  	public static void main(String[] args) {  		BreathFirstSearch<Integer> searchHelper = new BreathFirstSearch<Integer>(); 		 		Tree<Integer> rootNode = createTree(); 		 		Integer searchValue = 7;  		Optional<Tree<Integer>> result = searchHelper.search(rootNode, searchValue);  		if (result.isPresent()) { 			System.out.println("Search completed successfully [" + result.get() + "]"); 		} else { 			System.out.println("Node [" + searchValue + "] is not found"); 		}  	}  	private static Tree<Integer> createTree() { 		// Create Tree 		Tree<Integer> rootNode = new Tree<Integer>(1); 		 		Tree<Integer> child1 = rootNode.addChild(2); 		child1.addChild(4); 		child1.addChild(5); 		 		Tree<Integer> child2 = rootNode.addChild(3); 		child2.addChild(6); 		child2.addChild(7); 		return rootNode; 	} }

Console Output:

Iteration 1 Queue=[1] Get 1 Iteration 2 Queue=[2, 3] Get 2 Iteration 3 Queue=[3, 4, 5] Get 3 Iteration 4 Queue=[4, 5, 6, 7] Get 4 Iteration 5 Queue=[5, 6, 7] Get 5 Iteration 6 Queue=[6, 7] Get 6 Iteration 7 Queue=[7] Get 7 Search completed successfully [7]        

2.b) Graph

Difference between Tree and Graph is that Graph can have cycles. Which adds a level of complexity. Now we have to remember what nodes we have already visited so we don't explore it again.

Following are the steps, how it works on the Graph.

1. Create a Queue
2. Add root node to the Queue to start with.
3. Create a Set to store already visited nodes.
4. Run a loop until Queue is empty.
   • Each iteration
     • Get a node from Queue
     • Add current node to already visited nodes Set.
     • Compare current node with search value.
       • If matched return current node and end the loop.
       • otherwise add children (not already part of Queue AND not visited yet) of current node to Queue.
5. Repeat Steps 4 to 5.

Flow Diagram

Java Code Example

Let's create Graph representation first.

package net.kheri;  import java.util.LinkedHashSet; import java.util.Set;  public class Graph<T> { 	private T value; 	private Set<Graph<T>> neighbors; 	 	public Graph(T value) { 		this.value = value; 		this.neighbors = new LinkedHashSet<Graph<T>>(); 	}  	public Graph<T> connect(Graph<T> neighbor) { 		if(this==neighbor) { 			throw new IllegalArgumentException("Can't connect to itself"); 		} 		this.neighbors.add(neighbor); 		return neighbor; 	} 	 	public T getValue() { 		return value; 	} 	public Set<Graph<T>> getNeighbors() { 		return neighbors; 	} 	 	@Override 	public String toString() { 		return String.valueOf(this.value); 	} }        

Search method

Make sure to refer Java comments, explaining each step.

public class BreathFirstSearch<T> { 	 	public Optional<Graph<T>> search(Graph<T> startNode, Integer searchValue) {  		// STEP 1 : create queue to maintain the next node to be explored. 		Queue<Graph<T>> queue = new ArrayDeque<>(); 		 		// STEP 2: add starting node to list to start the search. 		queue.add(startNode);  		// STEP 3: create a set for already visited nodes 		Set<Graph<T>> alreadyVisitedNodes = new HashSet<>();   		// STEP 4: Iterate until queue is empty 		int counter =0; 		while (!queue.isEmpty()) { 			System.out.println("Iteration "+(++counter)+" Queue="+queue); 			// STEP 4.a: get the node from the Queue 			Graph<T> currentNode = queue.remove(); 			System.out.println("Get "+ currentNode); 			 			// STEP 4.b : add current node to already visited set 			alreadyVisitedNodes.add(currentNode); 			 			if (currentNode.getValue().equals(searchValue)) { 				// STEP 4.c: if current node matched with search value, return it. 				return Optional.of(currentNode); 			} else { 				// STEP 4.d: add current node's children to queue, search continues... 				for(Graph<T> neighbor:currentNode.getNeighbors()) { 					if(!queue.contains(neighbor) && !alreadyVisitedNodes.contains(neighbor)) { 						queue.add(neighbor); 					} 				} 			} 		} 		//STEP 5: Queue is empty that means searchValue doesn't exist in the tree. 		return Optional.empty(); 	} }

Let's take following example of graph to run a test on the program where we try to find node 7.

package net.kheri;  import java.util.Optional;  public class BreathFirstGraphSearchTest {  	public static void main(String[] args) {  		BreathFirstSearch<Integer> searchHelper = new BreathFirstSearch<Integer>(); 		 		Graph<Integer> rootNode = createGraph(); 		 		Integer searchValue = 7;  		Optional<Graph<Integer>> result = searchHelper.search(rootNode, searchValue);  		if (result.isPresent()) { 			System.out.println("Search completed successfully [" + result.get() + "]"); 		} else { 			System.out.println("Node [" + searchValue + "] is not found"); 		}  	}  	private static Graph<Integer> createGraph() { 		// Create Graph 		Graph<Integer> rootNode = new Graph<Integer>(1); 		Graph<Integer> node2 = new Graph<Integer>(2); 		Graph<Integer> node3 = new Graph<Integer>(3); 		Graph<Integer> node6 = new Graph<Integer>(6); 		 		rootNode.connect(node2); 		rootNode.connect(node6); 		rootNode.connect(node3); 		 		node2.connect(new Graph<Integer>(4)); 		node2.connect(new Graph<Integer>(5)); 		node2.connect(node6); 		 		node3.connect(node6); 		node3.connect(new Graph<Integer>(7)); 		 		return rootNode; 	} }        

Console Output:

Iteration 1 Queue=[1] Get 1 Iteration 2 Queue=[2, 6, 3] Get 2 Iteration 3 Queue=[6, 3, 4, 5] Get 6 Iteration 4 Queue=[3, 4, 5] Get 3 Iteration 5 Queue=[4, 5, 7] Get 4 Iteration 6 Queue=[5, 7] Get 5 Iteration 7 Queue=[7] Get 7 Search completed successfully [7]        

3) Conclusion

In this article, we learned about the Breadth-First Search algorithm and how to implement it in Java, for both Tree and Graph.

If you have any question over the implementation, please drop a comment.
Any suggestions on content improvements are welcome.

Keep Learning…

References:

Wiki

• Author
• Recent Posts

I write about Java and related open source technologies. If you like my articles, press the blue icon to follow me on twitter.

copegorry1953.blogspot.com

Source: https://wahecode.com/breadth-first-search-bfs-algorithm-with-java-examples/

Share this post