Skip to content

Instantly share code, notes, and snippets.

@larsaars
Last active October 27, 2020 13:48
Show Gist options
  • Save larsaars/8d9c0a907161d95633096bd2bc8e31d7 to your computer and use it in GitHub Desktop.
Save larsaars/8d9c0a907161d95633096bd2bc8e31d7 to your computer and use it in GitHub Desktop.
Uniformed Search for a graph: BFS (Breadth First Search) and DFS (Depth First Search) in Java
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
public class BFS_DFS {
public static void main(String[] args) {
//prepare some nodes
char[] alphabet = ("abcdefghijklmnopqrstuvwxyz").toCharArray();
Node[] ns = new Node[alphabet.length];
for(int i = 0; i < alphabet.length; i++)
ns[i] = new Node(alphabet[i]);
/*connect the nodes somehow (add children to each node)
like this:
ns[0].cs(ns[1], ns[2], ns[3]);
ns[1].cs(ns[12], ns[25]);
*/
ns[0].cs(ns[1], ns[2], ns[3]);
ns[1].cs(ns[12], ns[25]);
//print out result for dfs and bfs (goal and start node can also be re-defined)
//the reset of the nodes before / after each search is necessary, since else all nodes are still marked as discovered
long dfsStart = System.nanoTime();
Node[] dfs = dfs(ns[0], ns[ns.length - 1]);
long dfsEnd = System.nanoTime();
resetNodes(ns);
long bfsStart = System.nanoTime();
Node[] bfs = bfs(ns[0], ns[ns.length - 1]);
long bfsEnd = System.nanoTime();
resetNodes(ns);
System.out.printf("\nDFS: %dns; p=%s", dfsEnd - dfsStart, dfs == null ? "Failure" : nodeArrToString(dfs));
System.out.printf("\nBFS: %dns; p=%s", bfsEnd - bfsStart, bfs == null ? "Failure" : nodeArrToString(bfs));
}
public static void resetNodes(Node[] allNodes) {
for(Node n : allNodes)
n.discovered = false;
}
public static Node[] dfs(Node s, Node g) {
if(s.equals(g))
return new Node[]{s};
LinkedList<Node[]> L = new LinkedList<>();
s.discovered = true;
L.add(new Node[]{s});
while(L.size() > 0) {
Node[] p = L.get(0);
Node u = p[p.length - 1];
L.remove(0);
for(Node v : u.children) {
if(v.equals(g))
return path(p, v);
else if(!v.discovered) {
v.discovered = true;
L.add(0, path(p, v));
}
}
}
return null;
}
public static Node[] bfs(Node s, Node g) {
if(s.equals(g))
return new Node[]{s};
LinkedList<Node[]> L = new LinkedList<>();
s.discovered = true;
L.add(new Node[]{s});
while(L.size() > 0) {
Node[] p = L.get(0);
Node u = p[p.length - 1];
L.remove(0);
for(Node v : u.children) {
if(v.equals(g))
return path(p, v);
else if(!v.discovered) {
v.discovered = true;
L.add(path(p, v));
}
}
}
return null;
}
private static Node[] path(Node[] base, Node newNode) {
Node[] newInstance = new Node[base.length + 1];
System.arraycopy(base, 0, newInstance, 0, base.length);
newInstance[base.length] = newNode;
return newInstance;
}
private static String nodeArrToString(Node[] path) {
StringBuilder o = new StringBuilder();
for(int i = 0; i < path.length; i++) {
if(i != 0)
o.append(", ");
o.append(path[i].id);
}
return o.toString();
}
public static class Node {
public boolean discovered = false;
public LinkedList<Node> children = new LinkedList<>();
public final char id;
public Node(char id0) {
id = id0;
}
//adds child nodes
public void cs(Node... children0) {
children.addAll(Arrays.asList(children0));
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) return false;
Node node = (Node) o;
return id == node.id;
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment