3

以下のグラフでは、子パーツが再帰的にトラバースされます。各子は、直接の親を報告する必要があります。問題は、child[3] が直接の親 (つまり、child[2] と child[4]) の両方を同じ行で同時に報告しなければならないことです。

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

Parent 
|---child[1]
|       child[2]
|           child[3]
|---child[4]
        child[3]

現在、一度に 1 つのノードでグラフをトラバースしており、生成される出力は -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2]
child[3]  child[4]

期待される出力は -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2], child[4]

ノードを検索し、グラフの期待される出力を生成する最良の方法は何でしょうか? どんな助けでも大歓迎です。

4

1 に答える 1

8

親へのリンクを持っている (または追加できる) 場合は、最初にノードに遭遇したときにすべての親をリストし、繰り返しの訪問でそれをスキップできます。ノードが訪問されたかどうかを追跡するための複数のオプションがあります。

  1. 訪問したノードのセットを維持し、現在のノードがセット内にあるかどうかを確認します。そうでない場合は、処理してセットに追加します。それ以外の場合はスキップします。

    利点: 一般的なアプローチ

    欠点: グラフが大きい場合、セットを維持するために大量のメモリが必要になる場合があります

  2. isVisitedメンバー値をノードに追加し(falseデフォルトで に設定)、ノードに遭遇したときにそれをチェックします。値が の場合、ノードを処理して truefalseに設定します。isVisitedそれ以外の場合はスキップします。

    利点: 追加メモリが少ない

    短所: 押し付けがましく、タスク固有であり、不要な場合でも追加の変数が存在し、複数の「まだ処理されていない」という決定を同時に必要とするタスクには十分に対応できません。

親リンク オプションが使用できない場合は、追加のマップで子と親の関係を維持できます。ノードを処理するときに、子から親のセットにマップします。最初の処理 (マップの作成) が完了したら、マップを反復処理して、各ノードとその親をリストします。

直接の親リンクに対する利点は、グラフを作成/変更するときに余分なメンテナンスが必要ないことです (マッピングを最新の状態に保ちたい場合を除く)。

欠点は、グラフの構造に一連の変更を加えた後、グラフを処理するたびにマップを再構築する必要があることです (ただし、アドベンテージの注を参照してください) 。

注: すべての子をトラバースして一般的なグラフをトラバースすると、グラフに有向 (親から子へ) の円がある場合、無限ループにつながる可能性があります。これはあなたの問題には当てはまらないと思いますが、すべてのベースをカバーするためです.グラフを処理するときに「訪問した」ノードのセットを維持できます. 利用可能なオプションの説明は、最初の部分 (「親へのリンク」) と同じです。

于 2012-06-20T12:31:14.520 に答える