一尘不染

关系的数据结构

algorithm

我正在将VB6转换为C#,我想使保存值和关系的数据结构更有效。在VB中,我具有值的集合以及这些值之间的关系的另一个集合,这些关系具有优先级。我还有一种算法,当将一组值传递给它时,会返回将这些值连接在一起所需的所有关系。例如,说值集合包含1-10,关系集合包含

1,2
3,2
5,2
2,8
8,10
9,10

如果输入为1,9,10,则返回的关系为-

1,2
2,8
8,10
9,10

由于可能存在多条路径,因此将返回最少数量的关系,但是存在关系优先级的警告。如果关系具有更高的优先级,则将添加该关系,然后从那里添加其余关系。我正在考虑使用不交集数据结构,但不确定。

有任何想法吗?

更多信息 -

值的数量通常小于100,关系小于500。这些集合是静态的,该算法将一次又一次地用于查找路径。另外,我没有问这个问题,但是不相交集数据结构中的算法是否最有效?


阅读 199

收藏
2020-07-28

共1个答案

一尘不染

听起来您拥有的是Graph。这是具有节点和边缘的结构。有许多处理图的和工具。微软甚至发布了有关如何处理它们的论文。我认为图表很棒,并且在许多情况下非常有用。

图的一大好处是能够为节点之间的边缘分配优先级。然后,当您想找到两个节点(繁荣)之间的路径时,图形可以选择具有理想优先级的路径。

在您的情况下,值是节点,关系是边。

2020-07-28