c++ - 提升图的级别有序遍历

Question

我是boost图形库的新手，给定一个有向图，我想构建一个顶点的水平有序向量，即给定顶点A,B,C,D,E,F和边

A->B、A->C、B->D、C->E 和 E->F

得到一个顶点向量，这些顶点在图中（或树）中处于相同深度：

[[A]、[B、C]、[D、E]、[F]]

谢谢你的帮助。

Answer 1

你试过什么了？

这是关于我如何解决这个问题的一般性高级描述。

1. 创建一个数据结构来保存“级别有序向量”

2. 创建一个持有此结构的访问者和一个当前深度计数器

3. 从 A 开始进行图形遍历，使用 A 的深度和当前节点在“级别有序向量”中的正确位置更新访问者

另一种方式：

1. 使用捆绑属性功能保存每个节点的深度

2. 遍历图形，使用正确的深度更新节点属性。

3. 根据上一步中遍历设置的深度属性，遍历节点以确定每个节点应放置在“级别有序向量”中的哪个位置。

作为参考，这里是广度优先遍历方法http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/breadth_first_search.html