グラフのデータ構造と Algorithms （例）
サラ・チェン
⚡ スマートサマリー
グラフデータ構造は、頂点と辺からなる非線形な集合であり、各辺は2つの頂点を結び付けます。グラフは、地図、ソーシャルネットワーク、ウェブページなど、現実世界のネットワークをモデル化し、多くの強力なアルゴリズムをサポートします。
データ構造におけるグラフとは何ですか?
グラフは、頂点と辺から構成される非線形データ構造であり、頂点には情報またはデータが含まれており、辺は2つの頂点間のリンクとして機能する。
これは、目的地までの最適なルートの探索や、通信およびソーシャルネットワークの経路探索など、現実世界の様々な問題を解決するために使用されます。グラフでは、ユーザーがノードとして扱われ、ワイヤはユーザー同士をつなぐエッジです。
エッジが E で表され、頂点が V で表される場合、グラフ G は頂点とエッジのセットとして次のように書くことができます。 G（V、E）.
データ構造のグラフの例
グラフデータ構造の簡単な例を以下に示します。
これは単純な無向グラフ（グラフの一種）です。頂点の集合は{A, B, C, D, E, F}です。2つの頂点は辺を形成します。例えば、AとBは辺で結ばれています。しかし、AとFはどの辺でも結ばれていません。
データ構造におけるグラフ用語
グラフデータ構造で使用される重要な用語を以下に示します。
| 契約期間 | 詳細説明 |
|---|---|
| 頂点 | 各データ要素は頂点またはノードと呼ばれます。上の図では、A、B、C、D、Eが頂点です。 |
| エッジ(円弧) | 2つのノードまたは頂点間の接続リンクはエッジ（弧）と呼ばれます。エッジには2つの端点があり、（開始頂点、終了頂点）として表されます。 |
| 無向エッジ | 双方向エッジです。 |
| 有向エッジ | 一方向エッジです。 |
| 加重エッジ | 値が設定されたエッジ。 |
| 度 | グラフにおいて、頂点に接続されている辺の数を次数と呼ぶ。 |
| 度数 | 頂点に接続されている入力エッジの総数。 |
| 出次数 | 頂点に接続されている発信エッジの総数。 |
| セルフループ | エッジの XNUMX つの端点が一致する場合、エッジは自己ループと呼ばれます。 |
| 隣接 | 頂点同士が辺で繋がっている場合、それらの頂点は隣接していると言われる。 |
データ構造におけるグラフの種類
最も一般的なもののリストは次のとおりです データ構造内のグラフの種類:
- 有向グラフ
- 無向グラフ
- 加重グラフ
- 双方向グラフ
- 無限グラフ
- ヌルグラフ
- 自明なグラフ
- マルチグラフ
- 完全なグラフ
- 接続されたグラフ
- 循環グラフ
- 有向非巡回グラフ（DAG）
- サイクルグラフ
- XNUMX部グラフ
- オイラーグラフ
- ハミルトングラフ
グラフをデータ構造で表現するには？
グラフは通常、2つの表現形式のいずれかを使用してメモリに格納されます。どちらの形式を選択するかによって、グラフが使用するメモリ量と、一般的な操作の実行速度が変わります。
- 隣接行列: 2次元のV×V配列で、頂点iと頂点jの間にエッジが存在する場合はセル[i][j]が1（またはエッジの重み）、存在しない場合は0となる。エッジの検索はO(1)で済むが、O(V²)の空間を使用するため、密なグラフに最適である。
- 隣接リスト: 各頂点が隣接する頂点のリストを格納するリストの配列。O(V + E)の空間を使用し、疎なグラフに対して効率的であるため、ほとんどの現実世界のグラフで使用されています。
これらについての詳細は、 グラフの隣接リストと行列表現 チュートリアル。
グラフデータ構造の応用
グラフには多くの用途があります。グラフを利用するアルゴリズムは数多く存在します。以下に、グラフの応用例をいくつか示します。
- Google Mapsはグラフを使用して2つの道路の交差点を見つけ、2つの場所間の距離を計算します。たとえば、 ダイクストラ出発地と目的地間の最短距離を求めるため。
- Facebookはグラフを用いてユーザー間の共通の友人を見つけ出す。そのアルゴリズムでは、各ユーザーをグラフのノードとして扱う。
- リソース割り当てには、DAG（有向非巡回グラフ）が使用されます。DAGはリソース間の依存関係をチェックします。
- その Google 検索エンジンはグラフを使用してウェブサイトのランキングを作成します。
- 地図ping このデバイスはグラフデータ構造を使用します。
- A ルータ そしてそのプロトコルは、グラフを使用して目的地までの経路を学習します。
