Посетитель DFS не пересекает отдельные вершины
У меня есть график, представленный списком смежности. Я применяю для этого алгоритм deep_first_visit. Все работает почти нормально.
Проблема в том, что алгоритм посещает только те вершины, которые связаны с моей начальной точкой вершины. Если у меня есть отдельные вершины (без какой-либо связи), они не пройдены.
Конечно, я решил эту проблему, найдя не посещенные вершины и затем запустив алгоритм из них, но в документации написано, что эти «отсоединенные» вершины также должны быть пройдены. Вопрос — я что-то не так делаю?
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)
);
Решение
«Если граф отключен, DFS не будет посещать все его вершины. Для получения дополнительной информации см. Алгоритм поиска подключенных компонентов». Ссылка: Algolist
Вы не делаете ничего плохого. И ваше исправление (поиск других не посещенных узлов и повторный запуск алгоритма) — это то, что делают другие реализации.
Как еще одно видимое доказательство, посмотрите на это отличная реализация на странице TimL. Вы можете продолжать нажимать и наблюдать за выполнением DFS. (Прокрутите вниз до середины страницы.)
Другие решения
Кажется, что ваш алгоритм правильный, так как это, по сути, то, что делает DFS: он пересекает все подключенные узлы, что означает, что вам нужно будет запускать его на каждом подключенном компоненте в отдельности. В зависимости от вашего варианта использования вы можете изучить алгоритмы поиска подключенных компонентов, которые используют какой-либо алгоритм DFS или BFS.