Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

BFS and DFS in Java. Please give suggestions!!

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;
   }
}
share|improve this question
    
Can we count the distance as well? –  user21691 Jan 31 '13 at 22:12
add comment

3 Answers

up vote 8 down vote accepted

There seem to be some inconsistencies here. What is s? I guess this is the stack? Also declaring a class Main is a little strange. You certainly want to have a main method, but a Main class?

Also I'd suggest you not use raw collections e.g. replace

Queue queue = new LinkedList();

with

Queue<Node> queue = new LinkedList<Node>();

You may like to consider implementing DFS recursively so that you don't have to explicitly use a stack, although that's a matter of taste. Also, where is getUnvisitedChildNode() defined? Where are the edges of the graph actually stored? This could be e.g. an adjacency list carried around by each node, or perhaps in another object, but it should be somewhere.

share|improve this answer
    
Also it make sense to replace Stack stack = new Stack(); with Deque<Node> s = new LinkedList<Node>(); –  yurilo Jul 7 '12 at 5:47
add comment

It is better to name the functions as breadth-first traversal, or depth-first traversal instead, as you didn't look up any element, but travelled all the nodes. Quite trivial though :)

share|improve this answer
add comment

LinkedList supports both Stack as well as Queue operations. So you can use this for both cases. Also if you are using Java 6+, better use Deque Interface instead of Queue. (Deque extends Queue).

So your stack and queue declaration should be like below (for Java 6+ )

Deque<Node> queue = new LinkedList<Node>();
Deque<Node> stack = new LinkedList<Node>();
share|improve this answer
add comment

protected by syb0rg Mar 2 at 18:17

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.