BFS vs DFS

이진트리에 해당하는 검색 알고리즘은 2가지가 있다: 너비 우선 탐색(Breath-first Search), 깊이 우선 탐색 (Depth-first Search).

BFS는 노드를 루트노드부터 시작하여 레벨단계로 검색합니다. 즉, 해당노드이 자식노드를 먼저 다 확인 한 후, 그 자식노드의 자식노드를 검색하는 형태입니다. 이 과정은 모든 노드들을 검색하거나, 검색 조건을 만족할때 까지 진행합니다.

BFS : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

DFS는 다르게 행동합니다. DFS는 루트노드부터 시작하여 제일 왼쪽 리프를 우선적으로 확인하고, 오른쪽 노드를 확인합니다.

DFS : 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

기본 이진 트리에 BFS를 Queue 자료 구조를 사용하여 적용한 모습입니다.

Public BinaryNode<T> bfs(Predicate<T> predicate) {
	Queue<BinaryNode<T>> queue = new LinkedList<>();
    queue.offer(this);
    while (!queue.isEmpty()){
    	BinaryNode<T> node = queue.poll();
        if ( predicate.test(node.data) ) return node;
        if ( node.left != null ) queue.offer(node.left);
        if ( node.right != null ) queue.offer(node.right);
     }
     return null;
}

만약 Queue를 Stack으로 바꾼다면, DFS의 모습입니다.

public BinaryNode<T> dfs(Predicate<T> predicate) {
	Stack<Binary<T>> stack = new Stack();
    stack.push(this);
    while(!stack.isEmpty()){
    	BinaryNode<T> node = stack.pop();
        if ( predicate.test(node.data)) return node;
        if ( node.right != null ) stack.push(node.right);
        if ( node.left != null ) stack.push(node.left);
    }
    return null;
 }

예를 들어, 당신은 다음에 오는 트리에서 1의 값을 가진 노드를 찾는다고 가정해보자.

노란색으로 칠한 것들이 우리가 원하는 노드를 찾기위해 검색 되어진 노드들입니다. 여기에서는, DFS에서는 검색 하는 동안의 노드들이 적게 요구되었다. 다른 상황에서는 DFS가 더 많은 프로세스가 요구되기도 한다.

파이썬을 이용해서 DFS를 해보았다.

def dfs(binaryTreeArray):
    stack = []
    seen = []
    start = binaryTreeArray[0]
    stack.append(start)

    while(len(stack) != 0):

        current = stack.pop()
        currentIndex = binaryTreeArray.index(current)
        if current not in seen:
            seen.append(current)
            print(current)

        rightIndex = currentIndex*2 + 2
        leftIndex = currentIndex*2 + 1

        if rightIndex < len(binaryTreeArray):
            right = binaryTreeArray[rightIndex]  
            if right is not None:
                stack.append(right)     

        if leftIndex < len(binaryTreeArray):
            left = binaryTreeArray[leftIndex]
            if left is not None:
                stack.append(left)