Breadth and Depth First Search in Java

  • 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;
    }
    }

    Can we count the distance as well?

  • Jason

    Jason Correct answer

    9 years ago

    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.


    Also it make sense to replace Stack stack = new Stack(); with Deque s = new LinkedList();

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM

Tags used