是否可以在不访问、过滤、索引等图形中的所有顶点的情况下进行深度或广度优先搜索/访问到 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 可以不使用索引吗?谢谢你的帮助。