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.booleanisCyclic()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:TraversalFromRootsRuns the traversal algorithm on a graph from a designated root.- Specified by:
trackin 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:TraversalFromRootsGets the collection of visited nodes to build a spanning tree.- Specified by:
getOrderedNodesin interfaceGraphTraversal<V>- Overrides:
getOrderedNodesin classTraversalFromRoots<V>- Returns:
- the collection of visited nodes
-
isCyclic
public boolean isCyclic()
Checks if the graph is cyclic.- Returns:
trueif the graph is cyclic
-
-