一棵树，其中每个节点可以有多个父节点

Question

这是一个理论/迂腐的问题：想象一下每个属性都可以由多个其他属性拥有的属性。此外，从一次所有权迭代到下一次所有权迭代，两个相邻的所有者可以决定部分合并所有权。例如：

territory 1, t=0: a,b,c,d
territory 2, t=0: e,f,g,h

territory 1, t=1: a,b,g,h
territory 2, t=1: g,h

也就是说，

c

和

d

不再拥有财产；可以这么说，

g

和

h

变成了肥猫。

我目前将此数据结构表示为一棵树，其中每个孩子可以有多个父母。我的目标是将其塞入组合设计模式中；但我在概念上遇到问题，无法了解客户如何返回并更新以前的所有权而不弄乱整个结构。

我的问题是双重的。

1. 简单：这个数据结构的一个方便的名称是什么，以便我可以自己用谷歌搜索它？

2. Hard：我做错了什么？当我编码时，我试图在脑海中保留“保持简单，愚蠢”的口头禅，但我觉得我正在打破这个信条。

Answer 1

我的问题有两个：简单：此数据的方便名称是什么 这样我就可以自己用谷歌搜索的结构？

这里的不是一棵树，而是一张图。多重地图将在这里为您提供帮助。 但任何邻接表或邻接矩阵都会给你一个好的开始。

这是有关邻接矩阵和列表的视频：有关邻接矩阵和列表的 Youtube

Hard：我做错了什么？

这个真的很难说。也许你没有为这种关系建模 以适当的方式。只要有一个良好的数据结构就可以开始，这并不难。

并且，当您询问设计模式时（但您可能自己发现了）， 复合模式将让您轻松地对此类设置进行建模。

Answer 2

您的所有者和您的领地（财产）之间存在“多对多关系”。我不确定您使用的是什么语言，但是这种事情可以在关系数据库中轻松表示和跟踪。 （您可能需要每个实体都有一个表，并且关系可能需要第三个“联结”表。如果需要能够查询“回到过去”，则可能有某种“时间索引”列也是。） 如果您使用面向对象的语言，您可能会创建两个类，Territory 和 Owner，其中 Territory 类有一个属性/成员/字段，它是对 Owners 的引用/指针的集合，而 Owner 类有一个类似的属性/成员/字段。领土的集合。 （这两个集合之一可能需要包含“弱”引用，具体取决于语言。）

在这种情况下，如果您希望能够及时返回并查看某个特定时间点的网络状态，可能会出现一些困难。 （如果这是您需要的，请说出来，我（或其他人）可以发布适用于该问题的解决方案。）

我不确定您正在努力追求什么程度的简单性，但是在这两种情况下，更新所有权关系都不是那么“困难”。也许如果您发布了一些代码，可能会更容易为您提供更具体的建议。

Answer 3

常见的结构是

有向无环图

。这里的基本规则是，图中的任何路径都不能循环回到自身。例如，采用路径 "A/B/C/B"，这将无效，因为 B 重复两次。

有效：-

"A/B/C"
1. 、

   "D/E/C"

   、节点

   C

   有两个父节点

   E

   和

   B

   。无效：-
"A/B/C/B"
2. ，节点

   B

   在同一路径中重复，导致循环。

Answer 4