推奨されます, 2019

エディターズチョイス

木とグラフの違い

ツリーとグラフは、ツリーが階層構造内のノード間の関係を表すのに非常に便利な方法を提供する非線形データ構造のカテゴリに属し、グラフはネットワークモデルに従います。 ツリーとグラフは、ツリー構造が接続されなければならず、グラフにはそのような制限がないのに決してループを持つことができないという事実によって区別されます。

非線形データ構造は、平面上に分布している要素の集まりで構成されています。つまり、要素間には、線形データ構造に存在するような順序はありません。

比較表

比較基準グラフ
パス2つの頂点の間に1つだけです。複数のパスが許可されています。
ルートノードルートノードは1つだけです。グラフにはルートノードがありません。
ループループは許可されていません。グラフはループを持つことができます。
複雑あまり複雑ではない比較的複雑
トラバーサル技術予約注文、予約注文、予約注文。幅優先探索と深さ優先探索
エッジ数n-1(nはノード数)定義されていません
モデルの種類階層的ネットワーク

木の定義

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

二分木、二分探索木、AVL木、スレッド二分木、B木などのような木の種類がいくつかある。データ圧縮、ファイル記憶、算術式の操作およびゲーム木は木の応用の一部である。データ構造。

木の性質:

  • ツリーのルートとして知られるツリーの最上部に指定ノードがあります。
  • 残りのデータ項目は、サブツリーと呼ばれる互いに素なサブセットに分割されます。
  • 木は、底に向かって高さが広がります。
  • ツリーは接続されている必要があります。つまり、あるルートから他のすべてのノードへのパスが存在する必要があります。
  • ループは含まれていません。
  • 木はn-1個の辺を持つ。

終点ノード、エッジ、レベル、次数、深さ、フォレストなど、ツリーに関連するさまざまな用語があります。それらの用語のうち、それらのいくつかを以下に説明します。

  • エッジ - 2つのノードを結ぶ線。
  • レベル - ツリーは、ルートノードがレベル0になるようにレベルに分割されます。次に、その直接の子はレベル1になり、その直接の子はレベル2になります。
  • 次数 - 与えられたツリーのノードのサブツリーの数です。
  • 深さ - 特定のツリー内の任意のノードの最大レベルであり、 高さとも呼ばれます。
  • 端末ノード - 最上位ノードは端末ノードで、端末ノードとルートノードを除く他のノードは非端末ノードとして知られています。

グラフの定義

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

グラフは、有向グラフ、無向グラフ、連結グラフ、非連結グラフ、単純グラフ、マルチグラフなど、さまざまなカテゴリに分類されます。 コンピュータネットワーク、交通システム、ソーシャルネットワークグラフ、電気回路およびプロジェクト計画は、グラフデータ構造のアプリケーションの一部です。 グラフ構造を解析するPERT (プログラム評価・レビュー手法)やCPM (クリティカルパス法)と呼ばれる管理手法にも採用されています。

グラフの性質:

  • グラフ内の頂点は、辺を使用して他の任意の数の頂点に接続できます。
  • エッジは双方向化または方向付けできます。
  • エッジには重みを付けることができます。

グラフでも、隣接する頂点、パス、サイクル、次数、連結グラフ、完全グラフ、加重グラフなどのさまざまな用語を使用します。これらの用語のいくつかを理解しましょう。

  • 隣接頂点 - 辺(a、b)または(b、a)がある場合、頂点aは頂点bに隣接します。
  • パス - ランダムな頂点wからのパスは、隣接する頂点の並びです。
  • サイクル - 最初と最後の頂点が同じパスです。
  • 程度 - 頂点に入射するエッジの数です。
  • 連結グラフ - ランダムな頂点から他の頂点へのパスが存在する場合、そのグラフは連結グラフと呼ばれます。

ツリーとグラフの主な違い

  1. ツリーには、任意の2つの頂点間に1つのパスしかありませんが、グラフには、ノード間に単方向パスと双方向パスがあります。
  2. ツリーには、ルートノードが1つだけあり、すべての子には親が1つだけ存在できます。 反対に、グラフにはルートノードという概念はありません。
  3. グラフはループと自己ループを持つことができますが、ツリーはループと自己ループを持つことはできません。
  4. グラフはループと自己ループを持つ可能性があるため、より複雑です。 対照的に、木はグラフと比較して単純です。
  5. ツリーは、事前順序付け、順序どおり、および順序変更後の手法を使用してトラバースされます。 一方、グラフ探索にはBFS(Breadth First Search)とDFS(Depth First Search)を使います。
  6. 木はn-1個の辺を持つことができます。 それとは反対に、グラフには事前定義された数のエッジはなく、それはグラフに依存します。
  7. グラフはネットワークモデルを持つのに対し、ツリーは階層構造をしています。

結論

グラフとツリーは、さまざまな複雑な問題を解決するために使用される非線形データ構造です。 グラフは頂点とエッジのグループで、エッジは頂点のペアを接続しますが、ツリーは、接続され、ループがないようにする必要がある最小接続グラフと見なされます。

Top