Посетитель DFS не пересекает отсоединенные вершины

У меня есть график, представленный списком смежности. Я применяю для этого алгоритм depth_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)
    );

person user2301299    schedule 05.06.2013    source источник


Ответы (2)


«Если граф несвязный, DFS не будет посещать все его вершины. Подробнее см. Алгоритм поиска связных компонентов». Ссылка: Алголист

Вы не делаете ничего плохого. И ваше исправление (нахождение других непосещенных узлов и повторный запуск алгоритма) — это то, что делают другие реализации.

В качестве еще одного наглядного доказательства посмотрите на эту отличную реализацию на странице TimL. Вы можете продолжать нажимать и наблюдать за выполнением DFS. (Прокрутите вниз до середины страницы.)

person Ram Narasimhan    schedule 05.06.2013

Похоже, ваш алгоритм верен, так как это, по сути, то, что делает DFS: он проходит через все подключенные узлы, а это означает, что вам нужно будет запускать его на каждом подключенном компоненте отдельно. В зависимости от вашего варианта использования вы можете захотеть изучить алгоритмы поиска подключенных компонентов, которые используют какой-то алгоритм DFS или BFS.

person Florian Lauck    schedule 05.06.2013