2

在许多图形算法中，所需结果的连接通常存储在parent数组中。

例如，在 BFS 或 DFS，或最小生成树，或最短路径中，我们将每个顶点的父节点存储在parent[].

我的问题是，如果我只有这样一个parent[]，我怎样才能轻松地获得任意顶点之间的路径，比如说，在 O(n) 中？请注意，它是 BFS 或 DFS 或其他东西并不重要，重要的是parent[]我从图形算法中得到的唯一。

如果其中一个顶点是另一个顶点的祖先，我可以轻松获得路径，否则我只能从一个顶点追溯到parent[]根，然后对另一个顶点再次执行此操作，然后检查它们的路径在哪个祖先（到根）合并。这导致 O(n^2) 因为我必须将一个顶点的每个祖先与另一个顶点的每个祖先进行比较以寻找合并点。

任何人都可以帮忙吗？

4

6 回答 6

5

如果您使用大小为 N 的布尔数组 A，则可以消除寻找合并点的复杂性，当您从顶点 i 到根时，沿途为每个顶点标记 A[i] = true。当你从顶点 j 到根时，如果 A[i] == true，那就是合并点（第一个这样的顶点）。

于 2012-05-02T11:56:07.923 回答
3

这个问题听起来像是从两个相交的链表中找到相交节点的问题。请检查此解决方案从两个相交的链表中查找相交节点

于 2012-05-02T11:57:06.103 回答
1 
// print the path between v1 and v2
w1 = v1
while w1 != root:
  ++n
  w1 = w1.parent

w2 = v2
while w2 != root:
  ++m
  w2 = w2.parent

if (m < n):
  swap(v1, v2)
  swap(m, n)

(m - n) times do:
  print v2
  v2 = v2.parent

while v1 != v2:
  print v2
  stack.push(v1)
  v1 = v1.parent
  v2 = v2.parent

while not stack.empty:
  print stack.pop
于 2012-05-02T11:55:07.173 回答
1

在树中找到 , 之间的路径x：您 可以及时执行此操作，“k”是它们之间最短路径的长度。而不是在每个节点中存储一个值为 0 的整数 aux。yT
O(k)O(n)

Climb up `x`'s and `y`'s ancestors simultaneously.  
Make each of `x`'s ancestors' aux = aux + 1  
Make each of `y`'s ancestors' aux = aux + 2

用z它们之间的第一个共同祖先表示。请注意，xz连接的路径zy将为您提供最短路径xy。

如果y' 的祖先有 aux=3 或如果x' 的祖先有，那么你已经达到z.

当其中一个是另一个的祖先时，您可能必须解决这个问题......此外，按顺序打印顶点可能需要您将x' 的祖先放入堆栈中并将y' 的祖先放入队列中并且然后在最后弹出它们。

于 2012-09-14T23:11:39.147 回答
0

正如您所说，您可以轻松获取从根到任何顶点的路径。如果您需要任何其他顶点的路径，则必须以该顶点为根重新开始搜索。这不是一种O(n)方法，但它似乎是你能得到的最好的方法。（考虑沿某条边的路径与沿同一边向后的路径的权重不同或根本不存在的情况。）

于 2012-05-02T11:23:31.500 回答
0

最简单的方法是使用堆栈。像这样的东西：

def getpath(parent, first, last):
     path = []
     while first != last:
         if last == None: # there isn't a path between first and last
             return None
         path.append(last)
         last = parent[last]
     path.append(first)
     path.reverse()
     return path
于 2012-05-02T11:32:21.423 回答