有关树的算法问题

ppxlqq

给定一棵树


(0,1)
(0,7)
(0,12)
(0,13)
(0,15)
(1,2)
(1,4)
(1,6)
(1,7)
(2,3)
(2,5)
(2,6)
(3,4)
(3,5)
(7,8)
(8,9)
(8,10)
(8,11)
(9,10)
(9,11)
(12,13)
(13,14)
(13,15)


0代表根节点，每一数组代表两节点间有无向边。请问，如何判断某节点是否是另一节点的祖先？谢谢

ank11111

考虑一下这些问题吧：
1, How do you represent a single Node in the Graph?
2, How do you represent a single edge in the Graph?
3, How do you build the Graph from your input?

If there is a path from Node A to Node B, then A is a ancestor of B.

ppxlqq

但是，在我的算法书上写，在一棵以r为根的树中，如果顶点v位于从顶点w到r的一条唯一路径T上，则v被成为w的祖先

关键这里的一条唯一路径我不知该如何处理，谢谢！

ank11111

如果是树(Tree)的话，路径应该是唯一的吧。如果是图(Graph)的话，路径就不一定唯一了。

如果你的每一个节点知道自己的老爸的话，那么从w开始，到w爸，然后w爷爷，……，直到r。如果在中途遇到v了，那么v就是w的祖先了吧。

wanwei

1。深度搜索
2。最小传递闭包算法
3。求出两点间的最短路径，若不为无穷大则成立

mtss123

// record the input pairs.

boolean isAncestor(int a,int b){
  // judge if a is ancestor of b.
  // travel from b to 0
  // return if a is visted
}