在图中查找组

Question

有什么算法可以让我在图中生成组吗？当我描述组时，我指的是组中的图节点:父节点和子节点。在这样一个群体中，必须有一个家长和至少一个孩子。组在图中用黄色标记。我给出了这两组图。图节点只有在与图的外部最接近的情况下才在组中。图中间的节点对我来说并不重要。

有没有解决这个问题的算法？或者你知道一个接近我的图形问题吗？

​

​

Answer 1

我认为如果一个节点只有一个边，它将是一个组的节点。

因此，首先，找到所有的节点，其中只有一个边。并将该节点与其邻居节点分组。会是你想找的一群人。

最后，如果两个组之间存在一个交点，则将两个组组合起来，并递归地生成一个组。

Answer 2

如果您有一个图，并且需要自己将它分成几个组，或者通过特定的查询，您可以使用DSU算法将选定的节点添加到特定的父节点，这样就可以构建几个组件(组)。