我在创建基于关系的程序时遇到了一些麻烦,我需要的是创建一个函数来将相关节点聚合在一起,就像这样,如果我有这 4 个节点:
如果A -> B,B -> C,C -> D,A -> C,B -> D,像这样: 节点
当 A -> D 时,我想创建一个中间节点,用从每个节点到这个新节点的单个连接替换这些节点之间的所有关系。像这样:
@<- cluster
A ->@、B -> @、C -> @、D -> @
因此,无论谁连接到@,都与它的所有成员都有关系
这是为了避免 5x5、10x10、25x25 的关系,这些关系对内存来说确实很重。
我通过几个步骤实现了这个目标,首先我计算两个必须连接的公共节点,如果这些公共节点> 5,那么我将它们聚集在一个组中并删除它们的连接。
此外,当连接被删除时,这意味着在某个下限下,必须拆除集群并且必须重新创建节点之间的所有单一关系,
如果普通用户> 100,这种方法可能很危险。
我想知道是否有人可以帮助我做这样的事情,例如在合理的时间内创建集群或拆除集群,因为现在我的技术是 O(n) 并且非常消耗资源
提前谢谢您
我认为你所说的“簇”就是图论中所谓的“直接图中的强连通分量”https://en.wikipedia.org/wiki/Strongly_connected_component
你要求比 O(n) 更好的性能,但你没有说出 n 是什么。 也许是节点数量? 查找强连通分量的最佳算法是 O(V+E),其中 V 是节点数,E 是连接数。 所以你所要求的是不可能的。