graph - グラフ ライブラリの実装

Question

加重グラフを実装しようとしています。加重グラフを実装するには 2 つの方法があることを知っています。2 次元配列 (隣接行列) またはリンクされたリストの配列 (隣接リスト) のいずれかを使用します。どちらがより効率的で高速ですか?

Answer 1

どちらがより効率的で高速ですか?

これは、使用方法と保存するグラフの種類によって異なります。

n をノードの数、m をエッジの数とします。2 つのノード u と v が接続されているかどうか (およびエッジの重み) を知りたい場合は、隣接行列を使用すると、エントリを取得するだけで、一定時間 ( O 表記法、O(1)) でこれを判断できます。 A[u,v]. 隣接リストでは、u のリストまたは v のリストのすべてのエントリを確認する必要があります。最悪の場合、n 個のエントリが存在する可能性があります。したがって、隣接リストのエッジ ルックアップは O(n) です。

隣接行列の主な欠点は、必要なメモリです。全体として、n^2 エントリを格納する必要があります。隣接リストを使用すると、実際に存在するエッジのみを保存する必要があります (m エントリ、有向グラフを想定)。したがって、グラフがまばらな場合、隣接リストが占有するメモリは明らかにはるかに少なくなります。

私の結論は次のとおりです。主な操作が2つの特定のノードのエッジの重みを取得する場合は、隣接行列を使用してください。グラフが十分に小さく、n^2 エントリがメモリに収まるという条件の下で。それ以外の場合は、隣接リストを使用します。

Answer 2

個人的には、リンクされたリストのアプローチを使用します。これは、疎なグラフになることが多い (つまり、配列セルのほとんどがスペースの無駄になる) ことを前提としています。

ウィキペディアにアクセスして、隣接リスト(グラフを使用してから何年も経ちます) を調べました。2 つのアプローチのトレードオフに関するすばらしいセクションがあります。最終的には、多くのいずれかまたは両方の選択肢と同様に、ライブラリのユースケースがどのようなものであるかに基づいて、「依存する」ことになります。

ウィキの記事を読んだ後、リストの使用を支持する別のポイントは、各有向セグメントにデータを添付することだと思います (または、異なる重みで、2 点間の徒歩/自転車/車の距離などを考えてください)。