リンクリストとマトリックスを使ったグラフ表現

Question

リンクリストやマトリックスを使ってグラフを実装する方法を知っています。しかし、私はリンクされたリスト&をいつグラフ表現のためにマトリックスを使うべきかを知りたいですか？

Answer 1

V =グラフの頂点

ポイント有利マトリックスの数：
1.エッジそれに対し、一定時間内にその端頂点所与（エッジは2つの頂点の間に存在するかどうかを調べる）にアクセスすることができ隣接リストを使用している間にO（度（頂点））の時間をとります。
2.グラフが密集している場合は、行列が良好です。さもなければ、それはO（V * V）スペースを使用するのでスペースを無駄にする。

adjacency listを好む点：
1.隣接リストを使用する場合、O（度（頂点））が必要ですが、頂点の近傍を反復するにはO（V）時間が必要です。
2.隣接リストには多くの領域がありません。

Answer 2

あなたの問題とニーズによって異なります。速度が必要で大容量のストレージ（行列が大きい場合など）が必要な場合はマトリクスを使用し、スペースを節約する必要がある場合はリンクされたリストを使用してください。

Answer 3

通常、グラフがdenseの場合。使用されていないメモリと読み込みが不要な '損失'が無視されるため、行列を使用することをお勧めします。あなたがある場合
あなたはエッジが存在する場合には速いかを知りたいときは、通常、行列を使用するか、またはあなたが

リンクリスト（*）[などPage Rankなど]グラフ上の行列OPSをプリフォームしたいが、通常好まれます各頂点のすべての辺を読み込むときに使用します[例えば：on BFS]。

（*）...グラフが非常に散在しているので舞台裏そのページランクは通常、リンクリストを使用しているが、我々は「散在行列」とみなします

の間に2つの根本的な違いがあります

Answer 4

これら2つの実装はメモリ消費と複雑さの面で優れています。

1. 行列表現は、それが より多くのスペースを消費定数 時間挿入および除去要素が、（一般に）要素にランダムアクセスを可能にします。
2. 一方、リンクされたリストは、でもですが、 の要素および近傍へのアクセスは、となる可能性があります。

Answer 5

常に行列を使用します。

スパース行列を表すためにリンクリストを使用するさまざまな方法を含む、メモリ内の行列の表現方法はさまざまです。行列計算に関する良い本は、いつ使うべきかについての多くの表現とガイドラインを持っています。あなたのグラフによっては、それほど一般的ではない表現の1つが適切かもしれません。