Boost Graph: 遍历树到单个叶子节点的算法

Question

这是我想要实现的目标：

• 我有一个固定的图形，其结构类似于树的根：单一头部，向下多个级别，大多数级别具有单个节点，某些级别具有兄弟节点。没有循环分支。
• 在每次运行时，我想要从头部遍历图形直到遇到第一个叶子节点。
• 在随后的运行中，我希望再次遍历，但在每个级别上使用交替分支。分支切换从顶部开始，然后向下传播。
• 在每个级别上，我希望对遍历命中的节点执行操作。没有任何操作会修改图形。

我可以从头开始做，但我认为 Boost Graph 最有可能成为我的好帮手。但是，有太多不同的结构和仅专家才理解的算法名称。

您是否知道 Boost Graph 中是否已经存在我想要做的（如上所述）？

- Maitre Bart

---

“我想再次遍历，但每个级别都使用交替分支”，你所说的“每个级别”是什么意思？当在第一层选择不同的分支时，其他层的分支就不能与先前的遍历相同了... - trincot

Answer 1

您的要求似乎有矛盾之处：

每次运行，我想从头到第一个遇到的叶子节点遍历图形。

• 这正是深度优先遍历（DFS）的典型特征

在随后的运行中，我想再次遍历，但在每个级别上使用交替分支。 分支切换从顶部开始然后向下传播。

• 这是广度优先遍历（BFS）的典型特征

我可以向您展示使用Boost的标准BFS / DFS，但如果您想要自己的混合算法，您可能必须自己编写它。 我猜您实际上想要BFS¹

代码

• 我有一个固定的图形，其结构类似于树的根：单个头部，多个级别向下，大多数级别具有单个节点，某些级别具有兄弟节点。 没有循环分支。

auto make_graph() {
    enum { root, a, b, c, d, e, f, g, h, i, j };
    boost::adjacency_list<> graph(j+1);
    add_edge(root, a, graph);
    add_edge(root, b, graph);
    add_edge(root, c, graph);
    add_edge(a,    d, graph);
    add_edge(a,    e, graph);
    add_edge(d,    f, graph);
    add_edge(b,    h, graph);
    add_edge(h,    i, graph);
    add_edge(i,    j, graph);
    return graph;
}

这对应于

进行遍历：

最简单的BFS是：

int main() {
    Graph const graph = make_graph();

    boost::default_bfs_visitor vis;

    std::vector<boost::default_color_type> colors(num_vertices(graph));
    boost::breadth_first_visit(graph, Vertex{ root },
        boost::visitor(vis).color_map(colors.data()));
}

这里使用默认的访问器，实际上什么也没有做。

您可以覆盖任何事件，例如：

struct Vis : boost::default_bfs_visitor {
    void discover_vertex(Vertex u, Graph const&) {
        std::cout << "Discover " << names[u] << "\n";
    }
    void examine_vertex(Vertex u, Graph const& g) {
        if (0 == out_degree(u, g)) {
            std::cout << "Examine Leaf Node " << names[u] << "\n";
        }
    }
    using Edge = Graph::edge_descriptor;
    void tree_edge(Edge e, Graph const& g) const {
        auto a = source(e, g);
        auto b = target(e, g);
        std::cout << "Tree edge " << names[a] << " -> " << names[b] << "\n";
    }
} vis;

当所有启用时，将打印出：

Discover root
Tree edge root -> a
Discover a
Tree edge root -> b
Discover b
Tree edge root -> c
Discover c
Tree edge a -> d
Discover d
Tree edge a -> e
Discover e
Tree edge b -> h
Discover h
Examine Leaf Node c
Tree edge d -> f
Discover f
Examine Leaf Node e
Tree edge h -> i
Discover i
Examine Leaf Node f
Tree edge i -> j
Discover j
Examine Leaf Node j

这里是所有事件的完整文档：https://www.boost.org/doc/libs/1_73_0/libs/graph/doc/BFSVisitor.html。

---

¹（因为即使第一个叶子节点仍然会首先被报告，它正在访问其他节点的事实可能不可观察）

- sehe

---

谢谢。现在我有一些提示可以深入研究了。 - Maitre Bart