1

これらの中で最も効率的なデータ構造は何ですか？

  • エッジリスト
  • 隣接リスト
  • 隣接行列

Prim-Jarnikのアルゴリズムを実行するためとその理由は？

4

1 に答える 1

1

エッジリストとは、グラフGのすべてのエッジのリストを意味すると思いますか？次に、頂点uに到達するたびにリスト全体をトラバースして、どの（u、v）ペアがGにあるかを知る必要があるため、これは3つの中で最も遅いです。隣接行列はそれよりもいくらか高速ですが、それでも低速です。隣接する頂点とそれぞれのエッジの重みを見つけるには、マトリックスの行全体をトラバースする必要があるためです。ただし、密グラフがある場合、隣接行列は隣接リストのようになります。隣接リストは、マトリックス行の各列に直接アクセスするよりもリストをトラバースする方がコストがかからないように、グラフの密度がそれほど高くないと仮定すると、より高速になります。

とはいえ、プリムのアルゴリズムの重要な問題は実際にはこれではありません。説明されている計算の複雑さを実現するには、優先キューを使用する必要があります（これは、懸念すべき部分です）。

于 2012-12-04T01:50:49.007 に答える