演習課題「親を求める」
頂点数 n のグラフが与えられるので、頂点 s から深さ優先探索をおこなったとき、1 から n までの各頂点の親がどの頂点になるかを頂点の番号順に格納する配列 parent を求めるプログラムを完成させてください。
制約
・ 入力はすべて整数
・ 1 ≦ n ≦ 10
・ 頂点の番号は 1 以上 n 以下
期待する出力値
頂点 2 の親は 5 です
頂点 3 の親は 2 です
頂点 4 の親は 5 です
頂点 5 の親は 1 です
＃05:深さ優先探索
このチャプターでは、グラフを探索するアルゴリズムの1つである深さ優先探索について詳しく学習していきます。
準備：
・訪問済みかどうかを記録する配列を未訪問で初期化
探索：
・dfs(v) の内部で以下の処理を実装
1. 頂点 v を訪問済みにし、頂点に対する処理をおこなう
2. 隣接する頂点を順番に見て、もし未訪問であれば dfs を呼び出す
5 4 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 void printVertex(int v) {
System.out.println("頂点 " + (v + 1) + " を探索");
}
static List<List<Integer>> g;
// 訪問済みかどうかを記録する配列 visited を用意
static boolean[] visited;
static void dfs(int v) {
// 頂点 v を訪問済みにする
visited[v] = true;
// 頂点 v を出力する
printVertex(v);
// 頂点 v に隣接するすべての頂点 u について
for (int u : g.get(v)) {
// 頂点 u が訪問済みでなければ
if (!visited[u]) {
// 頂点 u に対して dfs を呼び出す
dfs(u);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), 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);
}
// 配列 visited を未訪問で初期化
visited = new boolean[n];
dfs(s);
sc.close();
}
}