Apr 182012
 

A recursive algorithm to find a path in a graph.

 /**
  * A recursive method for getting a path to a node if possible. Returns a
  * LinkedList of nodes that constitute the path starting at index 0.
  * It is important to note that the path returned may not be the shortest.
  * If the path it returns starts with the starting node and the ends
  * with the final node, then there is a path, if not, then there is no path.
  * If the start node and end node are the same, then it is cyclical.
  *
  * @param node The first node in the path
  * @param endNode The last node in the possible path
  * @param path An empty LinkedList<Node> used to build the path
  * @param visited An empty LinkedList<Node> used to record visited
  *        nodes
  * @return Returns a LinkedList of nodes that constitute a path. If the
  *         path it returns starts with the starting node and ends with
  *         the final node, then there is a path, otherwise, there is no
  *         path.
  */
private LinkedList<Node> visitNode(Node node,
                                      Node endNode,
                                      LinkedList<Node> path,
                                      LinkedList<Node> visited) {

  LinkedList<Node> children = this.adjacentNodes(node);
  boolean found = false;

  if((path.size()>1) && path.getLast().equals(endNode)) {
    found = true;
  }

  if(!found) {
    path.addLast(node);
  }

  for (Iterator<Node> it = children.iterator(); it.hasNext() && !found;) {
    Node child = it.next();

    if(child.equals(endNode)) {
      path.addLast(child);
      found = true;
    }

    if(!visited.contains(child) && !found) {
      visited.add(child);
      path = visitNode(child, endNode, path, visited);
    }
  }

  return path;
}
 Posted by at 7:18 am