DepthFirstSearch.java

Go to the documentation of this file.

package aud.example.graph;
 
public class DepthFirstSearch extends Traversal {
 
  public DepthFirstSearch(MyGraph g) {
    super(g);
  }
 
  @Override public String name() { return "recursive DFS"; }
 
  private int count_ = 0;
 
  @Override public void start(MyNode s0) {
 
    initialize(); // reset all node attributes
 
    count_ = 0;
    s0.d=0.0;
 
    dfs(s0);
  }
 
  protected void dfs(MyNode s) {
    s.ord=count_++; // marked
    showMark(s);
    showVisit(s);
 
    if (verbose>0)
      System.out.println("s="+s);
 
    for (MyEdge e : g_.getOutEdges(s)) {
 
      if (verbose>1)
        System.err.println(e);
 
      MyNode t=(MyNode) e.destination();
      if (t==s)
          t=(MyNode) e.source(); // undirected graph
 
      if (t.ord<0) { // <=> not marked
        t.d=s.d+(e.hasWeight() ? e.getWeight() : 1.0);
        t.p=s;
        dfs(t);
      }
    }
  }
}