The BFS algorithm in Graphs implies the following:
- predefine a list of visited nodes
- create a queue instance, put the starting node in the queue
- while a queue is not empty:
– poll the queue, take the head element
– if the head element has already been visited, continue the loop
– analyze the value of the retrieved node and mark it as visited
– put to the queue all child nodes - time complexity: O(n)
- space complexity: O(m), where m is the maximum graph width.
public class ImplementGraphBFS {
private static final Map<String, List<String>> graph = new HashMap<>();
static {
graph.put("you", List.of("alice", "bob", "claire"));
graph.put("bob", List.of("anuj", "peggy"));
graph.put("alice", List.of("peggy"));
graph.put("claire", List.of("thom", "jonny"));
graph.put("anuj", List.of());
graph.put("peggy", List.of());
graph.put("thom", List.of());
graph.put("jonny", List.of());
}
public static String search(String startName, String searchable) {
var queue = new LinkedList<>(graph.get(startName));
var searched = new ArrayList<String>();
while (!queue.isEmpty()) {
var person = queue.poll();
if (searched.contains(person)) {
continue;
}
if (person.equals(searchable)) {
return person;
} else {
searched.add(person);
queue.addAll(graph.get(person));
}
}
return null;
}
public static void main(String[] args) {
System.out.println(search("you", "jonny"));
}
}