This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

undirected_dfs

Performs a depth-first traversal of the vertices in an undirected graph.

Complexity: O(E + V)
Defined in: <boost/graph/undirected_dfs.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/undirected_dfs.hpp>
#include <iostream>

struct VertexProps { int id; };

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProps>;
using Edge = boost::graph_traits<Graph>::edge_descriptor;

struct Visitor : boost::default_dfs_visitor {
    void discover_vertex(Graph::vertex_descriptor v, const Graph& g) const {
        std::cout << "discover " << g[v].id << "\n";
    }
    void finish_vertex(Graph::vertex_descriptor v, const Graph& g) const {
        std::cout << "finish   " << g[v].id << "\n";
    }
};

int main() {
    Graph g{4};
    for (int i = 0; i < 4; ++i) { g[i].id = i; }
    boost::add_edge(0, 1, g);
    boost::add_edge(0, 2, g);
    boost::add_edge(1, 3, g);

    using ColorMap = std::map<Graph::vertex_descriptor, boost::default_color_type>;
    using EdgeColorMap = std::map<Edge, boost::default_color_type>;
    ColorMap vcmap;
    EdgeColorMap ecmap;
    boost::undirected_dfs(g, Visitor{},
        boost::make_assoc_property_map(vcmap),
        boost::make_assoc_property_map(ecmap));
}
discover 0
discover 1
discover 3
finish   3
finish   1
discover 2
finish   2
finish   0

(1) Positional version

template <typename Graph,
          typename DFSVisitor,
          typename VertexColorMap,
          typename EdgeColorMap>
void undirected_dfs(const Graph& g, DFSVisitor vis,
    VertexColorMap vertex_color, EdgeColorMap edge_color);
Direction Parameter Description

IN

const Graph& g

An undirected graph. The graph type must be a model of Incidence Graph, Vertex List Graph, and Edge List Graph.

IN

DFSVisitor vis

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/OUT

VertexColorMap vertex_color

This is used by the algorithm to keep track of its progress through the graph. The type VertexColorMap must be a model of Read/Write Property Map and its key type must be the graph’s vertex descriptor type and the value type of the color map must model ColorValue.

UTIL

EdgeColorMap edge_color

This is used by the algorithm to keep track of which edges have been visited. The type EdgeColorMap must be a model of Read/Write Property Map and its key type must be the graph’s edge descriptor type and the value type of the color map must model ColorValue.

(2) With explicit start vertex

template <typename Graph,
          typename DFSVisitor,
          typename VertexColorMap,
          typename EdgeColorMap>
void undirected_dfs(const Graph& g, DFSVisitor vis,
    VertexColorMap vertex_color, EdgeColorMap edge_color,
    typename graph_traits<Graph>::vertex_descriptor start);
Direction Parameter Description

IN

const Graph& g

An undirected graph. The graph type must be a model of Incidence Graph, Vertex List Graph, and Edge List Graph.

IN

DFSVisitor vis

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/OUT

VertexColorMap vertex_color

This is used by the algorithm to keep track of its progress through the graph. The type VertexColorMap must be a model of Read/Write Property Map and its key type must be the graph’s vertex descriptor type and the value type of the color map must model ColorValue.

UTIL

EdgeColorMap edge_color

This is used by the algorithm to keep track of which edges have been visited. The type EdgeColorMap must be a model of Read/Write Property Map and its key type must be the graph’s edge descriptor type and the value type of the color map must model ColorValue.

IN

vertex_descriptor start

The vertex that the depth-first search should originate from.

(3) Named parameter version

template <typename Graph,
          typename P,
          typename T,
          typename R>
void undirected_dfs(Graph& G,
    const bgl_named_params<P, T, R>& params);
Direction Parameter Description

IN

Graph& g

An undirected graph. The graph type must be a model of Incidence Graph, Vertex List Graph, and Edge List Graph.

IN

visitor(DFSVisitor vis)

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].
Default: dfs_visitor<null_visitor>

UTIL/OUT

vertex_color_map(VertexColorMap vertex_color)

This is used by the algorithm to keep track of its progress through the graph. The type VertexColorMap must be a model of Read/Write Property Map and its key type must be the graph’s vertex descriptor type and the value type of the color map must model ColorValue.
Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.

UTIL

edge_color_map(EdgeColorMap edge_color)

This is used by the algorithm to keep track of which edges have been visited. The type EdgeColorMap must be a model of Read/Write Property Map and its key type must be the graph’s edge descriptor type and the value type of the color map must model ColorValue.
Default: none.

IN

root_vertex(typename graph_traits<VertexListGraph>::vertex_descriptor start)

This specifies the vertex that the depth-first search should originate from. The type is the type of a vertex descriptor for the given graph.
Default: *vertices(g).first

IN

vertex_index_map(VertexIndexMap i_map)

This maps each vertex to an integer in the range [0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.
Default: get(vertex_index, g). Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

Description

The undirected_dfs() function performs a depth-first traversal of the vertices in an undirected graph. When possible, a depth-first traversal chooses a vertex adjacent to the current vertex to visit next. If all adjacent vertices have already been discovered, or there are no adjacent vertices, then the algorithm backtracks to the last vertex that had undiscovered neighbors. Once all reachable vertices have been visited, the algorithm selects from any remaining undiscovered vertices and continues the traversal. The algorithm finishes when all vertices have been visited. Depth-first search is useful for categorizing edges in a graph, and for imposing an ordering on the vertices. Section Depth-First Search describes the various properties of DFS and walks through an example.

Similar to BFS, color markers are used to keep track of which vertices have been discovered. White marks vertices that have yet to be discovered, gray marks a vertex that is discovered but still has vertices adjacent to it that are undiscovered. A black vertex is discovered vertex that is not adjacent to any white vertices.

Edges are also colored during the search to disambiguate tree and back edges.

The undirected_dfs() function invokes user-defined actions at certain event-points within the algorithm. This provides a mechanism for adapting the generic DFS algorithm to the many situations in which it can be used. In the pseudo-code below, the event points for DFS are the labels on the right. The user-defined actions must be provided in the form of a visitor object, that is, an object whose type meets the requirements for a DFS Visitor. In the pseudo-code we show the algorithm computing predecessors p, discover time d and finish time t. By default, the undirected_dfs() function does not compute these properties, however there are pre-defined visitors such as predecessor_recorder and time_stamper that can be used to do this.

Algorithm Event Points 
DFS(G)
  for each vertex u in V
    vcolor[u] := WHITE
    p[u] := u
  end for
  for each edge e in E
    ecolor[u] := WHITE
  end for
  time := 0
  if there is a starting vertex s
    call DFS-VISIT(G, s)
  for each vertex u in V
    if vcolor[u] = WHITE
      call DFS-VISIT(G, u)
  end for
  return (p,d_time,f_time)

DFS-VISIT(G, u)
  vcolor[u] := GRAY
  d_time[u] := time := time + 1
  for each e in Out[u]
    var ec := ecolor[e]
    ecolor[e] := BLACK
    if (vcolor[v] = WHITE)
      p[v] := u
      call DFS-VISIT(G, v)
    else if (vcolor[v] = GRAY and ec = WHITE)
      ...
    ...
  end for
  vcolor[u] := BLACK
  f_time[u] := time := time + 1
 
.
.
initialize vertex u
.
.
.
.
.
.
.
start vertex s
.
.
start vertex u
.
.
.
.
discover vertex u
.
examine edge (u,v)
.
.
(u,v) is a tree edge
.
.
(u,v) is a back edge
.
.
finish edge (u,v)
.
finish vertex u

Visitor Event Points

  • vis.initialize_vertex(s, g) is invoked on every vertex of the graph before the start of the graph search.

  • vis.start_vertex(s, g) is invoked on the source vertex once before the start of the search.

  • vis.discover_vertex(u, g) is invoked when a vertex is encountered for the first time.

  • vis.examine_edge(e, g) is invoked on every out-edge of each vertex after it is discovered.

  • vis.tree_edge(e, g) is invoked on each edge as it becomes a member of the edges that form the search tree. If you wish to record predecessors, do so at this event point.

  • vis.back_edge(e, g) is invoked on the back edges in the graph.

  • vis.finish_edge(e, g) is invoked on the back edges in the graph as well as on each tree edge after its target vertex is finished.

  • vis.finish_vertex(u, g) is invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before their out-edges have been examined).

Notes

[1] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

Edit this Page