Skip to content

Instantly share code, notes, and snippets.

@dnavas77
Created January 23, 2020 00:19
Show Gist options
  • Save dnavas77/01436098eefa3c06b56c43ac5ee3de46 to your computer and use it in GitHub Desktop.
Save dnavas77/01436098eefa3c06b56c43ac5ee3de46 to your computer and use it in GitHub Desktop.
//DFS
public boolean hasPathDFS(int source, int destination) {
HashSet<Integer> visited = new HashSet<>();
return hasPathDFS(getNode(source), getNode(destination), visited);
}
private boolean hasPathDFS(Node source, Node destination, HashSet<Integer> visited) {
if (visited.contains(source.id)) {
return false;
}
visited.add(source.id);
if (source == destination) {
return true;
}
for (Node child : source.adjacent) {
if (hasPathDFS(child, destination, visited)) {
return true;
}
}
return false;
}
// BFS
public boolean hasPathBFS(int source, int destination) {
return hasPathBFS(getNode(source), getNode(destination));
}
private boolean hasPathBFS(Node source, Node destination) {
LinkedList<Node> nextToVisit = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
nextToVisit.add(source);
while (!nextToVisit.isEmpty()) {
Node node = nextToVisit.remove();
if (node == destination) {
return true;
}
if (visited.contains(node.id)) {
continue;
}
for (Node child : node.adjacent) {
nextToVisit.add(child);
}
}
return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment