====== 木構造と隣接行列 練習問題集 ====== C++ や Python で木構造を扱う前に、 「**隣接行列（adjacency matrix）**」で木を表現する練習をしよう！ 各行列は、A[i][j] = 1 なら「i → j（親→子）」を意味する。 --- ===== 🌟 例題 ===== 次の木構造を、**隣接行列** で表してみよう。 ``` 0 / \ 1 2 / \ 3 4 ``` ノード番号：0〜4 A[i][j] = 1 ⇔ i→j のとき。 --- **解答：** ^ ^0^1^2^3^4^ |0|0|1|1|0|0| |1|0|0|0|0|0| |2|0|0|0|1|1| |3|0|0|0|0|0| |4|0|0|0|0|0| **補足説明：** * ノード0が根。 * 0→1, 0→2, 2→3, 2→4 の4本の枝がある。 * 行の合計が「子の数」、列の合計が「親の数」。 * 入次数0のノード（列和が0）は根ノード。 * 出次数0のノード（行和が0）は葉ノード。 --- ===== 【第1部】隣接行列を読み取る ===== **問題1：** 次の隣接行列 A が示す木について、 (1) 根ノード、(2) 葉ノード、(3) 辺の一覧（親→子）を答えよ。 ^ ^0^1^2^3^4^ |0|0|1|1|0|0| |1|0|0|0|0|0| |2|0|0|0|1|1| |3|0|0|0|0|0| |4|0|0|0|0|0| --- **問題2：** 次の親配列から隣接行列を作成せよ。 A[i][j] = 1 ⇔ i→j とする。 ``` parent = { -1, 0, 0, 2, 2, 4 } ``` --- **問題3：** 次の隣接行列が与えられたとき、 根ノード 0 から探索したときの **DFS順** と **BFS順** をそれぞれ答えよ。 ^ ^0^1^2^3^4^5^ |0|0|1|1|0|0|0| |1|0|0|0|1|1|0| |2|0|0|0|0|0|1| |3|0|0|0|0|0|0| |4|0|0|0|0|0|0| |5|0|0|0|0|0|0| --- **問題4：** 次のような関数を作りたい。 出次数が 0 のノード（子を持たないノード）を列挙せよ。 ```cpp vector getLeaves(const vector>& A); ``` 入力例： ``` A = { {0,1,1}, {0,0,0}, {0,0,0} } ``` 出力： ``` [1, 2] ``` --- **問題5：** 次の隣接行列 A から、入次数が 0 のノードを求めよ。 （＝根ノード） ^ ^0^1^2^3^ |0|0|1|0|0| |1|0|0|1|0| |2|0|0|0|0| |3|0|0|0|0| --- ===== 【第2部】木から隣接行列を書く ===== **問題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>& A); ``` --- ===== 【補足】====== * 行の合計 → 出次数（子の数） * 列の合計 → 入次数（親の数） * 入次数0 → 根ノード * 出次数0 → 葉ノード