使用 boost 在图中查找子节点

Question

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

Answer 1

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

寻找Child个节点

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

给定一张图：

boost::adjacency_list<> g(10);

你得到顶点 5 的所有 children 的 vertex-descriptors:

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

使用 boost 在图中查找子节点

Find the child nodes in a graph using boost

c++

boost

graph

boost-graph

寻找Child个节点

现场演示

寻找 Nemo 领先节点

奖金：