8

ツリーのクローンを作成するアルゴリズムは非常に簡単です。そのための事前注文トラバーサルを行うことができます。グラフを複製する効率的なアルゴリズムはありますか?

私は同様のアプローチを試み、新しいグラフに既に追加されているノードのハッシュ マップを維持する必要があると結論付けました。そうしないと、1 つのノードが多くの親を持つことができるため、ノードの重複が発生します。

4

4 に答える 4

11

深さ優先検索を実行し、アクセスした各ノードをコピーするだけで十分です。あなたが言うように、サイクル エッジとクロス エッジのコピーを正しく接続できるように、元のグラフのノードを対応するコピーにマッピングする何らかの方法が必要です。

このマップは、DFS で既にアクセスしたノードを記憶するのにも十分です。

したがって、Java では次のようになります。

class Node {

  // Contents of node...
  Data data;

  // ... member declarations like array of adjacent nodes
  final ArrayList<Node> children = new ArrayList<>();

  // Recursive graph walker for copying, not called by others.
  private Node deepCloneImpl(Map<Node, Node> copies) {
    Node copy = copies.get(this);
    if (copy == null) {
      copy = new Node(data);
      // Map the new node _before_ copying children.
      copies.put(this, copy);
      for (Node child : children)
        copy.children.add(child.deepCloneImpl(copies));
    }
    return copy;
  }

  public Node deepClone() {
    return deepCloneImpl(new HashMap<Node, Node>());
  }
}

またはをオーバーライドしたくないことに注意してください。コピーを含むマップは、 で定義されている参照の等価性に依存しています。equalshashCodeNodeObject

別のアプローチは、コピーがある場合はコピーを指し、それ以外の場合は null である追加のフィールドを各ノードに配置することです。これは、別の方法でマップを実装するだけです。ただし、グラフに対して 2 つのパスが必要です。1 つはコピーを作成するため、もう 1 つは将来の再利用のためにこれらのマップ フィールドをクリアするためです。

于 2013-01-26T22:48:33.503 に答える
3

すべてのノードを一意に識別する簡単な方法があれば、ハッシュマップアプローチは実行可能と思われます。

それ以外の場合は、次の場合に最適です。

  1. データ構造を使用してグラフを保存し、「重複している」一意のフラグをすべてのノードに直接保存できるようにしました（たとえば、重複して0いない、重複1 しnumberOfNodesているノードの場合）。

  2. （BFS、DFSを介して）トラバースされたノードは、すでに複製されたノードを処理し、開始グラフからすべての接続を再構築します。

開始グラフと終了グラフの両方に、すべてのノードに対応する一意の「重複」フラグが必要です。これにより、開始グラフから接続を適切に再構築できます。もちろん、「重複している」フラグと「一意の識別子」を別々の変数として使用することもできます。

于 2013-01-26T12:38:18.547 に答える
0

ソース グラフからノードをコピーするときに、各ノードを<Node, Integer>マップに配置します (ノードに 1 から N までの番号を付けます)。

宛先グラフにノードを貼り付けるときに、各ノードを<Integer, Node>マップに配置します (ここでも 1 から N までの番号が付けられていますが、すぐに明らかになる理由から逆方向にマッピングされています)。

ソース グラフでバックリンクが見つかったらi、最初のマップを使用して、そのバックリンクされた「ソース コピー」ノードを整数にマップできます。次に、2 番目のマップを使用して整数iを検索し、同じバックリンクを作成する必要がある「宛先コピー」ノードを見つけます。

于 2013-08-10T00:22:36.830 に答える
0

クローニングを効率的にするには、次の 2 つの方法を使用します。

  • 最後に削除と追加が高速なDS 。list、またはqueue_stack
  • 高速検索を備えたDS 。Mapすばやく検索できます。つまり、O(1)償却できます。

アルゴリズム：

                        To be processed <--> Queue
                          / 
Not_Cloned_Yet -> Clone it -> Map
      `~~~~~~~~checks~~~~~~~~~~^


Root is "Not Cloned yet" and needs to be "To be processed" -- (1)
Clone it -> Put in Map & Queue  -- (2)

Continue till "To be processed" is not zero. i.e. Queue is not empty. -- (3)
    Traverse and update the list of neighbours  -- (4)
        Neighbours that are "Not cloned yet" needs "Clone it -> Put in Map & Queue"   --(5)
  1. ステップ2と5はに基づいていますTo be processed --> Queue
  2. のステップ 3 Queue -> To be processed。
  3. キュー要素は、すでに複製されているが処理されていないものです (つまり、その隣接リストは更新されていません)。
  4. ネイバーは、まだ複製されている場合とされていない場合があります。そのため、チェックインマップが必要です。
于 2017-09-03T07:44:35.207 に答える