Created
January 23, 2011 09:14
-
-
Save gennad/791932 to your computer and use it in GitHub Desktop.
Breadth-first search and depth-first search Java implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.