以下に示すようなグラフを作成するプログラムがあります
アルゴリズムは緑色のノードから開始し、グラフをトラバースします。画像の赤い点で示されているグラフに、ノード (左、右、上、下の 4 つの参照を持つリンク リスト タイプのノード) が追加されたとします。新しく作成されたノードを隣接するノードと統合するには、4 つのオブジェクトを見つけてリンクし、グラフの接続が保持されるようにする必要があります。
以下は、私が明確にする必要があるものです
- 黄色のノードはすべて null であり、新しく作成されたノードの隣接ノードの存在を見つける最も効率的な方法は、ノードをマップするための別のデータ構造を保持していないとします。DFS、BFS などの基本的なグラフ検索アルゴリズムと最短パス アルゴリズムは知っていますが、グラフには約 10000 個のノードがあり、グラフ検索アルゴリズム (緑色のノードから開始) を実行して、新しいノードが追加されたときの隣人は、私には計算コストがかかるようです。
- グラフ検索が避けられない場合、最良の代替構造は何ですか。大きな多次元配列を考えました。ただし、これにはメモリの浪費があり、負のインデックスがないという問題もあります。画像のグラフは任意の方向に成長できるためです。これに対する私の解決策は、配列ベースのデータ構造で構成される別のクラスを作成して、負のインデックスを表現することです。ただし、このオプションを選択する前に、新しい構造に解決せずに問題を解決し、多くの再作業を節約できるかどうかを知りたい.
フィードバックをいただき、この質問を読んでいただきありがとうございます。