BFS(너비 우선 탐색) 알고리즘

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

public class BFSAlgorithm {
    static class Node {
        int data;
        Node left, right;

        Node(int data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    static void BFS(Node root) {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.print(node.data + " ");

            if (node.left != null) {
                queue.add(node.left);
            }

            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        System.out.println("BFS traversal of binary tree is:");
        BFS(root);
    }
}

 

이 구현에서는 Node 클래스를 사용하여 이진 트리의 노드를 나타내고, BFS 함수를 사용하여 큐를 이용한 BFS 탐색을 수행합니다. 큐를 구현하기 위해 LinkedList 클래스를 사용합니다.

우선 큐 객체를 만들고, 루트 노드를 큐에 추가합니다. 그런 다음 큐가 비어 있지 않을 때까지 반복하여, 큐에서 노드를 꺼내어 해당 노드의 값을 출력하고, 해당 노드의 자식 노드들을 큐에 추가합니다. 이 과정을 반복하여 BFS 탐색을 수행합니다.

 

 

 

- 순회 순서 : A > B > C > D > E > F > G

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문

 

장점 :

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다.
• 단순 검색 속도가 DFS보다 빠르다.
• 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다고 해도 최단 경로를 반드시 찾을 수 있다.

단점 :

• 노드의 수가 늘어나면 탐색해야 하는 노드 또한 많아지기 때문에 비효율적이다.
• 다음에 탐색할 정점들을 큐에 저장해야 하므로 저장공간이 많이 필요하다.