Java DFS find path

Discussion in 'Mac Programming' started by dvince2, Nov 28, 2007.

  1. macrumors 6502

    dvince2

    Joined:
    Mar 6, 2007
    Messages:
    283
    Location:
    Canada
    #1
    hey everyone!
    quick question.

    I've been working on this for several days now, and I can't seem to find whats wrong. I'm attempting to write a (recursive) method to for findPath using DFS. Its supposed to return an iterator over the verticies on the path. S is an instance variable of type Stack<Vertex<V>>

    My code presently compiles and runs a few recursions, then usually crashes. any suggestions? Thanks in advance!

    here is what I have:

    public Iterator<Vertex<V>> givePath(Graph<V> g, Vertex<V> v, Vertex<V> z){

    Iterator<Vertex<V>>result=null;;

    System.out.println("Object:" + v.getObject().toString()+" size S: "+S.size()) ;

    v.setMarker(true);
    this.S.push(v);

    if(v==z){
    return this.S.iterator();
    }

    Iterator <Edge<V>>incidentEdges= v.incidentEdges();
    Vertex<V> w;
    Edge<V> e;
    while(incidentEdges.hasNext()){
    e=incidentEdges.next();

    w = g.giveOpposite(v, e);
    if(!w.getMarker()){
    result=givePath(g,w,z);

    if(result!=null){
    return result;
    }
    }
    }

    this.S.pop();
    return null;

    }
     

Share This Page