3

维基百科：有向无环图

不确定叶节点是否仍然是正确的术语，因为它不是真正的树（每个节点可以有多个子节点，也可以有多个父节点），而且我实际上正在尝试找到所有根节点（这实际上只是语义问题，如果你反转所有边的方向，它们将是叶节点）。

现在我们只是遍历整个图（可以从指定的节点访问），但这有点贵，所以我想知道是否有更好的算法来做这件事。我在想的一件事是我们跟踪已经访问过的节点（在遍历不同的路径时）并且不重新检查这些节点。

还有其他算法优化吗？

我们还考虑过保留一个该节点是其后代的根节点的列表，但如果我们需要检查它是否在每次添加、移动或更改节点时都发生变化，那么维护这样一个列表似乎也会相当昂贵。删除。

编辑：

这不仅仅是查找单个节点，而是查找作为端点的所有节点。

也没有节点的主列表。每个节点都有一个它的子节点和它的父节点的列表。（嗯，这并不完全正确，但是提前从数据库中提取数百万个节点的成本非常高，并且可能会导致 OutOfMemory 异常）

编辑2：

可能会或可能不会改变可能的解决方案，但该图是最底层的，因为最多有几十个根节点（我试图找到）和数百万个（可能是数千万或数亿个）叶节点（我'我开始）。

4

3 回答 3

3

有几种方法可能会更快，具体取决于您的结构，但总的来说，您需要的是遍历。

深度优先搜索，遍历每条可能的路线，跟踪已经访问过的节点。这是一个递归函数，因为在每个节点上，您必须分支并尝试它的每个子节点。如果您不知道以哪种方式查找对象，则没有更快的方法，您只需尝试每种方式！你肯定需要跟踪你已经去过的地方，否则会很浪费。它应该要求按节点数量的顺序进行完全遍历。

广度优先搜索类似，但在“继续”之前访问节点的每个子节点，因此会建立与所选根的距离层。如果预计目的地靠近根节点，这可能会更快。如果预计它会一直沿着一条路径前进，那么它会更慢，因为它会迫使您遍历所有可能的边缘。

您可能保留一个已知根节点的列表是对的，但权衡是您基本上必须在更改图形时进行搜索。如果您很少更改图表，这是可以接受的，但如果您更改图表的频率超过了生成此信息所需的频率，那么成本当然太高了。

编辑：信息更新。听起来我们实际上是在寻找两个任意节点之间的路径，根/叶语义不断切换。DepthFirstSearch (DFS) 从一个节点开始，然后对每个未访问的子节点进行递归。如果找到目标节点，则中断。由于递归评估的方式，这将一直沿着“左”路径遍历，然后在到达“右”路径之前枚举该距离处的节点。如果目标节点可能是右边的第一个子节点，那么这是耗时且低效的。广度优先一步一步走，在继续前行之前覆盖所有孩子。因为您的图表像树一样底部很重，所以两者的执行时间大致相同。

当图表底部很重时，您可能对反向遍历感兴趣。从目标节点开始往上走，因为这个方向的节点相对较少。只要节点的父节点通常比子节点多，这个方向就会快得多。你也可以结合这些方法，一个上一个下一个，然后比较节点列表，然后在中间的某个地方会面。（如果您忽略每一步完成两倍的工作，这种组合可能看起来最快）。

但是，由于您说您的图表存储为子列表列表，因此您没有真正的方法可以向后遍历图表。一个节点不知道它的父节点是什么。这是个问题。要修复它，您必须通过在图形更新中添加该数据或通过创建整个结构的副本（您所说的太大）来让节点知道它的父节点是什么。它将需要重写整个结构，这听起来可能是不可能的，因为此时它是一个大型数据库。有很多工作要做。 http://en.wikipedia.org/wiki/Graph_(data_structure)

于 2009-05-28T15:59:50.087 回答
2

只需着色（跟踪）访问的节点。

Python中的示例：

def reachable(nodes, edges, start, end):
  color = {}
  for n in nodes:
    color[n] = False
  q = [start]
  while q:
    n = q.pop()
    if color[n]:
      continue
    color[n] = True
    for adj in edges[n]:
      q.append(adj)
  return color[end]
于 2009-05-28T15:50:01.977 回答
0

对于一个顶点x，你想计算一个位数组f(x)，每个位对应一个根顶点Ri，1(resp 0)表示“x可以(resp不能)从根顶点Ri到达。

您可以将图形划分为一个“上”集合 U，其中包含所有目标根 R，如果 x 在 U 中，则 x 的所有父级都在 U 中。例如，距离最近的 Ri <=D 的所有顶点的集合.

保持 U 不要太大，并为 U 的每个顶点 x 预先计算 f。

然后，对于查询顶点 y：如果 y 在 U 中，则您已经有了结果。否则，递归地对 y 的所有父节点执行查询，缓存每个访问顶点 x 的值 f(x)（例如在地图中），因此您不会计算两次值。f(y) 的值是其父值的按位或。

于 2009-06-02T13:26:31.723 回答