グラフのデータ構造と Algorithms （例）
サラ・チェン
データ構造におけるグラフとは何ですか?
グラフは頂点とエッジで構成される非線形データ構造です。頂点には情報またはデータが含まれ、エッジは頂点のペア間のリンクとして機能します。
目的地までの最適なルートや通信やソーシャル ネットワークのルートを見つけるなど、実際の問題を解決するために使用されます。 ユーザーはグラフ内のノードとみなされ、ワイヤーはユーザーを接続するエッジとなります。
エッジが E で表され、頂点が V で表される場合、グラフ G は頂点とエッジのセットとして次のように書くことができます。 G (V, E)
データ構造のグラフの例
グラフ データ構造の簡単な例を次に示します。
これは単純な無向グラフ (グラフの一種) です。 ここでの頂点のセットは: {A, B, C,D,E,F} です。 XNUMX つの頂点がエッジを作成します。 たとえば、A と B はエッジでリンクされます。 ただし、A と F はどのエッジにもリンクされていません。
データ構造におけるグラフ用語
グラフ データ構造で使用される重要な用語を以下に示します。
| 契約期間 | 詳細説明 |
|---|---|
| 頂点 | すべてのデータ要素は頂点またはノードと呼ばれます。 上の画像では、A、B、C、D、E が頂点です。 |
| エッジ(円弧) | XNUMX つのノードまたは頂点間の接続リンクをエッジ (アーク) と呼びます。 これには XNUMX つの端があり、(startingVertex,endingVertex) として表されます。 |
| 無向エッジ | 双方向エッジです。 |
| 有向エッジ | 一方向エッジです。 |
| 加重エッジ | 価値のあるエッジ。 |
| 度 | グラフでは、頂点に接続されているエッジの数を次数と呼びます。 |
| 度数 | 頂点に接続されている入力エッジの総数。 |
| 出次数 | 頂点に接続されている発信エッジの総数。 |
| セルフループ | エッジの XNUMX つの端点が一致する場合、エッジは自己ループと呼ばれます。 |
| 隣接 | エッジが接続されている場合、頂点は隣接していると言われます。 |
データ構造におけるグラフの種類
最も一般的なもののリストは次のとおりです データ構造内のグラフの種類:
- 有向グラフ
- 無向グラフ
- 加重グラフ
- 双方向グラフ
- 無限グラフ
- ヌルグラフ
- 自明なグラフ
- マルチグラフ
- 完全なグラフ
- 接続されたグラフ
- 循環グラフ
- 有向非巡回グラフ（DAG）
- サイクルグラフ
- XNUMX部グラフ
- オイラーグラフ
- ハミルトングラフ
グラフデータ構造の応用
グラフには多くの使用例があります。グラフを多用するアルゴリズムは数多くあります。グラフの応用例をいくつか挙げます。
- Google マップはグラフを使用して XNUMX 本の道路の交差点を見つけ、XNUMX つの場所間の距離を計算します。
たとえば、 ダイクストラ、送信元と宛先の場所の間の最短距離を見つけます。 - Facebook は、ユーザーの共通の友人を見つけるために Graph を使用します。 そのアルゴリズムは、各ユーザーをグラフのノードとして考慮します。
- リソースの割り当てには、DAG (Direct Acyclic Graph) が使用されます。 リソースの依存関係をチェックします。
- Google 検索エンジンはグラフを使用して Web サイトのランキングを作成します。
- マッピング デバイスはグラフ データ構造を使用します。
- ルータ t のプロトコルは、グラフを使用して宛先パスのパスを学習します。
