BFS 너비 우선 탐색: 과정 이해하고 적용해보기

알아보기

Breadth-First Search 너비 우선 탐색이다.
임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.

BFS 는 재귀적으로 동작하지 않는다.
위의 그림에서도 볼 수 있듯이, 같은 레벨에 있는 노드들을 방문한 뒤 다음 레벨의 노드들을 방문하는 방식이다.

노드들은 큐에 집어넣어, 레벨이 바뀌면 뺀다. 이 과정은 아래의 그림을 통해 이해해 볼 수 있다.

적용하기

미로의 최단거리, 그래프 최단거리등 최단거리를 구하고자 할 때 사용된다.

말단 노드까지의 가장 짧은 경로를 구해보자.

 

import java.util.LinkedList;
import java.util.Queue;

class Node{
    int data;
    Node2 lt, rt;
    public Node2(int val){
        data = val;
        lt = rt = null;
    }
}
public class Main {
    Node root;
    public static int BFS(Node root){
        Queue<Node> queue = new LinkedList<>();
        int L=0;
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i=0; i<len; i++){
                Node node = queue.poll();
                if(node.lt != null ){
                    queue.offer(node.lt);
                }if(node.rt != null ){
                    queue.offer(node.rt);
                }if(node.lt == null && node.rt ==null){
                    return L;
                }

                L++;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Main tree = new Main();
        tree.root = new Node2(1);
        tree.root.lt = new Node2(2);
        tree.root.rt = new Node2(3);
        tree.root.lt.lt = new Node2(4);
        tree.root.lt.rt = new Node2(5);
        System.out.println(Main.BFS(tree.root));
    }
}

 

그래프 탐색과 큐를 그림으로 나타내 보았다.