グラフのデータ構造
1. 概要
グラフ理論で理解する最も重要なことの1つは、それらをメモリに格納する方法です。
このチュートリアルでは、グラフの3つの主要なデータ構造を説明および比較し、それらの長所と短所を示します。
2. 問題の定義
グラフ理論では、ノードを頂点 と呼び、ノード間の接続をエッジと呼びます。 グラフストレージのデータ構造を扱う場合、比較は空間と時間の複雑さに基づいて行われます。
2.1. 複雑さ
グラフストレージデータ構造では、通常、次の複雑さに注意を払います。
- スペースの複雑さ：選択したデータ構造にグラフを格納するために必要なメモリのおおよその量
- 時間計算量
- 接続チェックの複雑さ：2つの異なるノードが隣接しているかどうかを確認するために必要なおおよその時間
- 複雑さを見つける隣人：あるゴールノードのすべての隣人ノードを見つけるのに必要なおおよその時間
最初のノードと2番目のノードを接続するエッジがある場合、2つの異なるノードを「隣接ノード」と呼びます。
2.2. グラフの種類
理解する必要があることの1つは、グラフは通常2つの要素に基づいて定義されるということです。
最初の要因は、グラフが重み付けされているかどうかです。 グラフ理論では、2つのノードが接続されているという事実だけを気にすることがあります。 また、ノードからノードに移動するコストも気になります。
この記事では、データ構造ごとに両方の場合に実行する必要がある更新を示します。
2番目の要素は、グラフが方向付けられているかどうかです。 から、へのエッジがあり、ノードからノードにしか移動できない場合、グラフは有向と呼ばれます。 ただし、無向グラフでは、ノード間のエッジとは、ノード間を移動したり、その逆を実行したりできることを意味します。
各エッジを2つのエッジの間で分離することにより、無向グラフを有向グラフにいつでも変換できます。 したがって、この記事では、より一般的なケースである有向グラフについて説明します。
3. グラフのデータ構造
グラフをメモリに格納するために、3つの主要なデータ構造が使用されます。
3.1. 隣接行列
最初のデータ構造は隣接行列と呼ばれます。 名前が示すように、隣接行列は、2つのノードが隣接（接続）されているかどうかをすばやく見つける必要がある場合に役立ちます。 隣接行列は、サイズがのブール配列です。
名前を付けましょう。そうすれば、次のようになります。
からへの直接エッジがある場合。
それ以外は。
ただし、処理されたグラフに重みが付けられている場合、各セルはとの間の直接エッジの重みを含む配列になります。
との間にエッジがない場合、との間に直接接続がないことを示す特別な値が含まれます。 通常、大きな値を使用できます。これは、uとvの間を直接移動するのに多くの費用がかかるか、不可能であることを示します。
3.2. 隣接リスト
2番目のデータ構造は隣接リストです。 このデータ構造では、すべての異なるペアとの値を格納することを目的とはしていません。 代わりに、ノードごとに、隣接ノードのみを保存します。
これを行うには、サイズの配列を作成します。 各セルはリンクリストを保持します。 リンクリスト内の各オブジェクトは、インデックスでノードに接続されているノードのインデックスを格納します。 したがって、各セルには、ノードに接続されているノードの数に対応するサイズのリンクリストがあります。
言い換えると：
これは、ノードのi thネイバーに等しくなります。
加重グラフを扱っている場合、リンクリスト内の各オブジェクトは、隣接ノードととの間のエッジのコストという2つの情報を保持します。
3.3. エッジリスト
最後のデータ構造はエッジリストです。 名前から、グラフのすべてのエッジをリンクリスト内に格納していると推測できます。
このリストを。と呼びましょう。 リンクリスト内の各オブジェクトは、ノードとノード、の2つを保持し、ノードとノードを接続するエッジが存在することを示します。 上記から、次のことが推測できます。
グラフ内のi番目のエッジの情報が含まれているようなものです。
グラフに重みが付けられている場合、各オブジェクトは、ノードとの間のエッジの重みである3番目の情報を保持します。
このデータ構造は、ノードの数が多いがエッジの数が少ないグラフで特に役立ちます。
4. 複雑
各グラフストレージデータ構造の複雑さの概要を示す以下の表を見てみましょう。 次に、それぞれの複雑さの背後にある理由を説明します。
4.1. スペースの複雑さ
- 隣接行列：隣接行列にはサイズの配列が格納されているため、スペースの複雑さはです。ここで、はグラフ内の頂点の数です。
- 隣接リスト：最初に、サイズの配列を格納します。各セルには、グラフのノードの1つの情報が格納されます。 これは、最初に、空の配列を格納するためのスペースの複雑さが必要であることを意味します。 次に、すべてのリンクリストのサイズの合計に移動します。 新しいエッジの場合にのみ追加のリンクリストオブジェクトを作成するため、リンクリストのサイズの合計がに等しいことを意味します。ここで、はグラフのエッジの数です。 これにより、スペース全体の複雑さがになります。
- エッジリスト：このデータ構造には、グラフ内のすべてのノード間で可能なすべてのエッジを格納するリンクリストのみがあります。 したがって、メモリの複雑さはです。
4.2. 接続チェックの複雑さ
- 隣接行列：隣接行列を使用する場合、2つのノードが接続されているかどうかを確認するのは非常に効率的です。 セルの値を探すだけです。 したがって、時間計算量は。に等しくなります。
- 隣接リスト： 2つのノードが接続されているかどうかを確認するには、内に格納されているリンクリストを反復処理する必要があります。 最悪の場合、との間にエッジはなく、反復を行うことになります。 したがって、全体の複雑さは、です。ここで、はの近傍の数です。
- エッジリスト：エッジリストの場合、他のオプションはありませんが、リンクリスト内のすべてのエッジを反復処理し、ノードとの間で必要なエッジを見つけることができるかどうかを確認します。 複雑さは、グラフ内のエッジの数です。
4.3. 複雑さを見つける隣人
- 隣接行列：あるノードのすべての隣接ノードを見つけるには、行 u 内のすべてのセルを反復処理して、どのノードに直接エッジが接続されているかを判断する必要があります。 つまり、すべてのセルをチェックする必要があります。ここで、。 したがって、時間計算量はです。
- 隣接リスト：すべての隣接ノードをすばやく見つけることが、隣接リストの作成目的です。 セルには、に接続されているすべてのノードを含むリンクリストが格納されているため、内に格納されているリンクリストを反復処理する必要があります。 このような反復の時間計算量はです。ここで、はノードの隣接ノードの数を表します。
- エッジリスト：エッジリストは、すべての隣接ノードをすばやく見つけるための最善のソリューションではない可能性があります。 リンクリスト内のすべての保存されたオブジェクトを反復処理し、保存されたノードがとであるかどうかを確認する必要があります。 したがって、時間計算量は、です。ここで、はグラフのエッジの数です。
5. 長所と短所
隣接行列は、2つのノードに直接エッジがあるかどうかをすばやく確認する必要がある場合に役立ちます。 ただし、主な欠点は、メモリが非常に複雑になることです。 隣接行列は、グラフに多数のノードが含まれていない場合に最も役立ちます。 また、グラフがほぼ完成している場合（すべてのノードが他のほとんどすべてのノードに接続されている場合）、隣接行列を使用することをお勧めします。
一方、隣接リストは、あるノードuのすべての隣接リストに継続的にアクセスする必要がある場合に最適なオプションです。 その場合、必要なノードのみを反復処理します。 隣接リストの制限は、2つのノードに直接エッジがあるかどうかを確認する必要がある場合に表示されます。
ただし、隣接リストの更新バージョンを使用できることは注目に値します。 リンクリストにすべての隣接ノードを格納する代わりに、たとえばsetなどのより複雑なデータ構造にそれらを格納できます。 これにより、隣接するノードを効率的に反復処理できます。 また、対数時間計算量で2つのノードが接続されているかどうかを確認できます。
エッジリストは、最も使用されていないデータ構造です。 主に、メモリ内に保存できないノードが大量にあり、エッジが少ない場合は、エッジリストを使用します。 その場合、エッジリストを使用する以外に選択肢はありません。 したがって、エッジリストの唯一の利点は、メモリスペースの複雑さが低いことです。
6. 結論
この記事では、グラフをメモリに格納するための3つの主要なデータ構造を紹介しました。
次に、ほとんどのグラフアルゴリズムが実行する主な操作の空間と時間の複雑さについて説明しました。
最後に、空間と時間の複雑さの観点から各データ構造の長所と短所、および各データ構造をいつ使用するかについて説明しました。
