BFS and DFS

 Recently I had interviewed with couple companies, BFS and DFS are frequently asked in interviews. I guess it's worth to write it down to refresh my memory.

BFS:

public void bfsWithRecursive(Queue q){

    if(q.isEmpty()) return;

    Node n = q.poll();

    System.out.println(n.data);

    for(Node node: n.getNeighbours()){

        if(node != null && !node.visited){

            node.visited = true;

            q.add(node);

        }

    }

    bsfWithResursive(q);

}

public void bfsWithoutRecursive(Queue q){

    if(q.isEmpty()) return;

    while(!q.isEmpty()){

        Node n = q.poll();

        if(!n.visited)  System.out.println(n.data);

        for(Node node:n.getNeighbours()){

            if(node != null && !node.visited) {

                node.visited = true;

                q.add(node);

            }

        }

    }

}

DFS:

public void dfsWithRecursive(Node node){

    System.out.println(node.data);

    node.visited = true;

    for(Node n:node.getNeighbours()){

        if(n != null && !n.visited){

            dfsWithRecursive(n);

        }

    }

}

public void dfsWithoutRecursive(Node node){

    Stack<Node> stack = new Stack<>();

    stack.add(node);

    while(!stack.isEmpty()){

        Node n = stack.pop();

        System.out.println(n.data);

        n.visited = true;

        for(Node nd: n.getNeighbours()){

            if(nd != null && !nd.visited){

                nd.visited = true;

                stack.add(nd);

            }

        }

    }

}