探索アルゴリズム (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 getValue();

        Tree getLhs();

        Tree getRhs();

        void walkPreorder(TreeWalker walker);

        void walkInorder(TreeWalker walker);

        void walkPostorder(TreeWalker walker);

    }

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

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

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

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

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

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

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

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

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

    private static class Symbol implements Tree {
        private String value;


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

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

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

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

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

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

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

    private static interface ExpressionWalker extends TreeWalker {
    }
}

2010年5月11日 | カテゴリー：アルゴリズム