木構造のトラバース

親番号配列からDFSとBFSを考える

1. 今日学ぶこと

木構造では、節点同士が親子関係でつながっています。

今日は、木を図ではなく、次のような配列で表します。

i     1  2  3  4  5  6  7  8
A[i]  0  1  1  2  2  4  3  3

この配列から木の形を読み取り、次の2つの方法で節点をたどります。

深さ優先探索
Depth First Search
DFS

幅優先探索
Breadth First Search
BFS

今日の目標は次の通りです。

1. 親番号配列から木の親子関係を読み取れる
2. 根・子・葉・深さを答えられる
3. DFSの訪問順を書ける
4. BFSの訪問順を書ける
5. C++で親番号配列をたどる方法を理解する

2. 木構造の基本用語

次の木を考えます。

1
├─ 2
│  ├─ 4
│  └─ 5
└─ 3
   ├─ 6
   └─ 7

2.1 節点

木を構成する1個のデータです。

1、2、3、4、5、6、7

2.2 根

木の一番上にある節点です。

根：1

2.3 親

ある節点の一つ上にある節点です。

節点4の親：2
節点6の親：3

2.4 子

ある節点の一つ下にある節点です。

節点1の子：2、3
節点2の子：4、5

2.5 葉

子を持たない節点です。

葉：4、5、6、7

2.6 深さ

根から何本の枝を通るかを表します。

根の深さを0とします。

深さ0：1
深さ1：2、3
深さ2：4、5、6、7

3. 親番号配列とは

節点1から節点nまでを持つ木を、整数配列で表します。

A[i] = 節点iの親番号

根には親がいないため、

根のA[i] = 0

とします。

次の配列を見てください。

i     1  2  3  4  5  6  7
A[i]  0  1  1  2  2  3  3

これは次の意味です。

A[1] = 0
→ 節点1は根

A[2] = 1
→ 節点2の親は1

A[3] = 1
→ 節点3の親は1

A[4] = 2
→ 節点4の親は2

A[5] = 2
→ 節点5の親は2

A[6] = 3
→ 節点6の親は3

A[7] = 3
→ 節点7の親は3

木にすると次の形です。

1
├─ 2
│  ├─ 4
│  └─ 5
└─ 3
   ├─ 6
   └─ 7

4. 配列から根を探す

根は、親番号が0になっている節点です。

A[i] = 0

となるiを探します。

例：

i     1  2  3  4  5
A[i]  0  1  1  2  2

A[1] = 0

なので、根は節点1です。

5. 配列から子を探す

節点xの子を探すには、

A[i] = x

となるiを探します。

例：

i     1  2  3  4  5  6
A[i]  0  1  1  2  2  3

節点2の子を探します。

A[4] = 2
A[5] = 2

したがって、

節点2の子：4、5

です。

6. 配列から葉を探す

葉は、子を持たない節点です。

つまり、

A[1]からA[n]までの中に、
一度も親番号として登場しない節点

が葉です。

例：

i     1  2  3  4  5  6  7
A[i]  0  1  1  2  2  3  3

親番号として登場している節点は、

1、2、3

です。

したがって、葉は、

4、5、6、7

です。

7. 練習1：親番号配列を読む

次の配列が表す木について答えなさい。

i     1  2  3  4  5  6  7  8
A[i]  0  1  1  3  3  5  5  5

問1

根はどれですか。

問2

節点3の子をすべて書きなさい。

問3

節点5の子をすべて書きなさい。

問4

葉をすべて書きなさい。

問5

葉の数を書きなさい。

8. トラバースとは

木の節点を順番に訪問することを、

トラバース

といいます。

同じ木でも、たどり方によって訪問順が変わります。

今日扱うのは次の2種類です。

DFS
→ 深く進む

BFS
→ 横に広がる

複数の子がある場合は、

節点番号の小さい順にたどる

ものとします。

9. 深さ優先探索

深さ優先探索は、

行けるところまで深く進み、
行き止まりになったら戻る

方法です。

英語では、

Depth First Search

略して、

DFS

と呼びます。

10. DFSを手でたどる

次の配列を考えます。

i     1  2  3  4  5  6  7  8
A[i]  0  1  1  2  2  4  3  3

この配列が表す木は次の通りです。

1
├─ 2
│  ├─ 4
│  │  └─ 6
│  └─ 5
└─ 3
   ├─ 7
   └─ 8

DFSでは、まず節点1を訪問します。

節点1の子は2と3です。

小さい番号の2へ進みます。

1 → 2

節点2の子は4と5です。

小さい番号の4へ進みます。

1 → 2 → 4

節点4の子は6です。

1 → 2 → 4 → 6

節点6には子がありません。

節点4へ戻ります。

節点4には他の子がないので、節点2へ戻ります。

節点2の次の子5へ進みます。

1 → 2 → 4 → 6 → 5

節点5には子がありません。

節点1へ戻り、次の子3へ進みます。

1 → 2 → 4 → 6 → 5 → 3

最後に、節点3の子7、8を順番に訪問します。

1 → 2 → 4 → 6 → 5 → 3 → 7 → 8

DFSの訪問順は次の通りです。

1 2 4 6 5 3 7 8

11. DFSの考え方

DFSでは、現在の節点から子を探します。

現在の節点を訪問する
↓
現在の節点の子を探す
↓
最初の子へ進む
↓
さらにその子を探す
↓
子がいなければ戻る

重要なのは、

一つの枝を奥まで進む

ことです。

12. 練習2：DFSをたどる

次の配列が表す木を、DFSでたどりなさい。

複数の子がある場合は、節点番号の小さい順にたどります。

i     1  2  3  4  5  6  7  8  9
A[i]  0  1  1  2  2  4  4  3  8

問1

根を書きなさい。

問2

節点4の子を書きなさい。

問3

DFSの訪問順を書きなさい。

13. 幅優先探索

幅優先探索は、

根に近い節点から順番に訪問する

方法です。

同じ深さにある節点を先にすべて訪問します。

英語では、

Breadth First Search

略して、

BFS

と呼びます。

14. BFSを手でたどる

次の木を使います。

1
├─ 2
│  ├─ 4
│  │  └─ 6
│  └─ 5
└─ 3
   ├─ 7
   └─ 8

深さごとに見ると、次のようになります。

深さ0：1
深さ1：2、3
深さ2：4、5、7、8
深さ3：6

したがって、BFSの訪問順は、

1 2 3 4 5 7 8 6

です。

15. BFSとキュー

BFSでは、これから訪問する節点をキューに入れます。

キューは、

先に入れたものを先に取り出す

データ構造です。

First In First Out
FIFO

とも呼びます。

16. BFSのキューを手で追う

最初に根1をキューへ入れます。

キュー：[1]

1を取り出して訪問します。

1の子2、3を入れます。

訪問：1
キュー：[2, 3]

2を取り出して訪問します。

2の子4、5を入れます。

訪問：2
キュー：[3, 4, 5]

3を取り出して訪問します。

3の子7、8を入れます。

訪問：3
キュー：[4, 5, 7, 8]

4を取り出して訪問します。

4の子6を入れます。

訪問：4
キュー：[5, 7, 8, 6]

この処理をキューが空になるまで繰り返します。

17. 練習3：BFSをたどる

次の配列が表す木を、BFSでたどりなさい。

i     1  2  3  4  5  6  7  8  9
A[i]  0  1  1  2  2  4  4  3  8

問1

深さ0の節点を書きなさい。

問2

深さ1の節点を書きなさい。

問3

深さ2の節点を書きなさい。

問4

BFSの訪問順を書きなさい。

18. DFSとBFSの比較

同じ木でも、訪問順は異なります。

1
├─ 2
│  ├─ 4
│  │  └─ 6
│  └─ 5
└─ 3
   ├─ 7
   └─ 8

DFS：

1 2 4 6 5 3 7 8

BFS：

1 2 3 4 5 7 8 6

違いは次の通りです。

探索方法	進み方	主に使うもの
DFS	一つの枝を奥まで進む	再帰、スタック
BFS	根に近い節点から進む	キュー

19. 練習4：DFSかBFSか

次の訪問順がDFSかBFSか答えなさい。

対象の木を表す配列：

i     1  2  3  4  5  6  7
A[i]  0  1  1  2  2  3  3

問1

1 2 4 5 3 6 7

回答：

問2

1 2 3 4 5 6 7

回答：

20. C++で親番号配列を作る

C++では、0番を使わず、1番から節点番号を対応させると分かりやすくなります。

const int NODE_COUNT = 8;

int parent[NODE_COUNT + 1] =
{
    0,
    0,  // 節点1の親
    1,  // 節点2の親
    1,  // 節点3の親
    2,  // 節点4の親
    2,  // 節点5の親
    4,  // 節点6の親
    3,  // 節点7の親
    3   // 節点8の親
};

0番は使いません。

parent[1] = 0

なので、節点1が根です。

21. C++で子を探す

節点currentの子は、

parent[i] == current

となるiです。

for (int i = 1; i <= NODE_COUNT; ++i)
{
    if (parent[i] == current)
    {
        std::cout << i << " ";
    }
}

例えば、currentが2なら、

parent[4] == 2
parent[5] == 2

なので、節点2の子は4と5です。

22. C++でDFSを行う

void DFS(const int parent[], int nodeCount, int current)
{
    std::cout << current << " ";

    for (int i = 1; i <= nodeCount; ++i)
    {
        if (parent[i] == current)
        {
            DFS(parent, nodeCount, i);
        }
    }
}

呼び出しは次の通りです。

DFS(parent, NODE_COUNT, 1);

節点1から探索を始めます。

23. DFSのコードを読む

std::cout << current << " ";

現在の節点を訪問します。

for (int i = 1; i <= nodeCount; ++i)

配列全体を調べます。

if (parent[i] == current)

現在の節点の子かどうかを調べます。

DFS(parent, nodeCount, i);

見つけた子を、さらにDFSでたどります。

24. C++でBFSを行う

#include <queue>

void BFS(const int parent[], int nodeCount, int root)
{
    std::queue<int> nodes;
    nodes.push(root);

    while (!nodes.empty())
    {
        int current = nodes.front();
        nodes.pop();

        std::cout << current << " ";

        for (int i = 1; i <= nodeCount; ++i)
        {
            if (parent[i] == current)
            {
                nodes.push(i);
            }
        }
    }
}

呼び出しは次の通りです。

BFS(parent, NODE_COUNT, 1);

25. BFSのコードを読む

std::queue<int> nodes;

これから訪問する節点番号を保存します。

nodes.push(root);

最初に根を入れます。

int current = nodes.front();
nodes.pop();

キューの先頭を取り出します。

if (parent[i] == current)
{
    nodes.push(i);
}

現在の節点の子を、キューの後ろへ追加します。

26. 練習5：DFSの穴埋め

次のDFSを完成させなさい。

void DFS(const int parent[], int nodeCount, int current)
{
    std::cout << current << " ";

    for (int i = 1; i <= nodeCount; ++i)
    {
        if (____________________________)
        {
            ____________________________;
        }
    }
}

27. 練習6：BFSの穴埋め

次のBFSを完成させなさい。

void BFS(const int parent[], int nodeCount, int root)
{
    std::queue<int> nodes;
    nodes.__________(root);

    while (!nodes.__________())
    {
        int current = nodes.__________();
        nodes.__________();

        std::cout << current << " ";

        for (int i = 1; i <= nodeCount; ++i)
        {
            if (parent[i] == current)
            {
                nodes.__________(i);
            }
        }
    }
}

28. 最終問題

次の親番号配列が表す木について答えなさい。

複数の子がある場合は、節点番号の小さい順にたどります。

i      1  2  3  4  5  6  7  8  9  10
A[i]   0  1  1  2  2  4  4  3  8   8

問1

根を書きなさい。

問2

節点2の子をすべて書きなさい。

問3

節点4の子をすべて書きなさい。

問4

葉をすべて書きなさい。

問5

葉の数を書きなさい。

問6

節点9の深さを書きなさい。

問7

DFSの訪問順を書きなさい。

問8

BFSの訪問順を書きなさい。

29. 解答

練習1

問1：1
問2：4、5
問3：6、7、8
問4：2、4、6、7、8
問5：5個

練習2

配列：

i     1  2  3  4  5  6  7  8  9
A[i]  0  1  1  2  2  4  4  3  8

問1：1
問2：6、7
問3：1 2 4 6 7 5 3 8 9

練習3

問1：1
問2：2、3
問3：4、5、8
問4：1 2 3 4 5 8 6 7 9

練習4

問1：DFS
問2：BFS

練習5

void DFS(const int parent[], int nodeCount, int current)
{
    std::cout << current << " ";

    for (int i = 1; i <= nodeCount; ++i)
    {
        if (parent[i] == current)
        {
            DFS(parent, nodeCount, i);
        }
    }
}

練習6

void BFS(const int parent[], int nodeCount, int root)
{
    std::queue<int> nodes;
    nodes.push(root);

    while (!nodes.empty())
    {
        int current = nodes.front();
        nodes.pop();

        std::cout << current << " ";

        for (int i = 1; i <= nodeCount; ++i)
        {
            if (parent[i] == current)
            {
                nodes.push(i);
            }
        }
    }
}

最終問題

配列：

i      1  2  3  4  5  6  7  8  9  10
A[i]   0  1  1  2  2  4  4  3  8   8

問1：1
問2：4、5
問3：6、7
問4：5、6、7、9、10
問5：5個
問6：3
問7：1 2 4 6 7 5 3 8 9 10
問8：1 2 3 4 5 8 6 7 9 10

30. まとめ

親番号配列では、

A[i] = 節点iの親番号

と考えます。

根は、

A[i] = 0

となる節点です。

節点xの子は、

A[i] = x

となるiです。

葉は、

親番号として一度も登場しない節点

です。

探索方法は次の2つです。

DFS
→ 一つの枝を奥まで進む
→ 再帰、スタック

BFS
→ 根に近い節点から進む
→ キュー

同じ木でも、DFSとBFSでは訪問順が変わります。