KOB - 9 months ago 42

Java Question

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`

`Node.getChildren()`

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.

Source (Stackoverflow)