0

ノードを取得し、これと隣接するすべてのノードをコピーして、このノードとまったく同じ新しい構造を作成する関数。

A
/ \
B CE
\ /
D

新しいノードで同様のネットワークを作成する必要があります

Node オブジェクトは次のように定義されます。

ノード{

配列リストの隣人。// 配列リスト内のすべての隣接ノードを返します

}

このコードは機能しますか?

public Node copyGraph(Node A){
    HashTable<Node, Node> hash = new HashTable<Node, Node> ();

    return copyGraphWithHash(A, hash);

}

public Node copyGraphWithHash(Node A, HashTable<Node, Node> hash){


  if (A.neighbours.size() == 0)
    return null;

  Node newfirst = null;

  if(!hash.hasKey(A))
    newfirst = new Node();
    hash.add(A,newfirst);
  }


  for ( Node n : A.neighbours()){

   if (copyGraphWithHash(n, hash))
         newfirst.neightbours.add(copyGraphWithHash(n, hash));
  }
  return newfirst;
 }

ここで何が欠けているか教えてください。

4

1 に答える 1

1

このコードは、スタック オーバーフロー例外をスローして終了します。

問題 :

  • 間違った基本ケース: 少なくとも 2 つのノードを含むグラフがある限り、すべてのケースですべての子に対して常に再帰関数を呼び出すため、無限再帰が発生します。
  • 間違った再帰ケース: 場合によっては、再帰関数がループ内で 2 回呼び出されます
  • グラフにノードが 1 つしかない場合の間違った動作: 複製されません

ソリューション:

  • ネイバーのテストを削除
  • ハッシュテーブルに処理されたノードが含まれている場合は、複製されたノードを直接返します
  • そうでない場合は、新しいノードを作成し、テーブルに対応を追加し、neighbors 変数を初期化することを忘れないでください。
  • ループでは、テストを削除し、常に隣接変数を埋めます

その他の潜在的な問題:

  • 再帰関数はパブリックです。事前に入力されたハッシュテーブルを提供する必要がない場合は、公開しないでください
  • 非マルチスレッド コンテキストでのハッシュマップの代わりのハッシュテーブルの使用
  • A が null の場合、エラー管理なし
于 2012-07-14T09:46:01.410 に答える