关系数据结构 [英] Data structure for relationships

问题描述

我正在将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

由于可能会有多条路径，最少的关系将被返回，但是有一个关系优先级的警告。如果一个关系具有较高的优先级，则该关系将被添加，并且其余的关系将从那里添加。我正在考虑使用不相交的数据结构，但我不确定。 / p>

任何想法？

谢谢

更多信息 -

值的数量通常小于100，关系小于500.集合是静态的，算法将是一次又一次地找到路径。此外，我没有问这个问题，但不相交数据结构中的算法是否为最有效的？

解决方案

这听起来像你是一个图表。这是一个具有节点和边缘的结构。有许多图书馆和处理图形的工具。 Microsoft 甚至提出了如何处理这些文件。我认为图形很好，在许多情况下非常有用。

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

在您的情况下，您的值是节点和你的关系是边缘。

I am converting a VB6 to C# and I want to make my data structure that holds values and relationships more efficient. In VB I have a collection of values and another collection of relationships between those values with priorities for those relationships. I also have an algorithm that when a set of values is passed to it all relationships required to join those values together is returned. For example, say the values collection contains 1-10 and the relationship collection contains

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

If the input was 1,9,10 the returned relationships would be --

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

Since there may be multiple paths the least amount of relationships would be returned but there is a caveat of relationship priorities. If a relationship has a higher priority then that relationship would be added and the rest of the relationships would be added from there. I am thinking of using a Disjoint-set data structure but I am not sure.

Any ideas?

Thanks

More information --

The number of values would normally be less than 100 and the relationships less than 500. The collections are static and the algorithm will be used again and again to find paths. Also, I did not ask this but would the algorithm in Disjoint-set data structure be the most efficient?

解决方案

It sounds like what you have is a Graph. This is a structure with Nodes and Edges. There are many many libraries and tools that deal with Graphs. Microsoft even put out a paper on how to deal with them. I think graphs are great and extremely useful in many situations.

One big benefit with graphs is the ability to assign priorities to the edges between the nodes. Then when you want to find the path between two nodes, boom, the graph can choose the path with the ideal priority.

In your situation, your values are the nodes and your relationships are the edges.

这篇关于关系数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！