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;
}
}
@aviggiano
Copy link

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

Regards

@frankhanner
Copy link

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

@dtturcotte
Copy link

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

@anileger
Copy link

Missing some Code Lines...

@lucasefe
Copy link

This is a copy of what you can find here: http://www.codeproject.com/Articles/32212/Introduction-to-Graph-with-Breadth-First-Search-BF

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.

@dharam3
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.

@mailmarwa
Copy link

Minor issue: getUnvisitedChildNode(node) instead of n.

@0xhmn
Copy link

0xhmn commented Jul 3, 2016

@sjcuello
Copy link

sjcuello commented Aug 2, 2016

cool!

@dkonayuki
Copy link

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

@sameer
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?

@juanmf
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(){
            return children.stream()
                    .filter(n -> ! n.visited)
                    .findFirst().orElse(null);
        }
    }

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

@AaronLiuIsCool
Copy link

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

@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