ツリーとグラフの違い

コンテンツ

比較表
ツリーの定義
ツリーのプロパティ：
グラフの定義
グラフのプロパティ：
結論

ツリーとグラフは非線形データ構造のカテゴリに分類され、ツリーは階層構造のノード間の関係を表す非常に便利な方法を提供し、グラフはネットワークモデルに従います。ツリーとグラフは、ツリー構造を接続する必要があり、グラフにはそのような制限がないのにループを作成できないという事実によって区別されます。

非線形データ構造は、平面上に分布する要素のコレクションで構成されます。つまり、線形データ構造に存在するような要素間にそのようなシーケンスはありません。

1. 比較表
2. 定義
3. 主な違い
4. 結論

比較表


比較の根拠	木	グラフ
道	2つの頂点のうち1つのみ。	複数のパスが許可されます。
ルートノード	ルートノードは1つだけです。	グラフにはルートノードがありません。
ループ	ループは許可されていません。	グラフにはループが含まれる場合があります。
複雑	それほど複雑ではない	比較的複雑
横断技術	事前注文、注文、および注文。	幅優先検索と深さ優先検索。
エッジの数	n-1（nはノードの数）	定義されていません
モデルタイプ	階層的	通信網

ツリーの定義

A 木通常、ノードと呼ばれるデータ項目の有限コレクションです。上で述べたように、ツリーはデータ項目をソートされた順序で配列する非線形データ構造です。さまざまなデータ要素間の階層構造を示すために使用され、情報に関連するブランチにデータを編成します。ツリーに新しいエッジを追加すると、ループまたは回路が形成されます。

ツリーには、バイナリツリー、バイナリ検索ツリー、AVLツリー、スレッドバイナリツリー、Bツリーなど、いくつかのタイプがあります。データ圧縮、ファイルストレージ、算術式の操作、ゲームツリーは、ツリーのアプリケーションの一部です。データ構造。

ツリーのプロパティ：

ツリーのルートには、ツリーの最上部に指定されたノードがあります。
残りのデータ項目は、サブツリーと呼ばれる互いに素なサブセットに分割されます。
ツリーは、下に向かって高さが拡張されます。
ツリーは接続されている必要があります。つまり、1つのルートから他のすべてのノードへのパスが必要です。
ループは含まれていません。
ツリーにはn-1個のエッジがあります。

終端ノード、エッジ、レベル、次数、深さ、森林など、ツリーに関連するさまざまな用語があります。これらの用語の中で、それらのいくつかを以下に説明します。

縁 – 2つのノードを接続する線。
レベル –ツリーは、ルートノードがレベル0になるようにレベルに分割されます。次に、その直接の子はレベル1になり、その直接の子はレベル2になります。
程度 –これは、特定のツリー内のノードのサブツリーの数です。
深さ –これは、特定のツリー内のノードの最大レベルであり、別名高さ.
ターミナルノード –最高レベルのノードはターミナルノードであり、ターミナルとルートノードを除く他のノードは非ターミナルノードと呼ばれます。

グラフの定義

A グラフまた、さまざまな種類の物理構造を表すことができる数学的な非線形データ構造です。頂点（またはノード）のグループと、2つの頂点を接続するエッジのセットで構成されます。グラフ上の頂点は点または円として表され、エッジは円弧または線分として表示されます。エッジはE（v、w）で表されます。vとwは頂点のペアです。回路または接続されたグラフからエッジを削除すると、ツリーであるサブグラフが作成されます。

グラフは、有向、無向、接続、非接続、シンプル、マルチグラフなどのさまざまなカテゴリに分類されます。コンピュータネットワーク、交通システム、ソーシャルネットワークグラフ、電気回路、プロジェクト計画は、グラフデータ構造のアプリケーションの一部です。次のような名前の管理手法にも採用されています。 パート （プログラム評価およびレビュー手法）および CPM （クリティカルパス法）グラフ構造が分析されます。