事前にエッジの数だけを知っている加重無向グラフを実装する効率的な方法を探しています。
サンプル入力:
N (エッジの数)
AB x (x は A から B までの距離)
.
.
Node* の隣接リスト (隣人を知る必要があります) と格納されたノードを動的ハッシュ テーブルに使用することを考えました (いくつのノードを取得するかわからないため、動的 - 検索/挿入 - コンテナーが必要です) ）。
それを行うより良い方法はありますか？
私の悪い英語でごめんなさい！:D
質問する
201 次
1 に答える
0
入力を取得する形式を考えると、非常に合理的なアプローチは、リストのハッシュテーブルを使用することです。ここで、キーはノードであり、値は（ノード、距離）のペアのリストです。あるいは、密グラフがあり、あるノードから別のノードまでの距離をすばやく判断できるようにしたい場合は、ハッシュテーブルのハッシュテーブルを用意するとよいでしょう。このハッシュテーブルでは、最上位のハッシュテーブルがノードを2番目のハッシュテーブルにマップします。 、次に、元のノードがエッジを持つ各ノードをそのコストにマッピングします。これにより、ノードの出力エッジ全体を反復処理できますが、距離のルックアップが高速になります。
別のアイデア（ユースケースによって異なります）は、最初のデータ構造（リストのハッシュテーブル）を構築することから始め、次に隣接行列を構築することによってそれを後処理することです。これは、ノードの発信エッジを反復処理する必要がなく、ノード間の距離への高速ランダムアクセスが必要な場合に役立ちます。これはハッシュテーブルのハッシュテーブルに似ていますが、おそらくスペース効率が高くなります。
お役に立てれば！
于 2013-01-17T16:55:53.150 に答える