Graph DFS algorithm is so similar to DFS in Trees. Two differences:
– a graph node can have more than 2 children
– a node can be visited multiple times, hence we must mark the visited node to prevent repeated processing.
Text description of the algorithm:
– predefine a list to store all visited nodes
– start DFS from the root node, pass the list of visited nodes as an argument
– if the current node has been already visited, return from the recursive function
– run a DFS on all child nodes
Time complexity: O(n).
Space complexity: O(m), where m – maximal depth of the graph.
public class ImplementGraphDFS {
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 searched = new ArrayList<String>();
return searchDFS(startName, searchable, searched);
}
private static String searchDFS(String currentName, String searchable,
ArrayList<String> searched) {
if (searched.contains(currentName)) {
return null;
}
searched.add(currentName);
var nodes = graph.get(currentName);
if (nodes.contains(searchable)) {
return searchable;
}
for (var node : nodes) {
var result = searchDFS(node, searchable, searched);
if (result != null) {
return result;
}
}
return null;
}
public static void main(String[] args) {
System.out.println(search("you", "jonny"));
}
}