ツリーとグラフのデータ構造
1. 概要
このチュートリアルでは、ツリーとグラフである重要なデータ構造の違いを見ていきます。 それらを使用すると、多くの複雑な問題を効率的に解決できます。
2. 木
ツリーデータ構造をノードのコレクションとして再帰的に定義できます。ツリー構造内の各ノードは、値とノードへの参照のリストを持つデータ構造です。下の図では、各円はツリー内のノードまたは頂点を示しています。ノード間の線をエッジと呼びます。 このツリーには、ルートとして次の6つのノードが含まれています。
との親です。 とはノードの子であるため、兄弟です。 それらは同じ親ノードであるためです。 ご想像のとおり、ノード間には明らかな階層があります。 ノードはツリー内のすべてのノードの祖先ですが、子と子には異なる子孫があります。
上の図は、二分木ではない構造を示しています。 これは、非バイナリでソートされていないツリーである汎用ツリーです。
通常、関係を表すためにツリーを使用します。 配列やリンクリストとは異なり、ツリーは階層構造で非線形構造です。 たとえば、チェスのような戦略ゲームで考えられる状況を見つけようとするとき、決定木を使用します。 他にも、ツリーデータ構造の実際の例がたくさんあります。
2.1. 二分木
バイナリツリーは、ツリーデータ構造の制限付きバージョンです。 二分木では、各ノードには最大2つの子があります。 この時点で、私たちは自分自身に問いかけることができます：これらの木の構造は自然界の木に本当に似ていますか？ 答えは完全ではありません。なぜなら、自然界では、木は根が地面にあり、葉が空中にある状態で成長するからです。 コンピューター科学者は、ルートが上部にあり、リーフが下部にあるツリーデータ構造について説明しています。
ツリーのルートのレベルは0であり、ツリー内の他のノードのレベルは、その親のレベルより1つ高くなっています。 たとえば、上の図のバイナリツリー（左側）では、ノードはレベル3にあります。 二分木の深さは、ツリー内の葉の最大レベルです。
2.2. 二分探索木（BST）
二分探索木は、二分データ構造の制限付きバージョンです。 その内部ノードは、ノードの左側のサブツリーにあるすべてのキーよりも大きく、右側のサブツリーにあるキーよりも小さいキーを格納します。
3. グラフ
グラフは、頂点またはノードのセットと、木のようなエッジを持つデータ構造です。ただし、グラフにはそのような制限はありません。 それらはツリーの拡張バージョンのようなものです
2つの頂点の間にエッジがある場合、グラフデータ構造でそれらを隣接頂点と呼びます。グラフを実装するには、隣接行列と隣接リストの2つの方法があります。 X209X]。
グラフは、接続、切断、および完全化できます。 加重グラフと非加重グラフ、有向および無向グラフに分類することもできます。 。 グラフの種類は、私たちが焦点を当てている問題と密接に関連しています。 たとえば、ルートごとに距離が異なる都市間の最小コストを見つけようとすると、その場合、加重グラフを使用する方が適している可能性があります。
4. ツリーとグラフのデータ構造の違い
ツリーは一種のグラフですが、ツリーとグラフのデータ構造にはいくつかの重要な違いがあります。
- ツリーには階層構造がありますが、グラフにはネットワークモデルがあります。
- ツリーでは、任意の2つの頂点間に1つのルートしか存在しませんが、ノード間に一方向のルートを持つことができるグラフを作成できます。
- ツリーにはループが含まれていませんが、グラフにはループが含まれている場合があり、自己ループも含まれている場合があります。
- ツリーの構造は単純ですが、グラフはループを持つ可能性があるため、より複雑な構造になる可能性があります。
- ツリーに多数のノードがある場合、エッジがあります。 グラフでは、エッジとノードの間にそのような関係はありません。 それは完全にグラフに依存します。
- ツリーには、ルートノードが1つだけあります。 ただし、グラフにはルートノードの概念はありません。
- インオーダー、プレオーダー、またはポストオーダーのトラバーサルメソッドを使用してツリーをトラバースできます。 グラフのトラバーサルには、幅優先探索（BFS）と深さ優先探索（DFS）を使用します。
5. 結論
この記事では、ツリーとグラフのデータ構造について簡単に説明しました。 また、それらの主な違いにも焦点を当てています。 これらの2つの概念は、コンピュータサイエンスにとって重要であるだけでなく、実際には数学において非常に重要な役割を果たしています。
