Standard recursive implementation of depth first search. More...

Inheritance diagram for aud.example.graph.DepthFirstSearch:

Collaboration diagram for aud.example.graph.DepthFirstSearch:

Public Member Functions
	DepthFirstSearch (MyGraph g)

String	name ()
	get traversal name More...

void	start (MyNode s0)
	start traversal at node s0 More...

Public Member Functions inherited from aud.example.graph.Traversal
	Traversal (MyGraph g)
	initiate traversal of `g` More...

abstract String	name ()
	get traversal name More...

abstract void	start (MyNode s0)
	start traversal at node s0 More...

void	showMark (MyNode node)
	callback to give visual feedback on marking a node More...

Protected Member Functions
void	dfs (MyNode s)

Protected Member Functions inherited from aud.example.graph.Traversal
void	initialize ()
	initialize graph for traversal (reset all attributes), provided for convenience to be called by `start` More...

Additional Inherited Members
Public Attributes inherited from aud.example.graph.Traversal
SingleStepper	singlestepper = null
	may halt if single stepper was set More...

int	nsteps = 1
	halt every nsteps steps in `time_` More...

int	verbose = 0
	set verbosity (extra output if >0) More...

Protected Attributes inherited from aud.example.graph.Traversal
MyGraph	g_ = null

int	time_ = 0

Detailed Description

Standard recursive implementation of depth first search.

This is the classic implementation of DFS. In addition, we provide two nonrecursive variants.

IterativeDFS1 is close to the recursive implementation (but reversing the order of examined edges)
IterativeDFS2 takes a "short cut" by marking nodes early. This leads to a different traversal.

See also: IterativeDFS1; IterativeDFS2

Definition at line 15 of file DepthFirstSearch.java.

Constructor & Destructor Documentation

◆ DepthFirstSearch()

aud.example.graph.DepthFirstSearch.DepthFirstSearch ( MyGraph g )

Definition at line 17 of file DepthFirstSearch.java.

                                     {
    super(g);
  }

Member Function Documentation

◆ dfs()

void aud.example.graph.DepthFirstSearch.dfs ( MyNode s )

protected

Definition at line 35 of file DepthFirstSearch.java.

                               {
    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);
      }
    }
  }

References aud.example.graph.MyNode.ord.

◆ name()

String aud.example.graph.DepthFirstSearch.name ( )

get traversal name

Reimplemented from aud.example.graph.Traversal.

Definition at line 21 of file DepthFirstSearch.java.

21{ return "recursive DFS"; }

◆ start()

void aud.example.graph.DepthFirstSearch.start ( MyNode s0 )

start traversal at node s0

Reimplemented from aud.example.graph.Traversal.

Definition at line 25 of file DepthFirstSearch.java.

                                         {
 
    initialize(); // reset all node attributes
 
    count_ = 0;
    s0.d=0.0;
 
    dfs(s0);
  }

References aud.example.graph.Traversal.initialize().

Here is the call graph for this function:

The documentation for this class was generated from the following file:

DepthFirstSearch.java

Public Member Functions

Protected Member Functions