Package com.jgalgo.alg

Interface Dfs

public interface Dfs

Depth first search (DFS) iterator.

The DFS iterator is used to iterate over the vertices of a graph is a depth first manner, namely it explore as far as possible along each branch before backtracking. The iterator will visit every vertex \(v\) for which there is a path from the source(s) to \(v\). Each such vertex will be visited exactly once.

The graph should not be modified during the DFS iteration.

 
 Graph<String, Integer> g = ...;
 String sourceVertex = ...;
 for (Dfs.Iter<String, Integer> iter = Dfs.newInstance(g, sourceVertex); iter.hasNext();) {
     String v = iter.next();
     List<E> edgePath = iter.edgePath();
     System.out.println("Reached vertex " + v + " using the edges: " + edgePath.edges());
 }
 

Author:

Barak Ugav

See Also:

Bfs, Wikipedia

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	Dfs.IntIter	A DFS iterator for IntGraph.
static interface	Dfs.Iter<V,E>	A DFS iterator.

Method Summary

Static Methods

Modifier and Type	Method	Description
static <V,E> Dfs.Iter<V,E>	newInstance(Graph<V,E> g, V source)	Create a DFS iterator.
static Dfs.IntIter	newInstance(IntGraph g, int source)	Create a DFS iterator for an int graph.

Method Detail

newInstance

static <V,E> Dfs.Iter<V,E> newInstance(Graph<V,E> g,
                                                   V source)

Create a DFS iterator.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

source - a vertex in the graph from which the search will start from

Returns:

a DFS iterator that iterate over the vertices of the graph

newInstance

static Dfs.IntIter newInstance(IntGraph g,
                               int source)

Create a DFS iterator for an int graph.

Parameters:

g - a graph

source - a vertex in the graph from which the search will start from

Returns:

a DFS iterator that iterate over the vertices of the graph