木構造

木構造とは

グラフ構造の中でも特に閉路を持たない連結なグラフを木構造と呼ぶ。

閉路を持たないとは、どういうことを指しているかというと

同じ頂点を通らずに始点と終点が同じになることはない

ということである。

連結であるとは全ての頂点が繋がっていることをいう。

つまり、閉路を持たない連結なグラフとは次のような状態である。

木構造には平衡 2 分探索木・AVL 木・トライ木・3 文探索木・赤黒木・スキュー木・スプレー木・B ＋木・パトリシア木などが存在する。

用語

開始となる頂点(ノード)を根と呼び、根と繋がっている辺のことを枝と言い、根と枝で繋がっている頂点を子ノードと呼ぶ。また、根が存在する木のことを根付き木と呼ぶ。

根から枝を通った個数をその頂点の深さと呼び、同じ根に属しているかつ同じ深さの頂点同士を兄弟ノードと呼ぶ。枝で接続しているかつ深さが-1である頂点を親ノードと呼ぶ。

根付き木において最大の深さにある頂点のことを葉(リーフ)と呼び、子ノードが存在するノードを根と見ることができ、この見方をした根付き木のことを部分木と呼ぶ。

木構造の条件である閉路を持たない連結なグラフの連結なを取り除いた閉路を持たないグラフのことを森と呼ぶ。

プログラム

グラフ構造の特別な条件が木構造となる。 そのため、グラフ構造と全く作成するプログラムは同じになる。

Python

box = [[1,5],[1,3],[1,4],[4,6],[6,2]]
graph = [[] for _ in range(6)]
for i in range(len(box)):
    graph[box[i][0]-1].append(box[i][1]-1)
    graph[box[i][1]-1].append(box[i][0]-1)

C++

int main() {
    vector<pair<int,int>> box = {{1,5},{1,3},{1,4},{4,6},{6,2}};
    vector<vector<int>> graph(6);
    for(int i = 0; i < box.size();++i){
        graph[box[i].first-1].push_back(box[i].second-1);
        graph[box[i].second-1].push_back(box[i].first-1);
    }
    return 0;
}

C#

public static void Main(string[] args)
{
    int[,] box = new int[,] { { 1, 5 }, { 1, 3 }, { 1, 4 }, { 4, 6 }, { 6, 2 } };
    List<List<int>> graph = new List<List<int>>();
    for (int i = 0;i < 6; ++i)
    {
        graph.Add(new List<int>());
    }
    for (int i = 0; i < box.Length/2; ++i)
    {
        graph[box[i, 0] - 1].Add(box[i, 1] - 1);
        graph[box[i, 1] - 1].Add(box[i, 0] - 1);
    }
}