Skip to content

Instantly share code, notes, and snippets.

@gennad
Created January 23, 2011 09:14
Show Gist options
  • Save gennad/791932 to your computer and use it in GitHub Desktop.
Save gennad/791932 to your computer and use it in GitHub Desktop.
Breadth-first search and depth-first search Java implementation
Class Main {
public void bfs()
{
// BFS uses Queue data structure
Queue queue = new LinkedList();
queue.add(this.rootNode);
printNode(this.rootNode);
rootNode.visited = true;
while(!queue.isEmpty()) {
Node node = (Node)queue.remove();
Node child=null;
while((child=getUnvisitedChildNode(node))!=null) {
child.visited=true;
printNode(child);
queue.add(child);
}
}
// Clear visited property of nodes
clearNodes();
}
public void dfs() {
// DFS uses Stack data structure
Stack stack = new Stack();
stack.push(this.rootNode);
rootNode.visited=true;
printNode(rootNode);
while(!stack.isEmpty()) {
Node node = (Node)s.peek();
Node child = getUnvisitedChildNode(n);
if(child != null) {
child.visited = true;
printNode(child);
s.push(child);
}
else {
s.pop();
}
}
// Clear visited property of nodes
clearNodes();
}
}
Class Node {
Char data;
Public Node(char c) {
this.data=c;
}
}
@nicksc423
Copy link

I realize this is a little pedantic, but these are Breadth and Depth first traversals not searches. They simply visit all nodes, not search for a specific node/value.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment