KOB KOB - 2 months ago 14
Java Question

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

Answer

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.