深さ優先探索(DFS)と幅優先探索(BFS)について、実装方法をよく忘れてしまうので、ここに簡単な例題を解く際の実装例としてメモしておく。
今回は、以下のようなツリーをDFSとBFSで探索することにする。
深さ優先探索(DFS)では、以下の順番で探索する。
0 -> 1 -> 3 -> 4 -> 2 -> 5 ->6
幅優先探索(BFS)では、以下の順番で探索する。
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
上記のように探索して、探索結果を表示するプログラムをJavaで作成した。
import java.util.ArrayDeque;
import java.util.Deque;
public class Dfs {
public void execDfs(TreeNode root) {
if (root == null) {
throw new IllegalArgumentException("Nothing to print because input tree is null.");
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.println(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static void main(String[] args) {
TreeNode root = new TreeNode(0);
root.left = new TreeNode(1);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right = new TreeNode(2);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);
new Dfs().execDfs(root);
}
}
これを実行すると、
0 -> 1 -> 3 -> 4 -> 2 -> 5 ->6
と表示される。
深さ優先探索では、スタックを使用するため、ArrayDeque をスタックとして使用している。
import java.util.ArrayDeque;
import java.util.Deque;
public class Bfs {
public void execBfs(TreeNode root) {
if (root == null) {
throw new IllegalArgumentException("Nothing to print because input tree is null.");
}
Deque<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public static void main(String[] args) {
TreeNode root = new TreeNode(0);
root.left = new TreeNode(1);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right = new TreeNode(2);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);
new Bfs().execBfs(root);
}
}
これを実行すると、
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
と表示される。
幅優先探索は、キューを使用するため、ArrayDeque をキューとして使用している。