3

初めまして、タイトル失礼します。誰かがより良いものを提案してください。質問を適切に表現する方法が本当にわかりませんでした。

基本的に、要素が次のように見えるデータ構造の名前を探しているだけです (ドットは無視してください)。

……5

....3...2

...4...1...6

9...2...3...1

最初はある種の「木」ではないかと思ったのですが、ウィキペディアには次のように書かれています。

ツリーは [...] 非巡回接続グラフであり、各ノードには 0 個以上の子ノードと最大 1 つの親ノードがあります

私が探しているデータ構造には、ノードごとに複数の親が存在する可能性があるため、おそらくツリーではありません。

だから、ここに私の質問があります：

次の要素間のリンクでデータを表現できるデータ構造の名前は? (/ と \ はリンクです。ドットは無視してください):

……5

...../..\

....3...2

.../..\./..\

...4...1...6

../.\./..\./..\

9...2...3...1

4

4 に答える 4

4

「ダイグラフ」（有向グラフ）の方が適切な用語ですが、ツリーと呼ぶのは完全に間違っているとは思いません。

初めまして、タイトル失礼します。誰かがより良いものを提案してください。質問を適切に表現する方法が本当にわかりませんでした。

タイトルは結構です。質問を開いたとき、私は一生懸命笑っていました。私は今それらを「ボウリングピン」と呼び始めるつもりです:)

代替テキスト

      5

    3   2

  4   1   6

9   2   3   1
于 2010-08-22T03:38:30.010 に答える
3

このようにレイアウトされた最も人気のあるものは、パスカルの三角形です。二項係数の計算に使用される構造です。各ノードは、その親の合計です。

http://info.ee.surrey.ac.uk/Personal/L.Wood/publications/MSc-thesis/fig36.gif .

通常、そのようなアルゴリズム (そのようなクラスは一般に「動的プログラミング」と呼ばれます) を実装する場合、この「構造」は通常、単純な 2 次元配列として表されます。たとえば、ここを参照してください。

n\k  0  1  2  3  4
------------------
0    1  0  0  0  0 
1    1  1  0  0  0 
2    1  2  1  0  0 
3    1  3  3  1  0 
4    1  4  6  4  1 
5    1  5 10 10  5 
6    1  6 15 20 15

そのような構造には正式な名前はないと思いますが、動的プログラミングでは、そのようなものは単なる配列です。

しかし、これからは、NullUserException が示唆するように、私はそれを完全に「ボウリングピン」と呼んでいます:-)

于 2010-08-22T06:54:32.343 に答える
2

私が探しているデータ構造には、ノードごとに複数の親が存在する可能性があるため、おそらくツリーではありません。

あなたが探しているのはおそらくグラフです。ツリーは、各ノードがちょうど 1 つの親を持つグラフの特殊なケースです。(何も持たないルートを除く)

于 2010-08-22T03:43:47.733 に答える
2

「dag」または有向非巡回グラフは、ノードへの複数のパスが存在する可能性がある有向エッジを持つグラフであり、一部のノードには入力エッジと出力エッジの両方がある場合がありますが、ノードを離れてノードに戻る方法はありませんそれ（サイクルはありません）。有限 DAG では、少なくとも 1 つのノードには出力エッジのみが必要であり、少なくとも 1 つのノードには入力エッジのみが必要であることに注意してください。そうでない場合は、(すべてのノードに出口があるため) 行き止まりに達することなく、(グラフが非循環であるため) どのノードにも 2 回アクセスすることなく、グラフを連続的に移動できます。ノードの数が限られている場合、それは明らかに不可能です。

于 2010-08-22T04:30:33.580 に答える