Package dev.nm.graph.algorithm.traversal
Class DFS<V>
- java.lang.Object
-
- dev.nm.graph.algorithm.traversal.TraversalFromRoots<V>
-
- dev.nm.graph.algorithm.traversal.DFS<V>
-
- Type Parameters:
V
- vertex type
- All Implemented Interfaces:
GraphTraversal<V>
public class DFS<V> extends TraversalFromRoots<V> implements GraphTraversal<V>
This class implements the depth-first-search using iteration.- See Also:
- Wikipedia: Depth-first search
- http://stackoverflow.com/questions/10342306/non-recursive-depth-first-search-dfs-using-a-stack
-
-
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<DFS.Node<V>>DFS(Graph<W,? extends Edge<V>> g, V root, int time)
Runs the depth-first-search on a graph from a designated root.List<DFS.Node<V>>
getOrderedNodes()
Gets the collection of visited nodes to build a spanning tree.boolean
isCyclic()
Checks if the graph is cyclic.List<DFS.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<DFS.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
-
DFS
public static <V,W extends V> List<DFS.Node<V>> DFS(Graph<W,? extends Edge<V>> g, V root, int time)
Runs the depth-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<DFS.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
-
isCyclic
public boolean isCyclic()
Checks if the graph is cyclic.- Returns:
true
if the graph is cyclic
-
-