Package com.jgalgo.alg

Interface Bfs

public interface Bfs

Bread first search (BFS) iterator.

The BFS iterator is used to iterate over the vertices of a graph in a bread first manner, namely by the cardinality distance of the vertices from some source(s) vertex. 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 BFS iteration.

 
 Graph<String, Integer> g = ...;
 String sourceVertex = ...;
 for (Bfs.Iter<String, Integer> iter = Bfs.newInstance(g, sourceVertex); iter.hasNext();) {
     String v = iter.next();
     Integer e = iter.inEdge();
     int layer = iter.layer();
     System.out.println("Reached vertex " + v + " at layer " + layer + " using edge " + e);
 }
 

Author:

Barak Ugav

See Also:

Dfs, Wikipedia

Nested Class Summary

Nested Classes

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

Method Summary

Static Methods

Modifier and Type	Method	Description
static <V,E> Bfs.Iter<V,E>	newInstance(Graph<V,E> g, V source)	Create a BFS iterator.
static Bfs.IntIter	newInstance(IntGraph g, int source)	Create a BFS iterator in an int graph.
static <V,E> Bfs.Iter<V,E>	newInstanceBackward(Graph<V,E> g, V source)	Create a backward BFS iterator.
static Bfs.IntIter	newInstanceBackward(IntGraph g, int source)	Create a backward BFS iterator in an int graph.

Method Detail

newInstance

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

Create a BFS iterator.

If an IntGraph is passed as an argument Bfs.IntIter is returned.

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 BFS iterator that iterate over the vertices of the graph

newInstance

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

Create a BFS iterator in an int graph.

Parameters:

g - a graph

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

Returns:

a BFS iterator that iterate over the vertices of the graph

newInstanceBackward

static <V,E> Bfs.Iter<V,E> newInstanceBackward(Graph<V,E> g,
                                                           V source)

Create a backward BFS iterator.

The regular BFS uses the out-edges of each vertex to explore its neighbors, while the backward BFS uses the in-edges to do so.

If an IntGraph is passed as an argument Bfs.IntIter is returned.

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 BFS iterator that iterate over the vertices of the graph using the in-edges

newInstanceBackward

static Bfs.IntIter newInstanceBackward(IntGraph g,
                                       int source)

Create a backward BFS iterator in an int graph.

The regular BFS uses the out-edges of each vertex to explore its neighbors, while the backward BFS uses the in-edges to do so.

Parameters:

g - a graph

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

Returns:

a BFS iterator that iterate over the vertices of the graph using the in-edges