データ構造におけるグラフの種類と例
サラ・チェン
⚡ スマートサマリー
データ構造におけるグラフは、頂点と辺の非線形集合であり、構造に基づいて、有向グラフ、無向グラフ、重み付きグラフ、巡回グラフ、非巡回グラフ、完全グラフ、連結グラフ、二部グラフ、オイラーグラフ、ハミルトングラフなどのファミリーに分類されます。
グラフは、頂点と辺から構成される非線形データ構造です。頂点には情報やデータが格納され、辺は2つの頂点間のリンクとして機能します。
グラフは、ノードとエッジの位置によって複数の種類に分類できます。以下に、重要なグラフの種類をいくつか示します。
有向グラフ
有向グラフの辺には、方向を示す矢印が付いています。矢印は、辺がどこを指しているか、あるいはどこが終点であるかを示します。以下に有向グラフの例を示します。
有向グラフ
- ノード A から D に移動できます。
- しかし、エッジはAからDに向いているため、ノードDからノードAへ移動することはできません。
- グラフには重みがないため、頂点 A から D への移動には、D から F への移動と同じコストがかかります。
無向グラフ
無向グラフは、ポインタを持たない辺で構成されます。つまり、2つの頂点間を双方向に移動できます。以下に、無向グラフの簡単な例を示します。
無向グラフ
上のグラフでは、
- 私たちはA地点からB地点へ移動できます。
- BからAへ移動することもできます。
- エッジには方向が含まれません。
これは、有限個の頂点と重みのない辺を持つ無向グラフの一例です。
加重グラフ
辺に重みまたはコストが設定されているグラフを重み付きグラフと呼びます。数値は一般的に、ある頂点から別の頂点への移動コストを表します。有向グラフと無向グラフの両方で、辺に重みを設定できます。以下に、重み付きグラフ（有向グラフ）の例を示します。
重み付き有向グラフ
- AからBへは辺があり、その重みは5なので、AからBへ移動するには5のコストがかかります。
- AはBを指していますが、このグラフではBはAに直接つながる辺を持っていません。したがって、BからAへ移動することはできません。
- しかし、AからFへ移動するには複数の経路があります。経路はADFとABFです。ADFのコストは(10+11)で21です。
- ここでは、経路 ABF のコストは (5+15) または 20 になります。ここでは、経路内の各エッジの重みを加算しています。
重み付き無向グラフの例を以下に示します。
重みを含む無向グラフ
ここで、エッジには重みがありますが、方向はありません。 つまり、頂点 A から D への移動には 10 のコストがかかり、その逆も同様です。
双方向グラフ
双方向グラフと無向グラフには共通の性質があります。それは次のとおりです。
- 一般的に、無向グラフは2つの頂点間に1つの辺を持つことができる。
具体的な例を挙げますと、以下の通りです。
- ここで、AからD、またはDからAに移動するには10のコストがかかります。
- 双方向グラフでは、XNUMX つの頂点の間に XNUMX つのエッジを持つことができます。
双方向グラフ
AからDへの移動には17のコストがかかりますが、DからAへの移動には12のコストがかかります。したがって、無向グラフの場合、2つの異なる重みを割り当てることはできません。
無限グラフ
グラフには無限個のエッジとノードが含まれます。グラフが無限であり、かつ連結グラフである場合、エッジも無限個含まれます。ここで、拡張エッジとは、これらのノードにエッジを介してさらに多くのエッジが接続されている可能性があることを意味します。以下に、無限グラフの例を示します。
無限グラフ
ヌルグラフ
ヌルグラフは、ノード（頂点）のみを含み、エッジを持たないグラフです。グラフ G = (V, E) が与えられた場合、V は頂点、E はエッジを表しますが、エッジの数 E がゼロであれば、ヌルグラフになります。以下にヌルグラフの例を示します。
ヌルグラフ
自明なグラフ
グラフデータ構造は、頂点またはノードが1つだけで辺が存在しない場合に、自明であるとみなされます。以下に、自明なグラフの例を示します。
マルチグラフ
2つの頂点間に複数のエッジが存在する場合、または頂点にループがある場合、そのグラフはマルチグラフと呼ばれます。グラフデータ構造における「ループ」とは、同じノードまたは頂点を指すエッジを意味します。マルチグラフは有向グラフまたは無向グラフのいずれかになります。以下にマルチグラフの例を示します。
BからAへの辺は2本あります。さらに、頂点Eは自己ループを持っています。上記のグラフは、辺に重みのない有向グラフです。
完全なグラフ
グラフは、各頂点が他のすべての頂点と有向または無向の辺でつながっている場合に完全グラフと呼ばれます。頂点の総数がVで、各頂点がちょうどV-1個の辺を持つとします。この場合、このグラフは完全グラフと呼ばれます。このタイプのグラフでは、各頂点は辺を介して他のすべての頂点と接続されています。以下は、5つの頂点を持つ完全グラフの例です。
画像からわかるように、ノードの総数は5つで、すべてのノードは正確に4つのエッジを持っています。
接続されたグラフ
グラフは、あるノードまたは頂点から出発して、その出発ノードからすべてのノードに移動できる場合、連結グラフと呼ばれます。そのためには、各ノードまたは頂点のペア間に少なくとも1つのエッジが存在する必要があります。以下に連結グラフの例を示します。
上記の連結グラフについて、以下に説明します。
- CとFの間にエッジが存在しない場合、AからGへ移動することはできません。しかし、CからFへのエッジが存在することで、任意のノードから任意のノードへ移動することが可能になります。
- 特定のグラフ内のあるノードから他のノードに移動できるため、完全なグラフは接続されたグラフです。
循環グラフ
グラフに1つ以上のサイクルが存在する場合、そのグラフは循環グラフであると言われます。以下に循環グラフの例を示します。
ここでは、頂点A、B、Cがサイクルを形成しています。グラフには複数のサイクルが存在する可能性があります。
有向非巡回グラフ（DAG）
グラフ内にサイクルがない場合、グラフは有向非巡回グラフ（DAG）と呼ばれます。DAGは、 トポロジカルソート または実行順序の検出。DAGはスケジューリングシステムの作成やリソースの依存関係のスキャンなどにも重要です。ただし、上記のグラフには内部にサイクルは含まれていません。以下は、有向非巡回グラフ（DAG）の簡単な例です。
サイクルグラフ
サイクルグラフは、循環グラフとは異なります。サイクルグラフでは、各ノードは正確に2つのエッジで接続され、つまり各ノードの次数は正確に2になります。以下にサイクルグラフの例を示します。
XNUMX部グラフ
これらの種類の グラフ 二部グラフは、頂点が2つの集合に割り当てられる特殊なグラフです。二部グラフは次の規則に従わなければなりません。
- 2つの頂点集合は互いに異なるものでなければならない。つまり、すべての頂点を2つのグループまたは集合に分割する必要がある。
- 同じ頂点集合は辺を形成してはならない。
オイラーグラフ
グラフデータ構造は、すべての頂点の次数が偶数である場合にオイラーグラフとみなされます。頂点の次数とは、特定の頂点に向かう、または特定の頂点から出る辺の数を意味します。以下にオイラーグラフの例を示します。
すべての頂点の次数は偶数です。頂点A、D、E、Hの次数は2です。ここで、ノードCの次数は4で、偶数です。
ハミルトングラフ
ハミルトングラフとは、ある頂点から同じノードを再訪したり、同じ辺を使用したりすることなく、すべての頂点を訪れることができる連結グラフのことです。このような連結グラフは「ハミルトングラフ」と呼ばれます。与えられたグラフがハミルトングラフであるかどうかを確認するために辿る経路は、ハミルトン経路と呼ばれます。以下に、ハミルトングラフの簡単な例を示します。
この画像では、上のグラフの任意のノードからすべての頂点にアクセスできます。 パスの XNUMX つは次のとおりです。 アドシュベハミルトンサイクルを見つけることも可能です。ハミルトンサイクルは同じ頂点から始まり、同じ頂点で終わります。したがって、ハミルトンサイクルは次のようになります。 ADCHBEA.
