[JAVA] 이진트리에서 BFS 구현하기

BFS란?

Bredath First Serach

한국말로 번역하면 너비 우선 탐색이다.

 

너비 우선 탐색은 저번 포스팅 했던 DFS와 마찬가지로 트리나 그래프를 방문 또는 탐색하는 방법이다.

탐색 방법은 다음과 같다.

 

 

1. 루트에서 시작하여 자식 노드들을 [1]에 저장한다.

2.[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다.

3.[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다.

4.위의 과정을 반복하여 모든 노드를 방문하면 탐색을 마친다.

 

 

 

출처:나무위키

DFS와 BFS의 탐색 순서의 차이를 확연하게 알 수 있다.

DFS와의 차이점 중 가장 큰 것은, 여러 갈래 중 경로의 길이가 무한하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료가 불가능하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다.

 

---

JAVA에서 BFS 구현하기

 

    static Node root;
    public static void BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L=0;
        while(!Q.isEmpty()){
            int len = Q.size();
            System.out.print(L+" : ");
            for(int i=0; i<len; i++){
                Node cur = Q.poll();
                System.out.print(cur.data+" ");
                if(cur.lt!=null) Q.offer(cur.lt);
                if(cur.rt!=null) Q.offer(cur.rt);
            }
            L++;
            System.out.println();
        }
    }

root 노드는 제일 위(level 0)의 노드를 가리킨다.

Queue를 하나 만들어두고, root 노드를 집어 넣는다.

Queue에 들어가있는 각각의 노드들의 왼쪽,오른쪽 자식노드들을 또 Queue에 집어넣는다.

이 행동은 더이상 Queue가 빌때까지 계속된다.

 

Queue의 선입선출이라는 특성을 이용하여 BFS를 구현하였다.