グラフの実装と隣接行列の初期化

Question

グラフは多くの場合、隣接行列を使用して表されます。様々な情報源から、初期化のコストを| V^2 | （Vは頂点の数ですが）私はどのように計算したのでしょうか？

Javaでは、単に行列を宣言するだけです。 boolean adj [][]の場合、ランタイムはとなります。はfalseで配列を初期化します。これはO（V^2）コスト（配列のサイズ）になります。
私は誤解していますか？隣接行列の初期化の二次コストを避けることは可能ですか？これは実装言語に依存する理論的なものですか？

Answer 1

隣接行列のスパース行列表現を使用することで可能です。行列の各要素（多数のゼロを含む可能性があります）ではなく、「1」の位置のみが割り当てられます。 this threadも便利です

Answer 2

マトリックスの値のデフォルトの初期化は、実際には機能です。それがデフォルトの初期化ではなかったのですが、それでもあなたは自分のすべてのフィールドを初期化して、その値が何を期待するのかを知る必要はありませんか？

隣接行列にはこの欠点があります。メモリ効率が悪い（それらはメモリセルが必要です）、それらの初期化は遅いと言います。ただし、初期化は最大の問題とはみなされません。私の考えでは、メモリの割り当てはかなり遅く、必要なメモリは初期化の時間よりはるかに制限されています。

---

多くの場合、人々はマトリックスの代わりに隣接リストを使用することを好みます。そのようなリストには、O(m)のメモリが必要です。ここで、mはグラフの辺の数です。これは、特にスパースグラフの場合には、はるかに効率的です。このグラフ表現が隣接行列より悪い唯一の操作は、クエリis there edge between vertices i and jです。マトリックスはO(1)の答えを返し、リストは確かにかなり遅くなります。

（Dijkstra、Bellman-Ford、Prim、Tarjan、BFS及びDFS等）の典型的なグラフ・アルゴリズムのしかし多くは、与えられた頂点のすべてのネイバーを反復する必要があります。これらのアルゴリズムはすべて、行列の代わりに隣接リストを使用すると非常に便利です。

Answer 3

私はA_Aの答えを詳しく説明します。彼はスパース行列を推奨しています。基本的には、隣接リストの維持に戻ります。

パフォーマンスを気にせず、提供しているシンプルなコードのように、パフォーマンスが気になるがマトリックスが比較的いっぱいになる場合は、マトリックスを使用する理由が2つありますこの投稿のために、少なくとも20％満員）。

あなたは明らかにパフォーマンスを気にします。マトリックスが比較的空になる場合、その初期化オーバーヘッドは意味があり、隣接リストを使用するほうがよいでしょう。もし完全にいっぱいになると、初期化は無視できなくなります - 行列の右のセルを埋める必要があります（これは初期化よりも多くなります）。そしてそれらを処理する必要があります。それを初期化する）。

Answer 4

このスレッドでは、かなりの混乱と誤解があります。実際には、隣接行列（および任意の配列一般）の初期化コストを回避する方法があります。ただし、Javaプリミティブでのメソッドの使用はデフォルトでは初期化されているため使用できません。

アレイdata[0..n]が自動初期化されていないとすると、始めるには、それは前に記憶にあったものから迷惑でいっぱいです。 O（n）時間を上書きしたくない場合は、迷惑データから追加した良好なデータを区別するための方法が必要です。

"トリック"は、良好なデータを含むセルを追跡する補助スタックを使用することです。最初にdata[i]に書き込むときに、インデックスiをスタックに追加します。スタックはスタックに追加されるにつれて増加するだけなので、気にする必要のあるジャンクは一切含まれません。

data[k]にアクセスするたびに、kのスタックをスキャンしてそのジャンクがあるかどうかを確認できます。しかし、それは最初の場所の配列のポイントを破って、読み取りごとにO（n）時間かかるでしょう！

これを解決するために、別の補助配列stack_check[0..n]を作成します。この補助配列もまた迷惑メールでいっぱいです。この配列には、スタック内の要素へのポインタが含まれています。今度はdata[i]に書き込むと、iがスタックにプッシュされ、stack_check[i]が新しいスタック要素を指すように設定されます。

data[k]が良好なデータである場合、stack_check[k]は、スタック要素がkであることを示します。 data[k]が迷惑メールである場合、stack_check[k]の迷惑メールの値は、k以外のスタック要素を指しているか、または何らかのスタック要素を指しています（kは決してスタックに置かれていないため）。このプロパティをチェックするのはO（1）です。したがって、配列アクセスはまだ高速です。

すべてをまとめて、O（1）に配列とヘルパー構造を作成することができます。それぞれの読み書きで、指定されたセルに、私たちのヘルパーを使用して、O（1）時間のジャンクが含まれているかどうかがチェックされます。私たちが迷惑メールに上書きしている場合は、ヘルパー構造を更新して、セルを有効なデータとしてマークします。迷惑メールを読んだ場合は、問題に適した方法で処理できます。例えば、0のようなデフォルト値を返すことができます（今は初期化していないとは言えません！）、あるいは例外を投げるかもしれません。