非線形データ構造は、平面上に分布している要素の集まりで構成されています。つまり、要素間には、線形データ構造に存在するような順序はありません。
比較表
| 比較基準 | 木 | グラフ |
|---|---|---|
| パス | 2つの頂点の間に1つだけです。 | 複数のパスが許可されています。 |
| ルートノード | ルートノードは1つだけです。 | グラフにはルートノードがありません。 |
| ループ | ループは許可されていません。 | グラフはループを持つことができます。 |
| 複雑 | あまり複雑ではない | 比較的複雑 |
| トラバーサル技術 | 予約注文、予約注文、予約注文。 | 幅優先探索と深さ優先探索 |
| エッジ数 | n-1（nはノード数） | 定義されていません |
| モデルの種類 | 階層的 | ネットワーク |
木の定義
ツリーは、通常ノードと呼ばれるデータ項目の有限の集合です。 上述したように、ツリーはソートされた順序でデータ項目を配列する非線形データ構造です。 これは、さまざまなデータ要素間の階層構造を示すために使用され、データを情報を関連付けるブランチに編成します。 ツリーに新しいエッジを追加すると、ループまたは回路が形成されます。
二分木、二分探索木、ＡＶＬ木、スレッド二分木、Ｂ木などのような木の種類がいくつかある。データ圧縮、ファイル記憶、算術式の操作およびゲーム木は木の応用の一部である。データ構造。
木の性質：
- ツリーのルートとして知られるツリーの最上部に指定ノードがあります。
- 残りのデータ項目は、サブツリーと呼ばれる互いに素なサブセットに分割されます。
- 木は、底に向かって高さが広がります。
- ツリーは接続されている必要があります。つまり、あるルートから他のすべてのノードへのパスが存在する必要があります。
- ループは含まれていません。
- 木はn-1個の辺を持つ。
終点ノード、エッジ、レベル、次数、深さ、フォレストなど、ツリーに関連するさまざまな用語があります。それらの用語のうち、それらのいくつかを以下に説明します。
- エッジ - 2つのノードを結ぶ線。
- レベル - ツリーは、ルートノードがレベル0になるようにレベルに分割されます。次に、その直接の子はレベル1になり、その直接の子はレベル2になります。
- 次数 - 与えられたツリーのノードのサブツリーの数です。
- 深さ - 特定のツリー内の任意のノードの最大レベルであり、 高さとも呼ばれます。
- 端末ノード - 最上位ノードは端末ノードで、端末ノードとルートノードを除く他のノードは非端末ノードとして知られています。
グラフの定義
グラフは、さまざまな種類の物理構造を表すことができる数学的非線形データ構造でもあります。 それは頂点（またはノード）のグループと2つの頂点を結ぶエッジのセットから成ります。 グラフ上の頂点は点または円として表され、辺は円弧または線分として表されます。 辺はE（v、w）で表されます。ここで、vとwは頂点のペアです。 回路グラフまたは接続グラフからエッジを削除すると、ツリーであるサブグラフが作成されます。
グラフは、有向グラフ、無向グラフ、連結グラフ、非連結グラフ、単純グラフ、マルチグラフなど、さまざまなカテゴリに分類されます。 コンピュータネットワーク、交通システム、ソーシャルネットワークグラフ、電気回路およびプロジェクト計画は、グラフデータ構造のアプリケーションの一部です。 グラフ構造を解析するPERT （プログラム評価・レビュー手法）やCPM （クリティカルパス法）と呼ばれる管理手法にも採用されています。
グラフの性質：
- グラフ内の頂点は、辺を使用して他の任意の数の頂点に接続できます。
- エッジは双方向化または方向付けできます。
- エッジには重みを付けることができます。
グラフでも、隣接する頂点、パス、サイクル、次数、連結グラフ、完全グラフ、加重グラフなどのさまざまな用語を使用します。これらの用語のいくつかを理解しましょう。
- 隣接頂点 - 辺（a、b）または（b、a）がある場合、頂点aは頂点bに隣接します。
- パス - ランダムな頂点wからのパスは、隣接する頂点の並びです。
- サイクル - 最初と最後の頂点が同じパスです。
- 程度 - 頂点に入射するエッジの数です。
- 連結グラフ - ランダムな頂点から他の頂点へのパスが存在する場合、そのグラフは連結グラフと呼ばれます。
ツリーとグラフの主な違い
- ツリーには、任意の2つの頂点間に1つのパスしかありませんが、グラフには、ノード間に単方向パスと双方向パスがあります。
- ツリーには、ルートノードが1つだけあり、すべての子には親が1つだけ存在できます。 反対に、グラフにはルートノードという概念はありません。
- グラフはループと自己ループを持つことができますが、ツリーはループと自己ループを持つことはできません。
- グラフはループと自己ループを持つ可能性があるため、より複雑です。 対照的に、木はグラフと比較して単純です。
- ツリーは、事前順序付け、順序どおり、および順序変更後の手法を使用してトラバースされます。 一方、グラフ探索にはBFS（Breadth First Search）とDFS（Depth First Search）を使います。
- 木はn-1個の辺を持つことができます。 それとは反対に、グラフには事前定義された数のエッジはなく、それはグラフに依存します。
- グラフはネットワークモデルを持つのに対し、ツリーは階層構造をしています。
結論
グラフとツリーは、さまざまな複雑な問題を解決するために使用される非線形データ構造です。 グラフは頂点とエッジのグループで、エッジは頂点のペアを接続しますが、ツリーは、接続され、ループがないようにする必要がある最小接続グラフと見なされます。
