1

我想将图表拆分为其组件(如下面的示例 DAG 所示。请注意每个节点的彩色标识符,因为它们代表组件)。在我找到图片中的组件后,我想找到该组件的根和最后一个子组件。以蓝色组件为例,根是E,最后一个子是H绿色:根B- 最后一个孩子H

示例图: 示例图

E如果您可以在- H, B- E, B- H, A-之间找到连接,I而无需将其拆分为组件。让我知道,因为这是我的最终目标。

关于组件的编译。这实际上是我的最终目标。我只是想将其包括在内,以使您更好地了解我要实现的目标。一旦我找到这些联系,就不可能了。

我发现有帮助但没有回答我的问题的问题:

(这些答案可能就足够了,但我不知道如何实现它)

笔记:

  • 请以 C++ 或 C# 发布所有示例代码(如果您要发布示例代码)

  • 这是我的第一个问题。如果我做错了什么,请告诉我。

// 大编辑:重做问题,使其更清楚我想要什么。引入组件,因为我可能认为这会更有帮助。

4

1 回答 1

0

评论太长了,但我认为您找不到所有共同的祖先:

来自维基百科

在图论和计算机科学中,两个节点的最低共同祖先 (LCA)v和树或有向无环图 (DAG) 是具有和作为后代w的最低(即最深)节点,我们将每个节点定义为自身的后代(因此,如果与 有直接联系,则为最低共同祖先)。vwvww

如果您考虑父母的 LCA,则有 4 个顶点的父母,HC, DF然后G您可以将 LCA 视为任何一对父母的值:

  • LCA( C, D ) = B
  • LCA( C, F ) = C
  • LCA( C, G ) = C
  • LCA( D, F ) = D
  • LCA( D, G ) = D
  • LCA( F, G ) = E

因此,的父母的 LCAHBC和。DE

共同祖先将是最低的共同祖先及其祖先 -所以ABC和。DE

您需要解决原因AC并且D被排除在共同祖先之外。

于 2016-04-28T10:43:22.300 回答