boost-graph - 仅通过给定顶点连接的顶点的提升图上的拓扑排序

Question

我有一个代表一组依赖关系的大图。

• A --> B
• A --> C
• B --> F
• C --> G
• D --> E
• E --> L
• F --> H
• F --> 我
• H --> K
• J --> K

给定 B 作为起始节点，结果需要是：BFIHK

我不需要任何其他节点，因为它们无法从 B 到达。

用户可以指定一个节点，我需要收集所有路径和这些路径中的节点并打印这些节点的拓扑排序。

目前我正在通过

1. 创建一个新图表

2. 从给定节点中提取所有出边。

3. 在图中添加这些边。从这些边中获取节点并将它们添加到新图中。

4. 对于步骤 3 中的每个节点，重复 (2) 和 (3)

5. 在该新图上，执行拓扑排序并获取节点的顺序

   有没有其他更好的方法或已知算法来查找节点子集的拓扑类型？

Answer 1

我会研究 depth_first_visit() 函数和 boost 提供的访问者模式。访问者模式允许您在搜索树时检查顶点和边。depth_first_visit() 函数允许您从特定顶点开始 DFS 搜索。