c++ - 具有优先队列的 BGL DFS 访问者

Question

我有一棵树(在图形意义上)表示一棵树(在物理意义上)。树表示为 BGL 邻接列表，其中每个顶点包含半径和位置属性，即，我的图以以下形式定义

struct TreeVertexType {
  double radius;
  double position[3]; 
}

typedef adjacency_list<vecS, vecS, undirectedS, TreeVertexType> Tree;

我想对树执行 DFS 以创建分支列表。附加要求是，每当一个顶点有多个未探索的相邻顶点时，它会选择具有最大半径的顶点。此规则确保图的遍历顺序代表物理树分支。

似乎 DFS 访问者不支持优先级队列，所以我想知道是否有其他搜索公式可以通过 A* 获取此信息？

或者，我可以通过对顶点进行排序来实现我自己的 DFS 算法，但如果可能的话，我宁愿利用 BGL 框架。

谢谢

-约翰

Answer 1

在 DFS 期间，boost::graph 使用堆栈压入相邻顶点，这些顶点将按照压入顺序稍后弹出。

std::vector<VertexInfo> stack;//depth_first_search.hpp 的第 94 行 boost_1_47_0

作为解决方法，您可以重新定义这个stack使用相同的 push() 和 pop() 接口(interface)，您可以在任何 Vertex 时执行操作被插入stack只需对 your stack 的元素进行排序半径最大的顶点总是在顶部。

换句话说，用您自己的优先级队列伪造一个堆栈接口(interface)。

这将使您免于编写自己的 DFS 的痛苦。