Package dev.nm.graph.algorithm.traversal
Class BFS<V>
- java.lang.Object
-
- dev.nm.graph.algorithm.traversal.TraversalFromRoots<V>
-
- dev.nm.graph.algorithm.traversal.BFS<V>
-
- Type Parameters:
V
- vertex type
- All Implemented Interfaces:
GraphTraversal<V>
public class BFS<V> extends TraversalFromRoots<V> implements GraphTraversal<V>
This class implements the breadth-first-search using iteration.- See Also:
- Wikipedia: Breadth-first search
-
-
Field Summary
-
Fields inherited from class dev.nm.graph.algorithm.traversal.TraversalFromRoots
g
-
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static <V,W extends V>
List<BFS.Node<V>>BFS(Graph<W,? extends Edge<V>> g, V root, int time)
Runs the breadth-first-search on a graph from a designated root.List<BFS.Node<V>>
getOrderedNodes()
Gets the collection of visited nodes to build a spanning tree.List<? extends BFS.Node<V>>
track(V root, int time)
Runs the traversal algorithm on a graph from a designated root.-
Methods inherited from class dev.nm.graph.algorithm.traversal.TraversalFromRoots
traverse
-
-
-
-
Method Detail
-
track
public List<? extends BFS.Node<V>> track(V root, int time)
Description copied from class:TraversalFromRoots
Runs the traversal algorithm on a graph from a designated root.- Specified by:
track
in classTraversalFromRoots<V>
- Parameters:
root
- a roottime
- the initial time- Returns:
- the nodes visited
-
BFS
public static <V,W extends V> List<BFS.Node<V>> BFS(Graph<W,? extends Edge<V>> g, V root, int time)
Runs the breadth-first-search on a graph from a designated root.- Type Parameters:
V
- vertex type- Parameters:
g
- a graphroot
- a roottime
- the initial time- Returns:
- the nodes visited
-
getOrderedNodes
public List<BFS.Node<V>> getOrderedNodes()
Description copied from class:TraversalFromRoots
Gets the collection of visited nodes to build a spanning tree.- Specified by:
getOrderedNodes
in interfaceGraphTraversal<V>
- Overrides:
getOrderedNodes
in classTraversalFromRoots<V>
- Returns:
- the collection of visited nodes
-
-