public class DepthFirstSearch
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
java.util.Map<java.lang.Object,java.lang.Integer> |
d |
java.util.Map<java.lang.Object,java.lang.Integer> |
f |
Constructor and Description |
---|
DepthFirstSearch() |
Modifier and Type | Method and Description |
---|---|
<VertexType,EdgeType extends Edge<VertexType>> |
dfs(Graph<VertexType,EdgeType> G)
Performs a depth first search for a given graph G.
|
<VertexType,EdgeType extends Edge<VertexType>> |
dfs(Graph<VertexType,EdgeType> G,
java.util.Set<VertexType> roots)
Performs a depth first search for a given graph G.
|
public java.util.Map<java.lang.Object,java.lang.Integer> d
public java.util.Map<java.lang.Object,java.lang.Integer> f
public <VertexType,EdgeType extends Edge<VertexType>> DirectedGraph<VertexType,DirectedEdge<VertexType>> dfs(Graph<VertexType,EdgeType> G, java.util.Set<VertexType> roots)
DFS(G)
for each vertex u ∈ V[G]
do color[u] ← WHITE
π[u] ← NIL
time ← 0
for each vertex u ∈ V[G]
do if color[u] = WHITE
then DFS-VISIT(u)
DFS - VISIT(u)
color[u] ← GRAY *WHITE vertex u has just been discovered.
time ← time + 1
d[u] ← time
for each v ∈ Adj[u] *Explore edge(u,v).
do if color[v] = WHITE
then π[v] ← u
DFS - VISIT(v)
color[u] ← BLACK *BLACKen u;
Modifications:
G
- a graph.roots
- a set of vertices from which depth first search should be
performed.public <VertexType,EdgeType extends Edge<VertexType>> DirectedGraph<VertexType,DirectedEdge<VertexType>> dfs(Graph<VertexType,EdgeType> G)
G
- a graph.