How to represent data to be used for DFS/BFS

Question

I was assigned a problem to solve using various search techniques. The problem is very similar to the Escape From Zurg problem or the Bridge and Torch problem. My issue is that I am lost as to how to represent the data as a tree.

This is my guess as to how to do it, but it doesn't make much sense for searching.

Another way could be to use a binary tree sorted by their walking time. However, I'm still not sure if I'm attacking this problem correctly since search algorithms don't necessarily require binary trees.

Any tips on representing this data would be appreciated.

Answer 1

Generally when you are using a tree search to solve a problem, each node represents some possible "state" of the world (who's on what side of the bridge, for example), and the children of each node represent all possible "successor states" (new states that can be reached in one move from the previous state). A depth-first search then represents trying one option until it dead-ends, then backing up to the last state where another option was available and trying it out. A breadth-first search represents trying out lots of options in parallel and seeing when the first of them find the goal node.

In terms of the actual way of encoding this, you would represent this as a multiway tree. Each node would probably contain the current state, plus a list of pointers to child nodes.

Hope this helps!

Answer 2

U could use something like this:

public class Node
{
   public int root;
   public List<Node> neighbours;
   public Node(int x)
   {
       root=x;
   }
   public void setNeighboursList(List<Node> l)
   {
       neighbours = l;
   }
   public void addNeighbour(Node n)
   {
       if(neighbours==null) neighbours = new ArrayList<Node>();
       neighbours.add(n);
   }
   ...
} 

public class Tree
{
    public Node root;
    ....
}