私はしばらく探していましたが、別の解決策を見つけることができないようです。可能であれば、ノードが複数の親を持つことができるようなツリートラバーサルアルゴリズムが必要です（ここで素晴らしい記事を見つけました：データベースへの階層データの保存）。ルートノードから始めて、ノードのシーケンスと依存関係を決定できるようにするアルゴリズムはありますか（現在トポロジカルソートを読み取っています）？
2299 次
4 に答える
2
あなたが説明した構造は木ではなく、有向グラフです。階層的な描画に適しているため、ツリー（それ自体は非巡回連結グラフ）と考えたくなるかもしれません。
グラフの一般的なトラバーサルアルゴリズムは、深さ優先と幅優先です。グラフの実装は、特定のノードに何度もアクセスすることを避けるために、すでにアクセスしたノードを記録するという点でのみ異なります。ただし、データ構造によって非周期的であることが保証されている場合は、「親」を「子」として扱うだけで、グラフでツリーアルゴリズムを使用できます。
私が意味することを説明するために簡単なスケッチを作成しました（Googleドキュメントの新しい描画機能を試す絶好のチャンス）：
ご覧のとおり、非巡回有向形式のグラフをツリーとして扱い、ツリーアルゴリズムを適用することができます。このプロパティを保証できないとすぐに、専用のグラフアルゴリズムを使用する必要があります。
于 2010-04-21T09:08:58.403 に答える
1
ツリーは基本的に有向の重み付けされていないグラフであり、各頂点のエッジはN以下であり、サイクルは発生しません。
ツリーにサイクルがないと確信している場合は、親を指定されたノードの別の子として扱い、通常どおりプレオーダートラバーサルを実行できます。
ただし、サイクルが発生する可能性がある場合は、グラフアルゴリズムが必要です。
具体的には、幅優先探索です。
于 2010-04-21T09:47:36.017 に答える
0
おそらく単純なケースをチェックするだけです。2人の親が異なる親を持つことはできますか？いいえの場合は、それらを（概念的に）単一のノードに変えて、再びツリーを作成することができます。
それ以外の場合は、子ノードを分割し、他の親のブランチを複製する必要があります。（もちろん、これは、データ構造を維持する必要があるかどうかに応じて、後で不整合や非効率なアルゴリズムにつながる可能性があります）。
上記のオプションは、定義上、親を1つだけ持つことができるツリー構造を持つことを主張する場合に当てはまります。
したがって、一歩下がって、何を達成しようとしているのか、ノードが2つの親を持つことができるのになぜそれがツリー構造でなければならないのかを説明する必要があるかもしれません。
于 2010-04-21T10:30:11.080 に答える
0
ここでは木について説明していません。グラフをツリーと呼ぶことはできません。
ツリーは、サイクルのない無向グラフです。親子関係は、端に描かれた方向の解釈ではありません。これらは、1つの頂点にルートという名前を付けた結果です。
ルートへのパスの次の頂点であるため、頂点に現在の「親」という名前を付けます。現在の頂点に隣接する他のすべての頂点は「子」です。
「親」が「上」または「頂点を指す」、子が「下」または「頂点がそれらを指す」ように任意のグラフをレイアウトすることはできません。根が選ばれるので、木は木です。質問で描くのは木ではありません。また、ツリー走査アルゴリズムは、任意のグラフの走査には適用できません。
幅優先探索や深さ優先探索など、いくつかのグラフ走査アルゴリズムがあります（詳細については、これらのページのサイドノートを確認してください）。フル機能のグラフをツリーに関する知識に結び付けるのではなく、それらを使用してください。
于 2010-04-21T10:30:21.610 に答える