グラフと木

データ構造にはグラフと木が使われる。グラフとツリーの違いは確かにありますね。二項関係を持つ頂点の集合をグラフと呼び、互いにリンクしたノードの集合を木と呼ぶデータ構造である。

グラフィック

グラフはエッジで結ばれた項の集合であり、各項はノードまたは頂点と呼ばれる。つまり、グラフとは、二項関係を持つ頂点の集合として定義することができる。

グラフの実装では、ノードはオブジェクトまたは構造体として実装される。エッジはさまざまな方法で表現することができます。1つの方法は、各ノードが入射エッジの配列と関連付けられることである。情報をエッジではなくノードに格納する場合、配列はノードへのポインタとして機能し、またエッジを表す。この方法の利点の一つは、グラフにノードを追加できることである。既存のノードは、配列に要素を追加することで接続することができます。しかし、ノード間にエッジが存在するかどうかを判断するのに時間がかかるというデメリットがある。

別の方法として、2次元の配列または行列Mをブール値で保持する方法がある。ノードiからjへのエッジの有無は、エントリMijで指定される。この方法の利点は、2つのノード間にエッジが存在するかどうかを調べることができる点である。

樹木

また、ツリーとは、コンピュータサイエンスで用いられるデータ構造の一つで、木の構造に似ており、相互にリンクされたノードの集合を持つものである。

ツリーのノードには、条件や値を入れることができる。また、それ自体がツリーになることもあれば、別のデータ構造を表すこともある。木データ構造には、0個以上のノードが存在する。あるノードが子ノードを持つ場合、その子ノードの親と呼ばれる。ノードは最大1つの親を持つことができます。ノードからリーフへの最長の下り経路は、ノードの高さである。ノードの深さは、そのルートへのパスで表される。

木では、最上部のノードをルートノードと呼びます。ルートノードは最上位であるため、親ノードを持たない。このノードからすべてのツリー操作が始まります。他のノードは、リンクまたはエッジを使用してルートノードからアクセスすることができます。最下層のノードはリーフノードと呼ばれ、子ノードを持ちません。複数の子ノードを持つノードは、内部ノードまたはインナーノードと呼ばれます。