algorithm - 寻找祖先的算法

Question

这是在考试中被问到的。你能帮我找到解决办法吗？

设计一个算法来查找给定节点（树或图）的祖先数量，使用：

1. O(m) 内存
2. 无限内存大小

Answer 1

假设图中没有循环（在这种情况下，祖先没有意义） DFS-loop 可用于计算任何节点 k 的祖先，只需在每次迭代中标记计数的节点，不要计算访问过的节点两次。

for i in graph visited[i] = false // for DFS

for i in graph counted[i] = false // for ancestors

int globalcount = 0; // count the no of ancestors

for i in graph DFS(i,k) //DFS-loop

def bool DFS(u,k) {   //K is the node whos ancestors want to find


if(!visited[u]) {

visited[u] = true // prevent re-entering

totalret = false // whether there is path from u to k

for each edge(u,v) {

retval = DFS(v)

if(retval&&!counted[u]&&u!=k) {  //there is path from u to k & u is not counted 

  globalcount++

  counted[u] = true

  totalret = true

}

}

if(u == k) return true

else return totalret

}

return counted[u] // if visited already and whether ancestor(k)?
}

print globalcount // total ancestor(k)

空间复杂度：O(V)V：顶点数

时间复杂度：O(E) E：图中没有边

Answer 2

该算法将取决于树的设计。最简单的例子是包含其父节点的节点，在这种情况下它减少到

int ancestors = 0;
while( node = node->parent) ancestors++;

约束不会在任何合理的实现中造成问题。

如果节点不包含父节点，则取决于树的结构。

• 在最复杂的无序树的情况下，它需要一个完整的树搜索，计算祖先。
• 对于搜索树，您只需要进行搜索即可。