depth_first_visit
Visits all vertices in the same connected component as a source vertex using a depth-first pattern.
Complexity: O(E)
Defined in: <boost/graph/depth_first_search.hpp>
Example
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
#include <vector>
struct VertexProps { int id; };
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProps>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
struct PrintVisitor : boost::default_dfs_visitor {
void discover_vertex(Vertex v, const Graph& g) const {
std::cout << g[v].id << " ";
}
};
int main() {
Graph g{5};
for (int i = 0; i < 5; ++i) { g[i].id = i; }
boost::add_edge(0, 1, g);
boost::add_edge(0, 2, g);
boost::add_edge(1, 3, g);
boost::add_edge(2, 4, g);
// depth_first_visit explores from a single source without initializing colors.
// Caller must provide a color map.
std::vector<boost::default_color_type> colors(num_vertices(g), boost::white_color);
auto color_map = boost::make_iterator_property_map(colors.begin(), get(boost::vertex_index, g));
std::cout << "DFS visit order: ";
boost::depth_first_visit(g, vertex(0, g), PrintVisitor{}, color_map);
std::cout << std::endl;
}DFS visit order: 0 1 3 2 4(1) Basic version
template <class IncidenceGraph,
class DFSVisitor,
class ColorMap>
void depth_first_visit(IncidenceGraph& g,
typename graph_traits<IncidenceGraph>::vertex_descriptor s,
DFSVisitor& vis,
ColorMap color);| Direction | Parameter | Description |
|---|---|---|
IN |
|
A directed or undirected graph. The graph type must be a model of Incidence Graph. |
IN |
|
The source vertex from which to start the search. |
IN |
|
A visitor object that is invoked inside the algorithm at the event-points specified by the DFS Visitor concept. The visitor object is passed by value [1]. |
UTIL |
|
This is used by the algorithm to keep track of its progress through the
graph. The type |
(2) With terminator function
template <class IncidenceGraph,
class DFSVisitor,
class ColorMap,
class TerminatorFunc>
void depth_first_visit(IncidenceGraph& g,
typename graph_traits<IncidenceGraph>::vertex_descriptor s,
DFSVisitor& vis,
ColorMap color,
TerminatorFunc func = TerminatorFunc());| Direction | Parameter | Description |
|---|---|---|
IN |
|
A directed or undirected graph. The graph type must be a model of Incidence Graph. |
IN |
|
The source vertex from which to start the search. |
IN |
|
A visitor object that is invoked inside the algorithm at the event-points specified by the DFS Visitor concept. The visitor object is passed by value [1]. |
UTIL |
|
This is used by the algorithm to keep track of its progress through the
graph. The type |
IN |
|
A function object callable with two parameters — the descriptor of a
vertex and the graph instance — and returning |
Description
This function visits all of the vertices in the same connected component
as the source vertex s, using the
depth-first pattern.
The main purpose of the function is for the implementation of
depth_first_search() though sometimes it is useful on its own.
The DFSVisitor supplied by the user determines what actions are taken
at each event-point within the algorithm.
The ColorMap is used by the algorithm to keep track of which vertices
have been visited.
The second variant can be used, for example, to find all marked vertices reachable from a start vertex by a path which does not contain any another marked vertices.