是否有一种有效的方法来确定叶节点是否可以从有向非循环图中的另一个任意节点访问?

根据您的结构,有几种方法可能速度更快,但一般来说,您需要的是遍历。

深度优先搜索,通过每个可能的路径,跟踪已经访问过的节点。它是一个递归函数,因为在每个节点上,您都必须分支并尝试它的每个子节点。如果你不知道用哪种方法去寻找物体,就没有更快的方法了,你只需要尝试每一种方法!你肯定需要跟踪你已经去过的地方,否则会很浪费。它应该要求按节点数的顺序执行完全遍历。

宽度优先搜索是类似的,但是在“继续”之前访问节点的每个子节点,因此建立了与所选根的距离层。如果希望目标靠近根节点,则速度可能更快。如果期望它沿着一条路径一直走下去的话,速度会慢一些,因为它迫使你穿过每一条可能的边缘。

你说得对,也许你要保留一个已知根节点的列表,但这两者之间的权衡是,你只要改变图表,就必须进行搜索。如果您很少更改图形,这是可以接受的,但是如果您更改图形的频率比生成此信息所需的频率高,那么当然这是非常昂贵的。

编辑:信息更新。 听起来好像我们在寻找两个任意节点之间的路径,根/叶语义一直在切换。depthfirstsearch(df)从一个节点开始,然后针对每个未访问的子节点,递归。如果找到目标节点,则中断。由于递归计算的方式,这将沿着“左”路径一直遍历,然后在此距离枚举节点,然后再转到“右”路径。如果目标节点可能是右侧的第一个子节点,那么这将花费大量时间,而且效率低下。面包第一步一步走,在前进之前把所有的孩子都包起来。因为您的图底部和树一样重,所以这两个图的执行时间大致相同。

当图表处于最底层时,您可能对反向遍历感兴趣。从目标节点开始向上走,因为这个方向的节点相对较少。只要节点的父节点一般比子节点多,这个方向就会快得多。您还可以组合这些方法,一个向上,一个向下,然后比较节点列表,并在中间的某个地方开会。(如果忽略每一步完成的工作量的两倍,这种组合可能看起来最快)。

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

只需对访问的节点进行颜色(跟踪)即可。

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]

对于要计算位数组f(x)的顶点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)的值是其父级值的位或。