C ++ увеличить глубину сначала поиск указать порядок посещения - PullRequest
Новая
       28

C ++ увеличить глубину сначала поиск указать порядок посещения

0 голосов
/ 21 сентября 2019

Я новичок в улучшении и создании простого графика для первого поиска по глубине.Это график, который я создал. My Graph

Я выполняю поиск в глубину, начиная с узла 1. Затем я распечатываю время обнаружения и окончания для каждого узла, где узел 0 имеет время-1 потому что это никогда не достигается.В случае, если два или более узла будут одинаково подходить для следующего посещения, я хочу выбрать узел с наименьшим индексом.

Следовательно, мой желаемый результат: 

Discover Times: -1 0 1 3
Finish Times:   -1 5 2 4

Это все работает нормально, когда я вставляю ребра вот так 

boost::add_edge(boost::vertex(1, graph1), boost::vertex(2, graph1), graph1);
boost::add_edge(boost::vertex(1, graph1), boost::vertex(3, graph1), graph1);

Но когда я добавляю ребра в противоположном направленииorder 

boost::add_edge(boost::vertex(1, graph2), boost::vertex(3, graph2), graph2);
boost::add_edge(boost::vertex(1, graph2), boost::vertex(2, graph2), graph2);

Выходные данные 

Discover Times: -1 0 3 1 
Finish Times:   -1 5 4 2

Это означает, что узел 3 был посещен до узла 2.

Я подозреваю, что могу воспользоваться boost::vertex_indexфорсировать порядок посещения.Кроме того, я все еще не могу понять, как boost::make_iterator_property_map(&color_map[0], boost::get(boost::vertex_index, graph), color_map[0]) влияет на глубину моего первого поиска.

Весь мой код здесь: 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <iostream>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> graph_t;

void print_vector(std::vector<int> vec) {
    for(std::vector<int>::const_iterator i = vec.begin(); i != vec.end(); ++i) {
        std::cout << *i << ' ';
    }
    std::cout << std::endl;
}

void dfs(graph_t graph, int start_node) {
    int num_nodes = boost::num_vertices(graph);
    std::vector<int> dtime(num_nodes, -1);
    std::vector<int> ftime(num_nodes, -1);
    std::vector<boost::default_color_type> color_map(num_nodes);
    int time = -1;

    boost::depth_first_visit(
        graph,
        boost::vertex(start_node, graph),
        boost::make_dfs_visitor(std::make_pair(
            boost::stamp_times(&dtime[0], time, boost::on_discover_vertex()),
            boost::stamp_times(&ftime[0], time, boost::on_finish_vertex())
        )),
        boost::make_iterator_property_map(&color_map[0], boost::get(boost::vertex_index, graph), color_map[0])
    );

    std::cout << "Discover Times: ";
    print_vector(dtime);
    std::cout << "Finish Times:   ";
    print_vector(ftime);
}

int main() {
    std::ios_base::sync_with_stdio(false);

    int start_node = 1;
    int num_nodes = 4;

    graph_t graph1(num_nodes), graph2(num_nodes);

    // Add edges in order 1
    boost::add_edge(boost::vertex(1, graph1), boost::vertex(2, graph1), graph1);
    boost::add_edge(boost::vertex(1, graph1), boost::vertex(3, graph1), graph1);

    // Add edges in order 2
    boost::add_edge(boost::vertex(1, graph2), boost::vertex(3, graph2), graph2);
    boost::add_edge(boost::vertex(1, graph2), boost::vertex(2, graph2), graph2);

    std::cout << std::endl << "GRAPH 1" << std::endl;
    dfs(graph1, start_node);
    std::cout << std::endl << "GRAPH 2" << std::endl;
    dfs(graph2, start_node);
}

Что дает вывод: 

GRAPH 1
Discover Times: -1 0 1 3 
Finish Times:   -1 5 2 4 

GRAPH 2
Discover Times: -1 0 3 1 
Finish Times:   -1 5 4 2

Любая помощь приветствуется, спасибо заранее.

...