深さ優先探索と幅優先探索の簡単な実装方法

深さ優先探索と幅優先探索は、実は簡単に実装することができます。

次のインターフェースを実装したクラスで例を見ていきます。

interface Node {
  public String getName();
  public List<Node> getChildren();
}

深さ優先探索

深さ優先探索は以下の手順で実装できます。

1. スタックを用意する
2. スタックに最初の要素を入れる(push)
3. スタックから要素を取り出す(pop)
4. 要素に対して処理をする
5. 要素の子供をスタックに入れる(push)
6. スタックがカラになるまで3〜5を繰り返す

rootNodeから深さ優先探索でnameを出力するプログラムは次のようになります。

Deque<Node> stack = ArrayDeque<Node>();
stack.push(rootNode);
while(!stack.isEmpty()) {
  Node node = stack.pop();
  System.out.println(node.getName());
  for(Node childNode : node.getChildren()) {
    stack.push(childNode);
  }
}

幅優先探索

1. キューを用意する
2. キューに最初の要素を入れる(offer)
3. キューから要素を取り出す(poll)
4. 要素に対して処理をする
5. 要素の子供をキューに入れる(offer)
6. キューがカラになるまで3〜5を繰り返す

rootNodeから幅優先探索でnameを出力するプログラムは次のようになります。

Deque<Node> queue = ArrayDeque<Node>();
queue.offer(rootNode);
while(!queue.isEmpty()) {
  Node node = queue.poll();
  System.out.println(node.getName());
  for(Node childNode : node.getChildren()) {
    queue.offer(childNode);
  }
}

まとめ

こうしてみると深さ優先探索になるか幅優先探索になるかは、スタックを使うかキューを使うかで決まるみたいですね。今回はJavaで書きましたが、他の言語でもだいたい同じように実装できるので、流れだけ押さえとくといいかもしれません。