CODEWITHSUNDEEP
javasearchtreedepth-first-search
KOB
KOB

Reputation: 4545

DFS algorithm is searching from right to left

I have written a Depth First Search algorithm, but it is searching from the right side of the tree towards the left. I can see from my code why it is doing so, but I cannot come up with a solution to change it so that it searches from left to right.

public class DFS {

    public LinkedList<Node> search(Node root, Node target) {    
        LinkedList<Node> open = new LinkedList<>();
        LinkedList<Node> closed = new LinkedList<>();

        open.addLast(root);
        while (!open.isEmpty()) {
            Node current = open.removeFirst();
            if (current.equals(target)) {
                closed.addLast(current);
                return closed;
            }
            else {
                ArrayList<Node> children = current.getChildren();
                closed.addLast(current);
                for (Node child : children) {
                    if (!open.contains(child) && !closed.contains(child)) {
                        open.addFirst(child);
                    }
                }
            }
        }
        return null;
    }
}

closed is a list of the nodes visited in the order in which they were visited.

Node.getChildren() returns an ArrayList of the node's children in the order in which they were added.

EDIT

Here is the node class:

public class Node {

    private ArrayList<Node> children;
    private String name;

    public Node(String name){
        children = new ArrayList<Node>();
        this.name = name;
    }

    public ArrayList<Node> getChildren(){
        return new ArrayList<Node>(children);
    }

    public Node addChild(Node child){
        children.add(child);
        return child;
    }

    public void removeChild(Node child){
        children.remove(child);
    }

    public String getName() {
        return name;
    }

    public boolean equals(Node other){
        return (this.getName().compareTo(other.getName())==0);
    }
}

Upvotes: 0

Views: 2037

Answers (3)

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

The simple response to 'how to avoid right-to-left' question is:

            ArrayList<Node> children = current.getChildren();
            closed.addLast(current);
            // *** Not like this ***
            // for (Node child : children) {
            //    if (!open.contains(child) && !closed.contains(child)) {
            //        open.addFirst(child);
            //    }
            //}
            // **** But like this ****
            for(int i=children.size()-1; i>=0; i-- ) {
                Node child=children.get(i);
                if (!open.contains(child) && !closed.contains(child)) {
                    open.addFirst(child);
                }
            }
            // If you are **absolutely** sure your structure is a 
            // Tree (thus, no cycles) then testing against 
            // open/closed is unnecessary and the code can be simplified: as
            // open.addAll(0, children);

You algo is flawed anyway: there's no provision to windup/discard a descending path in the tree that failed to bear a result (you never remove from closed) - but this is out of the scope of your question.

Upvotes: 0

gia
gia

Reputation: 757

getChildren has elements 1..n

Then you have a stack "open", from which you pop the first element every time you execute the main loop.

You fill this stack by pushing childs to the front of the stack (addFirst), then for 1..n you end with n..1 (insert 1, it is now first, insert 2, it is now first, 1 is second, and so on).

pop open from the last index, or push children to the end of the stack and it should work unless getChildren is not returning in the order you claim it does.

Upvotes: 0

Jaleks
Jaleks

Reputation: 630

If your DFS really relies on the direction, reverse your children, or addFirst instead of addLast?

Upvotes: 1

Related Questions