データ構造におけるグラフの種類と例

グラフは、頂点とエッジで構成される非線形データ構造です。頂点には情報またはデータが含まれており、エッジは頂点のペア間のリンクとして機能します。

グラフには、ノードとエッジの位置に応じて複数のタイプがあります。重要なグラフの種類をいくつか示します。

有向グラフ

有向グラフのエッジには、方向を意味する矢印が含まれています。矢印は、エッジが指す場所または終了する場所を決定します。

以下は有向グラフの例です。

ノード A から D に移動できます。
ただし、エッジは A から D を指しているため、ノード D からノード A に移動することはできません。
グラフには重みがないため、頂点 A から D への移動には、D から F への移動と同じコストがかかります。

無向グラフ

無向グラフにはポインターのないエッジが含まれています。これは、XNUMX つの頂点間を逆に移動できることを意味します。

無向グラフの簡単な例を次に示します。

上のグラフでは、

私たちは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 のコストがかかり、その逆も同様です。

双方向グラフ

双方向グラフと無向グラフには共通の特性があります。あれは

一般に、無向グラフは XNUMX つの頂点間に XNUMX つのエッジを持つことができます。

例：

ここで、AからD、またはDからAに移動するには10のコストがかかります。
双方向グラフでは、XNUMX つの頂点の間に XNUMX つのエッジを持つことができます。

次に例を示します：

A から D への移動には 17 のコストがかかりますが、D から A への移動には 12 のコストがかかります。したがって、無向グラフの場合、XNUMX つの異なる重みを割り当てることはできません。

無限グラフ

グラフには、無限の数のエッジとノードが含まれます。グラフが無限であり、接続されたグラフでもある場合、同様に無限の数のエッジが含まれます。ここで、拡張されたエッジは、より多くのエッジがエッジを介してこれらのノードに接続される可能性があることを意味します。

以下は無限グラフの例です。

ヌルグラフ

Null Graph にはノードまたは頂点のみが含まれますが、エッジは含まれません。グラフ G = (V, E) (V は頂点、E はエッジ) が指定された場合、エッジ E の数が XNUMX であれば null になります。

Null グラフの例を次に示します。

自明なグラフ

頂点またはノードが XNUMX つだけ存在し、エッジが存在しない場合、グラフデータ構造は自明とみなされます。

以下は自明なグラフの例です。

マルチグラフ

XNUMX つの頂点間に複数のエッジが存在する場合、または頂点にループがある場合、グラフはマルチグラフと呼ばれます。グラフデータ構造における「ループ」という用語は、同じノードまたは頂点を指すエッジを意味します。マルチグラフは有向または無向にすることができます。

マルチグラフの例を次に示します。

B から A までのエッジが XNUMX つあります。さらに、頂点 E には自己ループがあります。上のグラフは、エッジに重みを持たない有向グラフです。

完全なグラフ

各頂点が他のすべての頂点とともに有向エッジまたは無向エッジを持つ場合、グラフは完成します。

合計 V 個の頂点があり、各頂点に正確に V-1 個のエッジがあるとします。そして、このグラフを完全グラフと呼びます。このタイプのグラフでは、各頂点はエッジを介して他のすべての頂点に接続されます。

以下は、XNUMX つの頂点を持つ完全なグラフの例です。

このイメージでは、ノードの合計数が XNUMX であり、すべてのノードに正確に XNUMX つのエッジがあることがわかります。

接続されたグラフ

ノードまたは頂点から開始し、開始ノードからすべてのノードを移動する場合、グラフは接続グラフと呼ばれます。このためには、ノードまたは頂点の各ペアの間に少なくとも XNUMX つのエッジが必要です。

接続されたグラフの例を次に示します。

上記の「完全なグラフの例」グラフの説明を次に示します。

C と F の間にエッジがないと仮定すると、A から G に移動することはできません。ただし、エッジ C から F を使用すると、特定のノードから任意のノードに移動できます。
特定のグラフ内のあるノードから他のノードに移動できるため、完全なグラフは接続されたグラフです。

循環グラフ

グラフ内に XNUMX つ以上のサイクルが存在する場合、グラフは循環的であると言われます。

循環グラフの例を次に示します。

ここで、頂点 A、B、C はサイクルを形成します。

グラフ内に複数のサイクルを含めることができます。

有向非巡回グラフ（DAG）

グラフ内にサイクルがない場合、グラフは有向非巡回グラフまたは DAG と呼ばれます。 DAG は、トポロジカルソートまたは実行順序を見つける。 DAG は、スケジューリングシステムの作成やリソースの依存関係のスキャンなどにも重要です。ただし、上記のグラフには内部にサイクルが含まれていません。

以下は、有向非巡回グラフ (DAG) の簡単な例です。

サイクルグラフ

Cycle Graph は、Cyclic Graph とは異なります。 Cycle Graph では、各ノードには正確に XNUMX つのエッジが接続されます。これは、各ノードが正確に XNUMX 次を持つことを意味します。

以下はサイクルグラフの例です。

XNUMX部グラフ

これらの種類のグラフは、頂点が XNUMX つのセットに割り当てられる特別な種類のグラフです。

二部グラフは次のルールに従う必要があります。

XNUMX つの頂点セットは別個である必要があります。これは、すべての頂点を XNUMX つのグループまたはセットに分割する必要があることを意味します。
同じセットの頂点がエッジを形成してはなりません。

オイラーグラフ

すべての頂点の次数が偶数であれば、グラフデータ構造はオイラーグラフとみなされます。頂点の次数という用語は、特定の頂点を指す、または特定の頂点から指すエッジの数を意味します。

以下はオイラーグラフの例です。

すべての頂点の次数は偶数です。頂点 A、D、E、および H には XNUMX つの次数があります。ここで、ノード C の次数は XNUMX であり、偶数です。

ハミルトングラフ

ハミルトングラフは接続グラフであり、同じノードに再度アクセスしたり、同じエッジを使用したりすることなく、特定の頂点からすべての頂点にアクセスできます。この種の接続されたグラフは「ハミルトングラフ」として知られています。指定されたグラフがハミルトングラフであるかどうかを確認するためにアクセスするパスは、ハミルトンパスと呼ばれます。

ハミルトンの簡単なグラフの例を次に示します。

この画像では、上のグラフの任意のノードからすべての頂点にアクセスできます。パスの XNUMX つは次のとおりです。 アドシュベ。ハミルトンサイクルを見つけることも可能です。ハミルトンサイクルは同じ頂点で始まり、同じ頂点で終わります。したがって、ハミルトンサイクルは次のようになります。 アドチベア。