代码之家 › 专栏 › 技术社区 › PostMan

多对多关系

bipartite algorithm c#

PostMan · 技术社区 · 15 年前

所以,我需要一些方法来实现网络 (我认为这是正确的术语)在c中#

假设我有以下数据:

Foo1 <-> Bar1
Foo2 <-> Bar1
Foo2 <-> Bar2
Foo2 <-> Bar3
Foo3 <-> Bar2
Foo3 <-> Bar3

我如何实现可以支持这一点的东西?

一种方法是创建一个包含foo和一个bar的类,在我的示例中,我有6个这样的类,每个可能的组合,但是这会使数据加倍。

有了这些数据,我需要能够根据它指向多少条线,以及多少条线指向多少条线等对foo1进行计算。

我不是在寻找答案,我更希望在如何实现这一点上有一些指导,甚至一些链接。

5 回复 | 直到 15 年前

Community CDub 7 年前

您基本上概述了一个图形模型,传统上认为它是“节点”和“边”。但是证券/贷款是有效的。

这类问题有两个经典答案。

这取决于您希望能够对数据提出哪些问题、存储数据的效率以及数据的密度。

例如,如果证券和贷款之间存在30%的可能关系,那么密集的数据结构肯定会有回报。只要保持一个大矩阵:X上的证券,Y上的贷款(X,Y)意味着贷款存在。

如果集合不是很密集,则开始使用“稀疏边缘数据结构”。根据应用程序的不同,您可能会:

任何S对象都有其LS的列表。 { S->L,L,L; S->L; S->L,L,L } .很容易找到S的邻居,但很难找到L的邻居
s对象有ls的列表,ls有s的列表:( S->L,L,L 和 L->S,S,S )使用更多的空间,但同时提供方向性查询。
储存一套( S,L )成对的。很糟糕,除非你需要问“这和我有关系吗?”
存储两者的列表 S、L 和 L,S 以某种方式索引它。这就是我们所说的“让数据库完成工作”。

也见 Data structure for relationships

BobbyShaftoe 15 年前

好吧,在不给出答案的情况下,考虑如何使用二维数组,并从存储边缘信息的角度考虑问题。

Tim Long 15 年前

对我来说,这就像一个关系数据库问题。您所描述的是具有多对多关系的两个表。这个答案是否合适将很大程度上取决于您的数据实际上是什么样子的。前面建议让每个对象包含另一个对象的列表是一种方法,但让我们称之为“spade”或“spade”,这是一个关系数据库。考虑使用ADO.NET实体框架或LINQ等技术将数据定义为关系数据库,并使用LINQ查询数据。

你提到你关心的是让记忆加倍。这同样取决于你的真实数据是什么样子的,但是除非你有大量的数据,否则这可能不会是一个问题。唯一浪费的内存是空内存。使用内存,如果它(a)使问题更容易解决,或者(b)给你更多的灵活性。除非出现性能问题,否则不要优化。

Joe Caffeine 15 年前

每个类都可以有另一个类的类型列表。除非您使用的是值类型,否则不会以这种方式复制数据。交叉引用可能导致内存泄漏。

Steven Sudit 15 年前

乔说的话是正确的。每个贷款都有一个担保实例列表,每个担保都有一个贷款实例列表。诀窍是确保你没有一笔贷款,认为它与证券有关,但该证券不同意。我建议只允许成对执行添加或删除操作,以确保它们是并行执行的。我不知道这将如何导致内存泄漏,因为GC足够聪明来处理这个问题。相比之下,引用计数没有一些技巧就无法处理这个问题。