Clone Graph（グラフの複製）
Clone Graph（グラフの複製）とは
連結された無向グラフを、元とは独立した同じ構造のグラフとして複製する課題です。
循環を含む構造を再訪問せず、参照関係を保って複製する方法を学べます。
判断するときに確認すること
- 元と複製が別インスタンスか
- 循環で無限に探索しないか
- すべての隣接関係を再現できるか
具体例で整理する
避けたい判断
訪問済み管理をせず、循環するグラフを再帰し続ける。
条件が分かる判断
初めて訪れたノードをMapへ登録してから、その隣接ノードを探索する。
設計とレビューで使う
このページの推奨は次のとおりです。
元ノードと複製ノードの対応をMapへ保存し、DFSまたはBFSで隣接関係を再構築する。