1

私のプロジェクトは、Java を使用して最小スパニング ツリーを実装することです。プリムのアルゴリズムを使用してタスクを実行することを目指しています。

グラフの定義は G = (V, E) です。ここで、V はピンのセット、E はピンのペア間の可能な相互接続のセットであり、E の各エッジ (u,v) に対して重み w( u,v) u と v を接続するためのコストを指定します。

私の考えは、2 つのハッシュマップを使用することです。まず、ピンをキーとして、近隣のリストを値として持ちます。2 番目のハッシュマップは、エッジ (u,v) のリストをキーとして取得し、値はその重みになります。

グラフを保存する最良の方法は何だと思いますか?

4

3 に答える 3

2

グラフは一般に (これらのグラフで使用されるアルゴリズムに関係なく) 次のいずれかとして保存されます。

  • 隣接リスト、
  • 隣接行列、
  • 発生率リスト、
  • 発生率行列。

すべてに、メモリ使用量とトラバースに必要な時間に関する長所と短所があります。ウィキペディアには、コンピューターでのグラフ表現に関する優れた記事があります。

于 2012-03-30T11:59:56.630 に答える
0

Kruskal と Prim の両方の最小スパニング ツリー アルゴリズムでは、グラフの隣接リスト表現で十分です。マトリックスのアプローチよりもメモリ使用量が効率的です。したがって、あなたの場合は良い選択です。

于 2012-03-30T12:14:07.810 に答える
0

ウィキペディアを見てください。継承された複雑さだけでなく、さまざまなデータ構造を利用できます

于 2012-03-30T11:57:26.537 に答える