Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link

aviggiano commented Feb 27, 2013

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

Regards

@frankhanner

This comment has been minimized.

Copy link

frankhanner commented Mar 7, 2013

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

@dtturcotte

This comment has been minimized.

Copy link

dtturcotte commented May 29, 2013

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

@anileger

This comment has been minimized.

Copy link

anileger commented Nov 20, 2013

Missing some Code Lines...

@lucasefe

This comment has been minimized.

Copy link

lucasefe commented Dec 16, 2013

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.

@ghost

This comment has been minimized.

Copy link

ghost commented Mar 3, 2014

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

@dharam3

This comment has been minimized.

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

This comment has been minimized.

Copy link

mailmarwa commented May 12, 2016

Minor issue: getUnvisitedChildNode(node) instead of n.

@yar00001

This comment has been minimized.

Copy link

yar00001 commented Jul 3, 2016

@sjcuello

This comment has been minimized.

Copy link

sjcuello commented Aug 2, 2016

cool!

@dkonayuki

This comment has been minimized.

Copy link

dkonayuki commented Sep 12, 2016

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

@sameer

This comment has been minimized.

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

This comment has been minimized.

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

This comment has been minimized.

Copy link

AaronLiuIsCool commented Mar 13, 2017

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

@nicksc423

This comment has been minimized.

Copy link

nicksc423 commented Apr 4, 2017

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
You can’t perform that action at this time.