PDA

View Full Version : Java DFS find path




dvince2
Nov 28, 2007, 02:02 PM
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;

}