Breadth First Search (BFS) in Java – Code

Long time ago, I had to implement BFS in Java as a part of exercise at the university. BFS, like Depth First Search (DFS), is a search algorithm for graphs and trees. They have uses in route planing(google-maps, navigation devices etc.) and in many other applications. You can read about some use cases and DFS vs. BFS comparisons here. For detailed explanation of the algorithms check this video.  Feel free to use the code as you wish.

The fist class in just an graph-edge information holder.

	/**
	 * @author Dzenan Hamzic
	 *
	 * Additional Class to encapsulate all edge information
	 */
	private class EdgeInfo {
		private GeographicPoint from;
		private GeographicPoint to;

		public EdgeInfo(GeographicPoint from, GeographicPoint to, String roadName, String roadType, double length) {
			this.from = from;
			this.to= to;
		}

		public GeographicPoint getFrom() {
			return from;
		}

		public void setFrom(GeographicPoint from) {
			this.from = from;
		}

		public GeographicPoint getTo() {
			return to;
		}

		public void setTo(GeographicPoint to) {
			this.to = to;
		}
	}

The graph structure(nodes and edges) are saved in the following DS.

// data structure to hold all graph objects
// 1. level keys -> vertice ID -> list of neighbours
// 2. level keys -> neighbour ID -> with edgeInfo
Map<GeographicPoint, List<EdgeInfo>> graphObjects;

Below is the BFS Java implementation.

public List<GeographicPoint> bfs(GeographicPoint start, 
			 					     GeographicPoint goal, Consumer<GeographicPoint> nodeSearched)
	{
		
		// Hook for visualization.  See writeup.
		//nodeSearched.accept(next.getLocation());
		
		Queue<GeographicPoint> queue = new LinkedList<>(); 
		Set<GeographicPoint> visited = new HashSet<>();
		Map<GeographicPoint, GeographicPoint> parentMap = new HashMap<>();
		
		// add start node to queue
		// set start node as visited
		queue.add(start);
		visited.add(start);
		
		// while queue is not empty
		while(!queue.isEmpty()){
			// 1. take first from queue
			// 2 if start == end finished=true
			// 3. check for any neghbours
			GeographicPoint current = queue.poll();
			if(current.equals(goal)) return recostructPath(start, goal, parentMap);
			if(graphObjects.get(current) == null) break;
			
			Iterator<MapEdge> neighbourListIter = graphObjects.get(current).iterator();
			// foreach neighbour n not in visited set
			while (neighbourListIter.hasNext()) {
				GeographicPoint neighbourID = neighbourListIter.next().getTo();
				// check if already visited
				if(visited.contains(neighbourID))
					continue;
				
				visited.add(neighbourID);
				parentMap.put(neighbourID, current);
				queue.add(neighbourID);
			}
		}
		// this point is reached if no path was found
		return null;
	}

and the method that reconstructs the found path…

/**
	 * @param start node
	 * @param goal node
	 * @param parentMap HashMap of node parents
	 * @return
	 */
	private List<GeographicPoint> recostructPath(GeographicPoint start, GeographicPoint goal,
			Map<GeographicPoint, GeographicPoint> parentMap) {
		// construct output list
		LinkedList<GeographicPoint> path = new LinkedList<>();
		GeographicPoint currNode = goal;
		while(!currNode.equals(start)){
			path.addFirst(currNode);
			currNode = parentMap.get(currNode);
		}
		path.addFirst(start);
		return path;
	}

Enjoy the source and have fun…