私は当初、2つの方法でそれを行っていました。1つの方法は、訪問したノードをリストに保存し、リストをトラバースして、ノードが以前に訪問したことがあるかどうかを判断することです。もう1つは、訪問済みノードと未訪問ノードの両方を追跡するブール配列を使用することでした。それは本当に私に興味を持った、最良の方法は何ですか？
1168 次
2 に答える
6
マイクロ最適化（キャッシュ動作の改善、ルックアップの回避）に役立つ1つのアプローチは、各ノードオブジェクトにフラグを格納することです。明らかな欠点は、グラフアルゴリズムが再入可能ではないことです。トラバーサル中に決定を下すために、別のグラフトラバーサルを実行したいですか？まあ、できません。また、後でこれらすべてのフラグをクリアすることを忘れないでください。
もう1つのカテゴリは、トラバーサルごとに個別のデータ構造を維持することです。リストアプローチは非常に非効率的ですが、あなたが提供するアプローチは両方ともこれに該当します-すべてのルックアップに対してO（n）時間。ブール配列（ビットセットに圧縮される可能性があります。このオプションはスペース効率が非常に高い）は、時間とスペースの両方でシンプルかつ効率的ですが、ノードに連続したインデックス/IDが必要です。これは常に与えられるわけではなく、グラフ処理の他の部分に影響を及ぼします。
それがなく、代わりにポインタでグラフオブジェクトを参照する場合は、それに基づくマッピングを使用できます。Pythonなどの高級言語では、これは非常に単純です（また、高度に調整されたハッシュテーブル/セットデータ構造により、かなり効率的です）。
明らかな利点は、グラフの走査が再入可能であることです。これはあまり聞こえないかもしれませんが、これが役立つ状況が時々発生することを証明できます。
于 2012-10-18T20:12:29.237 に答える
0
使用状況に応じて、時間のパフォーマンスを向上させるために、ハッシュマップを使用できます。bツリーを使用してノードを格納することもできますO（logn）挿入とルックアップ
個人的には、各ノードの一意の値に基づいたハッシュマップを使用します。ニーズを反映するようにハッシュマップのサイズを制御でき、優れたハッシュ関数を使用すると、衝突を制御できます。例については、このコードをご覧くださいhttps://github.com/himanshujindal/Reconstructing-Books-from-Google-Ngrams
于 2012-10-18T20:11:08.147 に答える