株式会社イーブ｜未経験・転職の方も就職可能。Javaプログラマー育成のエキスパート

HOME｜ JAVA技術者育成｜ システム開発｜ 求人情報｜ 個人情報保護｜

探索アルゴリズム (3)

トップページ > Java技術者育成 > アルゴリズム > 探索アルゴリズム (3)
前回まではリスト探索を行ないましたが、今回からはツリー探索を行ないます。
今回紹介するのは深さ優先探索 (DFS, Depth-First Search) です。
深さ優先探索とはその名のとおり、ツリー構造の深さの方向を優先して探索を行なうアルゴリズムです。深さ優先探索は再帰処理と相性がよく、次のように手順を再帰的に繰り返すだけで実装することができます。
  1. 走査対象のツリーをスタックにプッシュする。
  2. 走査対象のツリーがリーフであれば、これをスタックからポップする。
  3. 走査対象のツリーがノードであれば、このノードが指すサブツリーを全て走査して、その後にスタックからポップする。
以下のサンプルでは、式 (a + b) * (c - d) を構文解析した結果の抽象構文木があると仮定して、これを走査してそれぞれのノードやリーフの値を順番に出力します。
ツリー構造を走査するとき、どのタイミングでその値を処理するかによって値を処理される順番が変わるため、出力される順番が変わります。
特に後置記法で出力するものは、コンパイラで中置記法の式を読み込んで、計算機が処理しやすい順序に変換するためによく使われます。また、この順序でグラフ構造に対して深さ優先探索を適用すると、トポロジカルソートになります。(ただし循環構造には気をつけなければいけませんが)
また、下記で出力される中置記法は括弧が無いため、演算子の優先度を考慮すると正しい出力になりません。

search/tree/DepthFirstSearch.java
package search.tree;

public class DepthFirstSearch {

    public static void main(String[] args) {
        // (a + b) * (c - d)
        Expression expr = new Expression("*", 
                new Expression("+", new Symbol("a"), new Symbol("b")),
                new Expression("-", new Symbol("c"), new Symbol("d")));
        ExpressionWalker walker = new ExpressionWalker() {

            @Override
            public void process(String value) {
                System.out.print(value);
            }
        };
        // 前置記法
        System.out.println("Prefix Notation");
        expr.walkPreorder(walker);
        System.out.println();
        System.out.println();

        // 中置記法
        System.out.println("Infix Notation");
        expr.walkInorder(walker);
        System.out.println();
        System.out.println();

        // 後置記法
        System.out.println("Postfix Notation");
        expr.walkPostorder(walker);
    }

    private static interface Tree<T> {
        T getValue();

        Tree<T> getLhs();

        Tree<T> getRhs();

        void walkPreorder(TreeWalker<T> walker);

        void walkInorder(TreeWalker<T> walker);

        void walkPostorder(TreeWalker<T> walker);

    }

    private static interface TreeWalker<T> {
        void process(T value);
    }

    private static class Expression implements Tree<String> {
        private String value;
        private Tree<String> lhs;
        private Tree<String> rhs;

        Expression(String value, Tree<String> lhs, Tree<String> rhs) {
            this.value = value;
            this.lhs = lhs;
            this.rhs = rhs;
        }

        @Override
        public Tree<String> getLhs() {
            return this.lhs;
        }

        @Override
        public Tree<String> getRhs() {
            return this.rhs;
        }

        @Override
        public String getValue() {
            return this.value;
        }

        @Override
        public void walkPreorder(TreeWalker<String> walker) {
            walker.process(this.getValue());
            this.getLhs().walkPreorder(walker);
            this.getRhs().walkPreorder(walker);
        }

        @Override
        public void walkInorder(TreeWalker<String> walker) {
            this.getLhs().walkInorder(walker);
            walker.process(this.getValue());
            this.getRhs().walkInorder(walker);
        }

        @Override
        public void walkPostorder(TreeWalker<String> walker) {
            this.getLhs().walkPostorder(walker);
            this.getRhs().walkPostorder(walker);
            walker.process(this.getValue());
        }
    }

    private static class Symbol implements Tree<String> {
        private String value;

        Symbol(String value) {
            this.value = value;
        }

        @Override
        public Tree<String> getLhs() {
            return null;
        }

        @Override
        public Tree<String> getRhs() {
            return null;
        }

        @Override
        public String getValue() {
            return this.value;
        }

        @Override
        public void walkPreorder(TreeWalker<String> walker) {
            walker.process(this.getValue());
        }

        @Override
        public void walkInorder(TreeWalker<String> walker) {
            walker.process(this.getValue());
        }

        @Override
        public void walkPostorder(TreeWalker<String> walker) {
            walker.process(this.getValue());
        }
    }

    private static interface ExpressionWalker extends TreeWalker<String> {
    }

}

更新日時: 2010年5月11日 23:48


■[アルゴリズム]内の前後の記事
↑ 探索アルゴリズム (4)
→ 探索アルゴリズム (3)
↓ 探索アルゴリズム (2)


■更新日時での前後の記事
↑ 5月12日　お天気
→ 探索アルゴリズム (3)
↓ 5月11日　お天気