KOB - 1 year ago 73
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) {

while (!open.isEmpty()) {
Node current = open.removeFirst();
if (current.equals(target)) {
return closed;
}
else {
ArrayList<Node> children = current.getChildren();
for (Node child : children) {
if (!open.contains(child) && !closed.contains(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);
}

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

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

``````            ArrayList<Node> children = current.getChildren();
// *** Not like this ***
// for (Node child : children) {
//    if (!open.contains(child) && !closed.contains(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)) {
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.