c++ - 使用 boost 在图中查找子节点

Question

我是 boost 库的新手。有什么方法可以使用 boost.find 找到图形的所有子节点吗？或者我可以引用的任何文档来实现它都会有所帮助。我想到了使用 Out_Edge Iterator，因为没有出边意味着子节点。

Answer 1

第一次阅读时，我从字面上理解了你的问题。仅在第二次阅读时，我怀疑您实际上是想寻找叶节点。

寻找子节点

如果您有一个给定的节点(例如，顶点 #5)并且想要列出使用 1 个弧(边)可达的节点，那么这个问题就有意义了。

给定一张图:

boost::adjacency_list<> g(10);

你得到顶点 5 的所有 child 的顶点描述符:

for (auto vd : boost::make_iterator_range(adjacent_vertices(5, g)))
{
    std::cout << "vertex " << vd << " is an out-edge of vertex 5\n";
}

现场演示

为了让事情更有趣一点，让我们生成一个随机图:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <iostream>
#include <random>

int main() {
    boost::adjacency_list<> g;
    std::mt19937 rng { 42 };

    generate_random_graph(g, 10, 20, rng);

    for (auto vd : boost::make_iterator_range(adjacent_vertices(5, g)))
    {
        std::cout << "vertex " << vd << " is an out-edge of vertex 5\n";
    }
}

打印

vertex 1 is an out-edge of vertex 5
vertex 6 is an out-edge of vertex 5

图表是visualized作为:

寻找 Nemo 领先节点

连接一个顶点的边数称为它的度。出边数可以用out_degree查询:

for (auto vd : boost::make_iterator_range(vertices(g)))
    std::cout << "vertex #" << vd << " has out_degree: " << out_degree(vd, g) << "\n";

您会看到这意味着顶点 #1 和 #2 是叶节点。

奖励:

可视化叶节点:Live On Coliru