ねらいと前提
ツリー/グラフ探索は「親→子（隣接）」へ辿る処理です。再帰は直感的ですが、スタックあふれや制御の難しさが出ます。非再帰パターンでは、キュー（BFS）やスタック（DFS）を使って自分で「探索の順序」を管理し、Stream と組み合わせて宣言的に整形・出力します。重要ポイントは、訪問済み集合でループを防ぐ、レベル（深さ）ごとに流す、重い処理は短絡や早期停止で抑える、の3つです。
ツリー探索の基本（再帰なしで BFS/DFS）
幅優先探索（BFS）をキューで回し、Stream で整形
BFS は「近いノードから順に」調べる方法です。非再帰ではキュー（Deque）を使い、取り出し→子を追加を繰り返します。Stream は「結果の整形・出力」に使います。
import java.util.*;
import java.util.function.Function;
class Node {
final String name;
final List<Node> children;
Node(String name, List<Node> children) { this.name = name; this.children = children; }
}
static List<Node> bfs(Node root) {
List<Node> order = new ArrayList<>();
Deque<Node> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
Node cur = q.removeFirst();
order.add(cur);
for (Node ch : cur.children) q.addLast(ch);
}
return order;
}
static void mainBfs(Node root) {
bfs(root).stream()
.map(n -> n.name)
.forEach(System.out::println);
}
この形は再帰を使わず、要素に対する処理は Stream に乗せて読みやすさと整形の自由度を確保します。
深さ優先探索（DFS）をスタックで回す
DFS は「深く潜ってから戻る」探索です。非再帰ではスタック（Deque を後入れ先出し）を使います。
static List<Node> dfs(Node root) {
List<Node> order = new ArrayList<>();
Deque<Node> st = new ArrayDeque<>();
st.push(root);
while (!st.isEmpty()) {
Node cur = st.pop();
order.add(cur);
// 子を逆順で push すると、元の順序で訪問されやすい
List<Node> cs = cur.children;
for (int i = cs.size() - 1; i >= 0; i--) st.push(cs.get(i));
}
return order;
}
static void mainDfs(Node root) {
dfs(root).stream()
.map(n -> n.name)
.forEach(System.out::println);
}
スタックの操作で「探索順」を完全に制御できるため、再帰の制約から解放されます。
グラフ探索（サイクル対応と早期停止）
訪問済み集合でサイクルを防ぎ、BFS を安全化
グラフは戻り辺・サイクルがあるので、訪問済み（visited）を必ず持ちます。BFS を例にすると以下です。
class GNode {
final String id;
final List<GNode> adj;
GNode(String id, List<GNode> adj) { this.id = id; this.adj = adj; }
}
static List<GNode> bfsGraph(GNode start) {
List<GNode> order = new ArrayList<>();
Set<GNode> visited = new HashSet<>();
Deque<GNode> q = new ArrayDeque<>();
visited.add(start);
q.add(start);
while (!q.isEmpty()) {
GNode cur = q.removeFirst();
order.add(cur);
for (GNode next : cur.adj) {
if (visited.add(next)) q.addLast(next); // 初訪問だけ追加
}
}
return order;
}
visited.add(next) の戻り値（true 初回）を使えば、追加と重複排除を一発で行えます。
条件成立で早期停止（ターゲット探索×短絡）
ターゲット発見で探索を止めたい場合、ループ中に break します。Stream は最終整形のみに使うのが安全です。
static Optional<GNode> bfsFind(GNode start, java.util.function.Predicate<GNode> cond) {
Set<GNode> visited = new HashSet<>();
Deque<GNode> q = new ArrayDeque<>();
visited.add(start);
q.add(start);
while (!q.isEmpty()) {
GNode cur = q.removeFirst();
if (cond.test(cur)) return Optional.of(cur);
for (GNode next : cur.adj) {
if (visited.add(next)) q.addLast(next);
}
}
return Optional.empty();
}
探索自体は命令的に書き、結果を Optional にし、後段は Stream で扱いやすくします。
レベル（深さ）単位の探索を Stream 化する
BFS の「レベル」を保ちながら処理（スライディング風）
レベルごとに処理したい場合、キューを「今レベル / 次レベル」に分けて回します。各レベルのノードを Stream 化して整形できます。
static void bfsLevels(Node root) {
List<Node> curLevel = List.of(root);
while (!curLevel.isEmpty()) {
// レベルの整形や集計は Stream で
String line = curLevel.stream().map(n -> n.name).collect(java.util.stream.Collectors.joining(", "));
System.out.println(line);
List<Node> nextLevel = new ArrayList<>();
for (Node n : curLevel) nextLevel.addAll(n.children);
curLevel = nextLevel;
}
}
レベル単位の可視化や集計（件数・平均など）はこの形が読みやすく、再帰不要です。
フラット化（全ノード）を段階的に展開
ツリー/グラフの全ノードを「段階的にフラット化」したい場合、レベルループ内で蓄積して最後に Stream で整形する方法が安全です。
static List<Node> flattenTree(Node root) {
List<Node> all = new ArrayList<>();
List<Node> cur = List.of(root);
while (!cur.isEmpty()) {
all.addAll(cur);
List<Node> next = new ArrayList<>();
for (Node n : cur) next.addAll(n.children);
cur = next;
}
return all;
}
static void mainFlat(Node root) {
flattenTree(root).stream()
.map(n -> n.name)
.sorted()
.forEach(System.out::println);
}
巨大構造なら、整形を逐次（forEach で外へ書き出し）にして材質化を避けます。
実例で身につける非再帰探索
例題 1：ファイルシステム風ツリーの BFS でパス列作成
record FileNode(String name, List<FileNode> children) {}
static List<String> bfsPaths(FileNode root) {
List<String> out = new ArrayList<>();
Deque<Map.Entry<FileNode, String>> q = new ArrayDeque<>();
q.add(Map.entry(root, "/" + root.name()));
while (!q.isEmpty()) {
var e = q.removeFirst();
FileNode cur = e.getKey(); String path = e.getValue();
out.add(path);
for (FileNode ch : cur.children) {
q.addLast(Map.entry(ch, path + "/" + ch.name()));
}
}
return out;
}
static void demoFs(FileNode root) {
bfsPaths(root).stream().forEach(System.out::println);
}
パス情報を一緒にキューへ積むことで、再帰なしで「親パス連結」を維持できます。
例題 2：グラフで最短経路（BFS）を非再帰で復元
static List<GNode> shortestPath(GNode start, GNode goal) {
Set<GNode> visited = new HashSet<>();
Map<GNode, GNode> prev = new HashMap<>();
Deque<GNode> q = new ArrayDeque<>();
visited.add(start);
q.add(start);
while (!q.isEmpty()) {
GNode cur = q.removeFirst();
if (cur.equals(goal)) break;
for (GNode nx : cur.adj) {
if (visited.add(nx)) {
prev.put(nx, cur);
q.addLast(nx);
}
}
}
// 復元
List<GNode> path = new ArrayList<>();
GNode cur = goal;
while (cur != null && (cur.equals(start) || prev.containsKey(cur))) {
path.add(cur);
cur = (cur.equals(start)) ? null : prev.get(cur);
}
Collections.reverse(path);
return path;
}
BFS と「前ノード表」で最短経路を非再帰で復元できます。整形は Stream で行います。
例題 3：条件一致の最初のノードを DFS で高速発見
static Optional<Node> dfsFind(Node root, java.util.function.Predicate<Node> cond) {
Set<Node> visited = new HashSet<>();
Deque<Node> st = new ArrayDeque<>();
st.push(root); visited.add(root);
while (!st.isEmpty()) {
Node cur = st.pop();
if (cond.test(cur)) return Optional.of(cur);
List<Node> cs = cur.children;
for (int i = cs.size() - 1; i >= 0; i--) {
Node next = cs.get(i);
if (visited.add(next)) st.push(next);
}
}
return Optional.empty();
}
早期停止（条件一致で return）を素直に書けるのが非再帰の利点です。
深掘り：正しさ・性能・保守性の勘所
訪問済みの基準を明確化（equals/hashCode と ID）
グラフでは「同一ノード」の判定が要です。ID フィールド、equals/hashCode の実装、参照同一性のどれを採用するかを揃えます。揃わないと visited が効かず、無限ループや重複訪問になります。
巨大構造では逐次出力と短絡を優先
全ノードの材質化（toList）はメモリピークを押し上げます。見たいのが一部なら limit、条件一致で早期停止、forEach でファイル出力など「逐次」設計に寄せます。整形は Stream の強みですが、探索本体は命令的に書いたほうが制御が効きます。
並列は基本的に難しい（共有状態と順序依存）
探索は「共有状態（visited/prev）」「順序（レベル）」に依存するため、素直な並列化は難易度が高いです。並列は前処理（属性計算）に限定し、探索は順次で安全に。必要ならキーごとの独立サブグラフへ分割して並列にし、最後に統合します。
再帰を使わないメリットと限界
メリットはスタック制限からの解放、早期停止が書きやすい、レベル単位の処理が自然、デバッグ容易。一方、コードが多少冗長になりがちです。キュー/スタック操作を小さなヘルパーにまとめ、探索と整形の責務を分離すると保守性が上がります。
テンプレート（そのまま使える雛形）
BFS（ツリー）
static <T> List<T> bfs(T root, java.util.function.Function<T, List<T>> children) {
List<T> out = new ArrayList<>();
Deque<T> q = new ArrayDeque<>();
q.add(root);
while (!q.isEmpty()) {
T cur = q.removeFirst();
out.add(cur);
for (T ch : children.apply(cur)) q.addLast(ch);
}
return out;
}
DFS（ツリー）
static <T> List<T> dfs(T root, java.util.function.Function<T, List<T>> children) {
List<T> out = new ArrayList<>();
Deque<T> st = new ArrayDeque<>();
st.push(root);
while (!st.isEmpty()) {
T cur = st.pop();
out.add(cur);
List<T> cs = children.apply(cur);
for (int i = cs.size() - 1; i >= 0; i--) st.push(cs.get(i));
}
return out;
}
BFS（グラフ、訪問済みあり）
static <T> List<T> bfsGraph(T start,
java.util.function.Function<T, List<T>> adj) {
List<T> out = new ArrayList<>();
Set<T> visited = new HashSet<>();
Deque<T> q = new ArrayDeque<>();
visited.add(start); q.add(start);
while (!q.isEmpty()) {
T cur = q.removeFirst();
out.add(cur);
for (T nx : adj.apply(cur)) {
if (visited.add(nx)) q.addLast(nx);
}
}
return out;
}
レベル処理（BFS レベルごと）
static <T> void bfsLevels(T root,
java.util.function.Function<T, List<T>> children,
java.util.function.Consumer<List<T>> onLevel) {
List<T> cur = List.of(root);
while (!cur.isEmpty()) {
onLevel.accept(cur);
List<T> next = new ArrayList<>();
for (T n : cur) next.addAll(children.apply(n));
cur = next;
}
}
早期停止（ターゲット探索）
static <T> Optional<T> bfsFind(T start,
java.util.function.Function<T, List<T>> adj,
java.util.function.Predicate<T> cond) {
Set<T> visited = new HashSet<>();
Deque<T> q = new ArrayDeque<>();
visited.add(start); q.add(start);
while (!q.isEmpty()) {
T cur = q.removeFirst();
if (cond.test(cur)) return Optional.of(cur);
for (T nx : adj.apply(cur)) if (visited.add(nx)) q.addLast(nx);
}
return Optional.empty();
}
まとめ
非再帰探索は、キュー/スタックで順序を自分で握り、訪問済み集合で安全に回すのが基本です。探索本体は命令的に、整形・出力は Stream に任せると、読みやすく安全で高速な実装になります。レベル処理や早期停止は非再帰の強み。巨大構造では逐次出力と短絡を優先し、並列は前処理に限定。テンプレートを土台に、ツリー/グラフの実データへ子の取り方（children/adj）を差し替えるだけで、現場の探索を安定して組み立てられます。