演習課題「木と親と訪問順」
頂点数 n の木が与えられるので、頂点 s から深さ優先探索をおこなったとき、1 から n までの各頂点の親がどの頂点になるかを「訪問順」に出力するプログラムを完成させてください。
制約
・ 入力はすべて整数
・ 1 ≦ n ≦ 10
・ 頂点の番号は 1 以上 n 以下
期待する出力値
頂点 5 の親は 1 です
頂点 4 の親は 5 です
頂点 2 の親は 5 です
頂点 3 の親は 2 です
＃06:木の深さ
このチャプターでは、深さ優先探索を利用して木の深さを求めるプログラムを作成します。
準備：
・各頂点の深さを記録する配列を 0 で初期化
探索：
・dfs(v, p) の内部で以下の処理を実装
1. 隣接する頂点を順番に見て、もしその頂点が p でなければ、その頂点の深さを「v の深さ + 1」に更新したのち、その頂点に対して dfs を呼び出す
5 1
1 2
1 5
2 3
2 4
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;
public class Main {
static List<List<Integer>> g;
static int[] depth;
static void dfs(int v, int p) {
// v に隣接するすべての頂点 u について
for (int u : g.get(v)) {
// 頂点 u が親 p でなければ
if (u != p) {
// 頂点 u の深さを「頂点 v の深さ + 1」にする
depth[u] = depth[v] + 1;
// 頂点 u に対して dfs を呼び出す
dfs(u, v);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = n - 1, s = sc.nextInt() - 1;
g = new ArrayList<List<Integer>>(n);
for (int i = 0; i < n; i++) {
g.add(new ArrayList<Integer>());
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
g.get(a).add(b);
g.get(b).add(a);
}
depth = new int[n];
dfs(s, -1);
for (int i = 0; i < n; i++) {
System.out.println("頂点 " + (i + 1) + " の深さは " + depth[i] + " です");
}
sc.close();
}
}