Java 로 구현한 DFS (Depth First Search) 알고리즘

Tree traversal - DFS(Depth First Search)

 

Tree 를 탐색하고자 할때, 사용되는 알고리즘 중에서 DFS 라는 알고리즘이 존재한다.

DFS는 깊이우선 탐색으로서, Tree의 가장 깊숙한 곳까지 탐색하고 나서, 다시 Backtracking이라는 과정을 거치고, 다시 다른 노드들을 탐색하는 방식이다.

이 알고리즘은 미로찾기나 어떤 Grammar의 AST(Abstract Syntax Tree) 를 이용하여 Syntactic Analyzer를 만드는데 활용이 되는 중요한 알고리즘이다.

DFS에 대한 자세한 설명은 아래 링크에서 확인하면 된다.

http://en.wikipedia.org/wiki/Depth-first_search

DFS의 기본적인 Traverse는 아래 그림과 같이 이루어진다.

그래서 방문한 노드들은 A -> B -> D -> E -> C -> F -> G -> I -> J -> H 순서로 이루어진다.

또한 D 에서 E를 방문하기 위해서는 D -> B 로 Backtracking이 이루어지는 것을 알 수 있다.

Backtracking이란 목표 노드가 발견되지 않으면 최근에 방문한 부모노드로 돌아가는 과정을 의미한다.

여기서 Node를 탐색하는 간단한 Java 로 짜여진 소스를 살펴보기로 해보자.

public abstract class Node {

   Node [] children;

   Node parent;

   public void visit();

   public boolean visitAllChild();

   public Node getChild(int index);

   public int getNumChildren();

}

public class SimpleNode extends Node {

  public void visit() { 

    // 적절한 구현이 필요

  }

  public boolean visitAllChild(){ // 모든 자식노드를 방문했는지 를 검사

     // 적절한 구현이 필요

  }

  public Node getChild(int index) { return children[index]; } // Exception 처리 필요

  public int getNumChildren() { return children.length; } // Exception 처리 필요

}

public class DFSRecursive {

   public boolean DFS(Node node) { // Recursive 로 작성된 DFS

        if(node != null) {

            System.out.println(node.getClass().getSimpleName() + " visit.");

        }

        int numChild = node.getNumChildren();

        for(int i = 0; i < numChild; i++){

            Node child = node.getChild(i);                        

            DFS(child);

        }

        if(node != null) {

            System.out.println(node.getClass().getSimpleName() + " has visited");

        }

        return true;

    }

}

public class DFSIterative {

   public boolean DFS(Node node) { // Iterative 로 작성된 DFS

        Stack<Node> nodeStack = new Stack<Node>();

        nodeStack.push(node);

                

        while(!nodeStack.isEmpty()) {

            Node curNode = nodeStack.pop();            

            curNode.visit(); // mark this node 'visit'          

            

            if(curNode.visitAllChild()) {

                // Back Tracking이 수행되는 지점

            }

            

            if(curNode.getNumChildren() > 0) { // has child

                Node [] children = new Node[curNode.getNumChildren()];

                for(int i = children.length - 1; i >= 0; i--) { // expand node

                    children[i] = curNode.getChild(i);

                    nodeStack.push(children[i]);

                }

            }

        }

        return true;

    }

}

Recursive 알고리즘이 Iterative 한 알고리즘보다 구현하기가 훨씬 간단하다는 것을 알 수 있다.

이유는 Node들의 상태를 우리가 일일이 추적할 필요가 없어서이기 때문이다.

Recursive 알고리즘은 함수자체의 Call Stack 을 이용하여 처리가 된다. 하지만, Iterative 한 알고리즘은 우리가 직접 Call Stack을 디자인하고 처리를 해야 하기때문에, 코드의 양도 많아지고 알고리즘도 복잡해 지게 된다.