多くの場合、グラフは隣接行列を使用して表されます。さまざまなソースが、初期化のコストが |V^2| になるのを回避できることを示しています。（Vは頂点の数です）しかし、どうすればよいかわかりませんでした。
Java では、単に行列を宣言するだけで、たとえばboolean adj [][]、ランタイムは自動的に配列を初期化しfalse、これはO(V^2)コスト (配列の次元) になります。
私は誤解していますか？隣接行列の初期化の二次コストを回避することは可能ですか、それとも実装言語に依存する単なる理論的なものですか?
マトリックスの値のデフォルトの初期化は、実際には機能です。デフォルトの初期化がなかったら、すべてのフィールドを自分で初期化して、その値がどうなるかを知る必要があるのではないでしょうか?
隣接行列にはこの欠点があります。メモリ効率の点で悪く（O（n 2）メモリセルが必要です）、初期化が遅いと言ったように。ただし、初期化が最大の問題とは見なされません。私を信じてください、メモリ割り当てははるかに遅く、必要なメモリは初期化時間よりもはるかに制限されています.
多くの場合、行列の代わりに隣接リストを使用する方が好まれます。このようなリストにはO(m)メモリが必要です。ここmで、 はグラフ内のエッジの数です。これは、特にスパース グラフの場合に、はるかに効率的です。このグラフ表現が隣接行列よりも悪い唯一の操作はクエリis there edge between vertices i and jです。マトリックスは時間内に答えO(1)、リストは確かにずっと遅くなります。
ただし、典型的なグラフ アルゴリズムの多く ( Dijkstra、Bellman-Ford、Prim、Tarjan、BFS、DFSなど) は、特定の頂点のすべての隣接要素を反復するだけで済みます。行列の代わりに隣接リストを使用すると、これらすべてのアルゴリズムに大きなメリットがあります。
これは、行列のすべての要素（多数のゼロを含む可能性がある）ではなく、「1」の位置のみが割り当てられる隣接行列の疎行列表現を使用することで可能になります。このスレッドも役立つかもしれません
A_Aの答えについて詳しく説明します。彼はスパース行列を推奨しています。これは基本的に、隣接リストの維持に戻ることを意味します。
マトリックスを使用する理由は2つあります。パフォーマンスをまったく気にせず、提供される単純なコードが好きな場合、またはパフォーマンスを気にするがマトリックスが比較的いっぱいになる場合（少なくとも20％としましょう）この投稿のために、完全です）。
あなたは明らかにパフォーマンスを気にします。行列が比較的空になる場合は、初期化のオーバーヘッドが意味を持つ可能性があるため、隣接リストを使用することをお勧めします。完全にいっぱいになると、初期化は無視できるようになります。マトリックス内の適切なセルを埋める必要があり（初期化よりも時間がかかります）、それらを処理する必要があります（これも、よりも時間がかかります）。初期化）。