c++ - 在没有 O(number_of_vertices) 使用内存或时间的情况下，BGL 中的有限深度搜索？

Question

是否可以在不访问、过滤、索引等图形中的所有顶点的情况下，进行深度或广度优先搜索/访问距 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) 降低同一图形中每个单独搜索的复杂性？当 Terminator 返回 true 时，顶点的初始着色也有望停止，但这似乎已经得到处理。也许是一个相关的问题:如果图形使用 vecS 之外的其他东西，那么索引呢？在这种情况下，BFS/DFS 可以不用索引吗？感谢您的帮助。

Answer 1

事实证明，使用捆绑属性是实现这一目标的最简单方法。颜色属性包含在每个顶点中的事实比每次完成 dfs 时都为每个顶点创建颜色属性要好。图形类型应该是

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()
);

综上所述，在具有 1 亿个顶点的图形中执行有限的 dfs 不会增加内存消耗(占总内存的 76.2%)，而使用外部颜色 vector 时，搜索时内存使用量从 76.2% 增加到 78.5%。