4

如果这是此问题的错误 stackexchange 网站，请在其他地方指导我！

我有一个规则的二维节点网格。我还想存储有关网格节点之间边缘的数据，但我不确定如何以有效的方式执行此操作。

我立即想到的三个想法都有缺点，我不确定哪个更可取，或者是否确实有更好的方法。

  1. 将边缘数据存储在二维数组中。由于图节点本质上是一个二维数组，你可以简单地将边数据存储在一个普通的二维数组中——0,0 是左下节点，1,0 是它的右边，而 0,1 是直接“上面”它等等。

这种方法的问题是数据重复——关于 0,0 和 0,1 之间的边的数据存储在两个不同的位置。每当需要更新数据时，您都需要在两个地方都更新它，当然，您有额外的内存开销，因为您可能需要保存两倍的数据（即使其中一半是重复的）

  1. 仅将“顶部”和“左侧”边缘存储在二维数组中。这是方法 1 的扩展，可避免存储冗余数据。但是，这使得检索和存储数据变得更加困难，因为您现在需要 3 次调用来收集或设置节点的所有边（x,y；x+1,y；和 x,y-1）。

  2. 使用dictionary<<<x,y>,<x,y>>,Edge>字典（点元组）来存储和检索关于图中两个节点之间的边的数据。

这避免了冗余，但字典查找比数组慢，并且不可能一次获得所有 4 条边（接受一个节点并返回 4 条边的字典可以解决后者，但会重新引入冗余问题）。出于我的目的，我主要对一小组节点之间所有可能的边感兴趣，因此不检索所有节点并不是一个大问题。

现在，我倾向于方法#1，只是吸收和处理冗余数据。有没有更好的方法来存储/检索有关边缘的数据，或者这是最好的方法。

示例 - 在 Edge 中存储颜色：

在此处输入图像描述

4

2 回答 2

1

另一种选择是制作一个大的一维边缘对象列表，然后将它们适当地链接到节点。例如，您的节点类可能有TopEdge、LeftEdge、BottomEdge和RightEdge成员，每个成员都是对边缘列表中某个对象的引用。

最初设置这可能有点复杂，但可以避免数据重复并提供从节点对适当边缘的轻松访问。

如果您想要更正式的解决方案，您可能还想阅读图论。

于 2012-12-30T04:00:41.727 回答
1

假设一切都适合内存并且您的边缘不是非常稀疏，我会选择“仅将“顶部”和“左侧”边缘存储在二维数组中”，因为它可能具有您列出的选项的最佳缓存性能。

但是，这使得检索和存储数据变得更加困难，因为您现在需要 3 次调用来收集或设置节点的所有边（x,y；x+1,y；和 x,y-1）。

我不明白你这是什么意思。一切都应该封装在一个类中，以方便使用的接口。如果您发现自己需要设置节点的所有边，请编写一个方法来执行此操作。

于 2012-12-30T05:02:59.350 回答