有关树的算法问题

Question

给定一棵树
(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代表根节点，每一数组代表两节点间有无向边。请问，如何判断某节点是否是另一节点的祖先？谢谢

Answer 1

考虑一下这些问题吧：
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.

Answer 2

但是，在我的算法书上写，在一棵以r为根的树中，如果顶点v位于从顶点w到r的一条唯一路径T上，则v被成为w的祖先关键这里的一条唯一路径我不知该如何处理，谢谢！

Answer 3

如果是树(Tree)的话，路径应该是唯一的吧。如果是图(Graph)的话，路径就不一定唯一了。如果你的每一个节点知道自己的老爸的话，那么从w开始，到w爸，然后w爷爷，……，直到r。如果在中途遇到v了，那么v就是w的祖先了吧。