Function
depth_first_search
Implements a depth-first search on a graph.
depth_first_search(g, predecessor, discovery, finish)
Parameters
g
In-parameter:A graph.
Types: Graph
predecessor
Out-parameter:A property map.
Remarks: Predecessor subgraph produced by the depth-first search.
discovery
Out-parameter:A property map.
Remarks: The discovery time of a vertex v.
finish
Out-parameter:A property map.
Remarks: The time when v's adjacency list has been fully explored.
Return Values
void.
Remarks
In contrast to a breadth-first search the depth-first search is repeated from multiple sources if the graph is not connected. Hence, depth-first search produces a depth-first forest. To ensure each vertex ends up in exactly one tree we need not just a distance but a discovery and finishing time.
Example Programs
SeqAn - Sequence Analysis Library - www.seqan.de