木構造と隣接行列 練習問題集

C++ や Python で木構造を扱う前に、 「隣接行列（adjacency matrix）」で木を表現する練習をしよう！

各行列は、A[i][j] = 1 なら「i → j（親→子）」を意味する。

—

次の木構造を、隣接行列 で表してみよう。

```

  0
 / \
1   2
   / \
  3   4

```

ノード番号：0〜4 A[i][j] = 1 ⇔ i→j のとき。

—

解答：

補足説明：

* ノード0が根。 * 0→1, 0→2, 2→3, 2→4 の4本の枝がある。 * 行の合計が「子の数」、列の合計が「親の数」。 * 入次数0のノード（列和が0）は根ノード。 * 出次数0のノード（行和が0）は葉ノード。

—

問題1： 次の隣接行列 A が示す木について、 (1) 根ノード、(2) 葉ノード、(3) 辺の一覧（親→子）を答えよ。

—

問題2： 次の親配列から隣接行列を作成せよ。 A[i][j] = 1 ⇔ i→j とする。

``` parent = { -1, 0, 0, 2, 2, 4 } ```

—

問題3： 次の隣接行列が与えられたとき、 根ノード 0 から探索したときの DFS順 と BFS順 をそれぞれ答えよ。

—

問題4： 次のような関数を作りたい。 出次数が 0 のノード（子を持たないノード）を列挙せよ。

```cpp vector<int> getLeaves(const vector<vector<int»& A); ```

入力例：

``` A = { {0,1,1}, {0,0,0}, {0,0,0} } ```

出力：

``` [1, 2] ```

—

問題5： 次の隣接行列 A から、入次数が 0 のノードを求めよ。 （＝根ノード）

—

問題6： 次の木構造を隣接行列で表せ。

```

  0
 / \
1   2
   / \
  3   4

```

ノード番号：0〜4

—

問題7： 次の木を隣接行列で表せ。

```

  0
 /|\
1 2 3

```

ノード番号：0〜3

—

問題8： 次の木を隣接行列で表せ。

``` 0 → 1 → 2 → 3 → 4 ```

ノード番号：0〜4 直線構造（1本の鎖）

—

問題9： 次の木を隣接行列で表せ。

```

    0
   / \
  1   2
 / \
3   4

```

ノード番号：0〜4

—

問題10： 次の木を隣接行列で表せ。

```

    0
   / \
  1   2
 /     \
3       4

```

ノード番号：0〜4

—

チャレンジ： 隣接行列 A が「木構造」を表しているか判定する関数を考えよ。

条件：

* 入次数が 0 のノードがちょうど1つ（根） * すべてのノードがその根から到達可能 * 辺の数が (ノード数 - 1)

例：

```cpp bool isTree(const vector<vector<int»& A); ```

—

* 行の合計 → 出次数（子の数） * 列の合計 → 入次数（親の数） * 入次数0 → 根ノード * 出次数0 → 葉ノード