有没有一种有效的方法来确定在有向无环图中，一个叶节点是否可以从另一个任意节点到达？

Question

维基百科：有向无环图

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

现在我们只是遍历整个图（从指定节点可达的部分），但这证明是相当昂贵的，所以我想知道是否有更好的算法来做这件事。一个想法是我们记住已经访问过的节点（在遍历不同路径时）并且不再重复检查它们。

还有其他算法优化吗？

我们还考虑过保留此节点是后代的根节点列表，但似乎如果需要检查每次添加、移动或删除节点时是否更改了这样的列表，维护这样的列表也会相当昂贵。

编辑：

这不仅仅是找到单个节点，而是找到所有端点节点。

此外，没有节点的主列表。每个节点都有其子节点和父节点的列表。 （嗯，这并不完全正确，但是从DB中提取数百万个节点的存储开销非常昂贵，并且可能会导致OutOfMemory异常）

编辑2：

也许会改变可能的解决方案，但该图形具有底部重量级，即最多有几十个根节点（我正在寻找这些节点），以及一些数百万（可能是数十亿或数亿）的叶节点（我从哪里开始）。

- Davy8

---

DAG可以有叶节点。叶节点只是没有扇出的节点。 - ConcernedOfTunbridgeWells

Answer 1

有几种方法，每种方法都可能更快，具体取决于您的结构，但通常您需要的是遍历。

深度优先搜索会通过每个可能的路径，并跟踪已经访问过的节点。它是一个递归函数，因为在每个节点上，您必须分支并尝试其每个子节点。如果您不知道要查找对象的方向，那么没有更快的方法！您绝对需要跟踪您已经访问过的地方，否则会很浪费。完成完整遍历应该需要与节点数同级别的时间。

广度优先搜索类似，但会在“前进”之前访问每个节点的每个子节点，因此会建立起从所选根节点的距离的层次结构。如果目标预计靠近根节点，则这可能更快。如果预计目标位于整条路径的尽头，则较慢，因为它强制您遍历每个可能的边缘。

您的想法可能是保留已知根节点列表，其中的权衡是每当您更改图形时，您基本上必须执行搜索。如果您很少更改图形，则可以接受此操作，但如果您比需要生成此信息更频繁地更改图形，则显然成本太高。

编辑：信息更新。 听起来我们实际上正在寻找两个任意节点之间的路径，根/叶语义一直在变化。深度优先搜索（DFS）从一个节点开始，然后对于每个未访问的子节点，递归。如果找到目标节点，则中断。由于递归计算的方式，这将遍历整个“左”路径，然后枚举此距离的节点，然后才能到达“右”路径。如果目标节点可能是右侧第一个子节点，则这很耗时且效率低下。广度优先搜索按步骤走动，覆盖所有子节点，然后向前移动。由于您的图形类似于树形结构，因此两者的执行时间将大致相同。

当图形底部较重时，您可能会对反向遍历感兴趣。从目标节点开始向上行走，因为在这个方向上的节点比较少。只要节点通常具有更多的父节点而不是子节点，这个方向就会快得多。您还可以结合这些方法，向上和向下各步进一次，然后比较节点列表，并在中间汇合。（如果忽略每个步骤需要做两倍的工作量，这种组合可能看起来最快）。

然而，鉴于您说过您的图以孩子列表的列表形式存储，您无法真正遍历图的反向部分。节点不知道其父节点是什么，这是一个问题。要解决此问题，您需要在更新图表时为节点添加其父节点信息，或创建整个结构的副本（您已表示该结构太大）。对于后一种情况，需要重写整个结构，由于它是一个大型数据库，这听起来可能不太可行。还有很多工作要做。 http://en.wikipedia.org/wiki/Graph_(data_structure)

- Karl

---

好的，我们需要大约阅读这些信息三倍于图表变化的频率（非常粗略的估计），但由于我刚刚编辑过，图表更加底部重，我正在寻找顶部的节点。 - Davy8

这变得越来越复杂了。你是从叶子开始寻找根，还是从根开始寻找叶子？过程会有所不同，而你已经两者都问了……我们是在寻找两个任意节点之间的路径吗？那可能是一个更清晰的解决方案。 - Karl

抱歉造成困惑，我从一个任意节点开始寻找所有根节点（不关心路径）。 - Davy8

重点是我不是在寻找一个特定的节点，而是在寻找所有根节点（即没有父节点的节点，每个节点可能有多个父节点），这些根节点可以从指定的节点到达。除了节点的子节点和父节点的对象引用之外，我没有任何其他节点信息。 - Davy8

（没有关于图中任何其他节点的信息） - Davy8

很好，你有一个节点父级列表，这样你就可以向上遍历。由于你需要多个根节点，所以你将不得不进行大量的遍历，而且你总是可以朝一个方向前进，如果两条路径合并（访问的节点再次出现），你可以忽略它，并让另一条路径来处理它。只需要几个全局列表即可。 - Karl

Answer 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]

- lispmachine

---

+1 是可行的，但这些节点是我们的业务对象，我们需要在完成后取消所有节点的颜色。我已经提到过要跟踪已访问的节点。 - Davy8

包含颜色数据的结构体不必成为业务对象的一部分。对于每个算法保留附加数据会很繁琐（也不安全）。将这些对象简单地映射到布尔值（例如上面的字典）就足够了。 - lispmachine

好的观点。另一件事是，正如我在我的编辑中提到的（不确定你是否看到了），我没有所有节点和边的列表，我只有单个节点，每个节点都有一个父节点列表，我需要递归遍历它们。我猜这只是传递“颜色”列表的问题。 - Davy8

Answer 3

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

您可以将图分成一个包含所有目标根R的“上部”集合U，如果x在U中，则x的所有父节点都在U中。例如，距离最近的Ri小于等于D的所有顶点的集合。

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

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

- Eric Bainville