首页 文章

BGL中的有限深度搜索没有O（number_of_vertices）使用的内存或时间？

提问于
浏览 次
2

是否可以进行深度或广度的首次搜索/访问距离BGL中的顶点一定距离，而无需访问，过滤，索引等图中的所有顶点？

我设法写的最接近的是（创建图0 < - > 1 < - > 2 < - > 3 < - > 4 < - > 5但只访问顶点0到3）：

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

using namespace std;

struct custom_dfs_visitor : public boost::default_dfs_visitor {
    template < typename Vertex, typename Graph >
    void discover_vertex(const Vertex& v, const Graph& g) const {
        std::cout << v << std::endl;
    }
};

struct Terminator {
    template<class Vertex, class Graph>
    bool operator()(const Vertex& v, const Graph& g) {
        return v > 2;
    }
};

int main()
{
    typedef boost::adjacency_list<
        boost::vecS,
        boost::vecS,
        boost::undirectedS
    > Graph_T;

    Graph_T g(6);
    boost::add_edge(0, 1, g);
    boost::add_edge(1, 2, g);
    boost::add_edge(2, 3, g);
    boost::add_edge(3, 4, g);
    boost::add_edge(4, 5, g);

    std::vector<boost::default_color_type> color_map(boost::num_vertices(g));
    boost::depth_first_visit(
        g,
        boost::vertex(0, g),
        custom_dfs_visitor(),
        boost::make_iterator_property_map(
            color_map.begin(),
            boost::get(boost::vertex_index, g),
            color_map[0]
        ),
        Terminator()
    );

    return 0;
}

它只打印0 1 2 3而不是访问所有顶点，但代码仍然需要一个与整个图形一样大的颜色图（boost :: num_vertices（g）） . 有没有办法使搜索复杂度与图中边/顶点的总数不相上下？

使用捆绑颜色是可以接受的，因为许多搜索将在图形的不同部分进行，但是是否可以从O（number_of_vertices）降低同一图形中每个单独搜索的复杂性？当终结者返回true时，顶点的初始着色有望也会停止，但这似乎已经得到了解决 . 也许是一个相关的问题：如果图表使用的不是vecS，那么索引怎么办？在这种情况下，BFS / DFS可以不进行索引吗？谢谢你的帮助 .

c++ boost-graph

1 回答

  • 0

    事实证明，使用捆绑属性是实现此目的的最简单方法 . 每个顶点都包含color属性的事实比每次完成dfs时为每个顶点创建color属性更好 . 图表类型应该是

    typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    property<vertex_color_t, boost::default_color_type>
> Graph_T;

    并且对dfv的调用是

    depth_first_visit(
    g,
    vertex(0, g),
    custom_dfs_visitor(),
    get(vertex_color_t(), g),
    Terminator()
);

    有了上述内容，在具有100 M顶点的图形中执行有限的dfs不会增加内存消耗（占总内存的76.2％），而使用外部矢量颜色时内存使用率在搜索时从76.2％增加到78.5％ .

    回复于

相关问题