1

为具有 n 个节点的树给出一个矩阵 M[n, n]。在给定的矩阵 M 中，如果节点 j 是节点 i 的祖先，则 M[i, j] 为真。从给定的矩阵构造树。

例如，您在下面给出了矩阵。

   1  2  3  4
1  0  1  1  0

2  0  0  1  0

3  0  0  0  0

4  0  1  1  0

您需要构建下面的树。在构造的树上的祖先关系应该是正确的。节点可以位于其父节点的左侧或右侧，因为您无法从祖先矩阵中确定此信息

矩阵中使用的节点编号在括号中
                        5(3)
                         |     
                         |   
                        10(2)
                        / \
                       / \
                   12(1) 13(4)
4

1 回答 1

1

http://en.wikipedia.org/wiki/Topological_sorting有很好的算法，应该适用于这种情况

于 2012-09-17T19:27:37.160 回答