0

我有一个创建图表的程序，如下所示

创建图的结构

该算法从绿色节点开始并遍历图形。假设已将一个节点（具有 4 个引用 Left、Right、Up 和 Down 的链表类型节点）添加到图像中红点描绘的图形中。为了将新创建的节点与其邻居集成，我需要找到四个对象并将其链接起来，以便保留图形连接性。

以下是我需要澄清的

  1. 假设所有黄色节点都是空的，并且我没有保留另一个数据结构来映射节点，这是查找新创建节点的邻居是否存在的最有效方法。我知道基本的图搜索算法，如 DFS、BFS 等和最短路径算法，但我认为这些算法中的任何一个都不够有效，因为图可以有大约 10000 个节点并执行图搜索算法（从绿色节点开始）来找到添加新节点时的邻居对我来说似乎计算成本很高。
  2. 如果无法避免图形搜索，那么最好的替代结构是什么。我想到了一个大型的多维数组。但是，这会浪费内存，并且还存在没有负索引的问题。由于图像中的图形可以向任何方向增长。我对此的解决方案是编写一个单独的类，该类由基于数组的数据结构组成，以描绘负索引。但是，在选择此选项之前，我想知道我是否仍然可以在不解决新结构的情况下解决问题并节省大量返工。

感谢您提供任何反馈并阅读此问题。

4

3 回答 3

1

我不确定我是否理解正确。你想要_____吗

  • 检查是否存在从 (0,0) 到 (x1,y1) 的路径

或者

  • 检查 (x1,y1) 的任何邻居是否在图中？（即使没有从 (0,0) 到任何这个邻居的路径）。

我假设您正在寻找一条路径（否则您不会使用链表），这意味着您无法存储没有到 (0,0) 路径的点。

此外，您提到您不想在 / 旁边使用任何其他数据结构来代替您的 2D 链表。

您无法避免全图搜索。BFS 和 DFS 是经典算法。我认为您不关心最短路径-任何路径都可以。

您可能会考虑的另一种方法是 A*（此处为简单解释）或其变体之一（请看此处）。

另一种数据结构是一组节点（每个节点当然是一对 < x,y >）。您可以轻松地运行 4 次检查以查看它的任何邻居是否已经在集合中。检查和添加都需要 O(n) 空间和 O( logn ) 时间。如果您的编程语言不支持对作为集合的节点，您可以使用单个整数 (x*(Ymax+1) + Y) 来代替。

于 2013-06-29T17:53:46.800 回答
0

您可以使用空间索引，如四叉树或 r 树。

于 2013-06-29T17:38:55.170 回答
0

您的数据结构可以工作，但可能效率不高。这将是很多工作。

使用您当前的数据结构，您可以使用 A* 搜索（有关基本描述，请参见https://en.wikipedia.org/wiki/A *_search_algorithm）来查找指向该点的路径，该路径必然会找到邻居。然后假装你在那一点上有一个小家伙，把他的右手放在墙上，然后让他绕着这个点顺时针找到他的路。当他回来时，他会找到其余的。

我说的顺时针方向是什么意思？例如，假设您从邻居那里往下走以到达他的位置。然后你的家伙应该面对他有一个邻居的右、上和左中的第一个。如果他能向右走，他会，然后他会尝试向下、向右、向上和向左的方向。（想象一下试图用右手在墙上自己穿过迷宫。）

这种方式是精神错乱。

这里有两种更容易使用的替代数据结构。

您可以使用四叉树。有关说明，请参见http://en.wikipedia.org/wiki/Quadtree。通过这种插入，节点在时间上是对数的。寻找邻居也是对数的。而且您仅将空间用于您拥有的数据，因此即使您的图表非常分散，这也是内存效率。

或者，您可以为具有正索引和负索引的数组类型创建一个类。然后是一个基于它的二维类，它同时采用正索引和负索引。在引擎盖下，该类将被实现为常规数组和偏移量。所以一个数组可以从某个数字开始，正数或负数。如果您尝试在偏移量之前插入一条数据，您将创建一个新的偏移量，该偏移量低于该块的固定部分的数组长度，创建一个新数组，并将数据从旧的复制到新的。现在通常插入/查找邻居，O(1)但这可能非常浪费内存。

于 2013-06-29T17:43:55.413 回答