BFS – Breadth-First Search

	public Node search(Node start, Predicate<Node> endPredicate)
	{
		//Check if the start node is the endPredicate
		if(endPredicate.test(start))
			return start;

		//The queue containing all the nodes we have to search for
		//We used ArrayDeque because it has the best performance of all queues.
		ArrayDeque<Node> nodeQueue = new ArrayDeque<>(start.adjacent());
		//Adjacent, definition from the handbook.pdf contain all neighbors.
		//That means, that we would search in a node which we already searched for at another position.
		//Because of the insertion and lookup time O(1) in both situations, we chose the HashSet.
		HashSet<Node> checkedNodes = new HashSet<>();

		//Repeat till we have no element in the queue left.
		while(nodeQueue.size() > 0) {
			Node currentNode = nodeQueue.removeFirst();
			if(endPredicate.test(currentNode))
				return currentNode;
			//The current node does not equal the predicate we
			//are searching for. Add all node's adjacent which we did not checked yet.
			currentNode.adjacent().stream().filter(node -> !checkedNodes.contains(node)).forEach(node -> {
				nodeQueue.addLast(node); //Add it to the queue
				checkedNodes.add(node); //Add it to the hasSet
			});
		}

		//We cant reach that state, but just in case return null.
		return null;
	}

 

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.