DFS visitor does not traverse detached vertices

Question

I have a graph represented by adjacency list. I apply depth_first_visit algorithm for it. Everything works almost OK. The problem is that the algorithm visits only vertices, which are connected with my starting point vertex. If I have separate vertices (without any connection), they are not traversed. Of course I have solved this problem by finding not visited vertices and then starting the algorithm from them but In the documentation it is written that those "detached" vertices shall also be traversed. Question - am I doing something wrong?

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex, Edge > GraphType;

vector<default_color_type> color_map(num_vertices(m_graph));

depth_first_visit(
       m_graph,
       *vp.first,
       custom_dfs_visitor(m_currentPath, visited),
       make_iterator_property_map(
           color_map.begin(),
           get(vertex_index, m_graph),
           color_map[0]),
       Terminator(m_currentPath)
    );

Answer 1

"If a graph is disconnected, DFS won't visit all of its vertices. For details, see finding connected components algorithm." Reference: Algolist

You not are doing anything wrong. And your fix (finding other unvisited nodes, and starting the algorithm again) is what other implementations do.

As further visible proof, look at this excellent implementation on TimL's page. You can keep clicking and watch the DFS being executed. (Scroll down to the middle of the page.)

Answer 2

It seems like your algorithm is correct, since this is essentially what a DFS does: It traverses all connected nodes, meaning that you would need to run it on each connected component separately. Depending on your use case you might want to look into algorithms for finding connected components, which utilize some sort of DFS or BFS algorithm.