Skip to content

Instantly share code, notes, and snippets.

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();
rootNode.visited = true;
while(!queue.isEmpty()) {
Node node = (Node)queue.remove();
Node child=null;
while((child=getUnvisitedChildNode(node))!=null) {
// Clear visited property of nodes
public void dfs() {
// DFS uses Stack data structure
Stack stack = new Stack();
while(!stack.isEmpty()) {
Node node = (Node)s.peek();
Node child = getUnvisitedChildNode(n);
if(child != null) {
child.visited = true;
else {
// Clear visited property of nodes
Class Node {
Char data;
Public Node(char c) {;
Copy link

Very nice and clear code
However your dfs sometimes uses s for the variable stack and n for the variable node.


Copy link

Also, I noticed that you reference "visited" for node objects, but I don't see that defined in the node class.

Copy link

where are the methods printNode() and visited() defined? Or what type of object is rootNode?

Copy link

Missing some Code Lines...

Copy link

This is a copy of what you can find here:

Looks like the whole implementation can be downloaded from there.

Copy link

ghost commented Mar 3, 2014

The code's problem is that when the graph is disconnected, there will be nodes missing.

Copy link

dharam3 commented Jun 1, 2014

If your graph vertices are connected like this
A-->C-->B ( A to C and A to B)
B-->D ( B to D)
C-->B-->D( C to B and C to D)
D ( No outward connection)
E-->D ( E to D)

Please note that E is not reachable from any other vertices.

And if A is root Node, E will never be visited.

Copy link

Minor issue: getUnvisitedChildNode(node) instead of n.

Copy link

0xhmn commented Jul 3, 2016

Copy link

sjcuello commented Aug 2, 2016


Copy link

In DFS method, why not just use pop() instead of peek()?

Copy link

sameer commented Nov 30, 2016

What I find odd is that the code marks nodes visited without checking if they've already been visited...
If they've already been visited, shouldn't they be ignored?

Copy link

juanmf commented Feb 3, 2017

Nice implemetation.

you can avoid casting by using type parameters. Queue<Node> queue Stack<Node> stack

class Node {
        List<Node> children;
        boolean visited = false;
        Node getUnvisitedChildNode(){
                    .filter(n -> ! n.visited)

@dkonayuki its ok peek, since in DFS she needs to revisit nodes and ask for other children.

Copy link

Answer @dkonayuki,It would break the stack chain and without missing the right child node, if its use pop().

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