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 に答える