BFS (Breadth First Search)

BFS (Breadth First Search) 설명:

BFS는 그래프나 트리를 탐색하는 알고리즘 중 하나로, 시작 노드에서 시작하여 인접한 모든 노드를 먼저 탐색하고, 그 다음 레벨의 노드를 탐색하는 방식으로 진행합니다. BFS는 큐를 사용하여 구현됩니다.

BFS의 기본 원칙:
1. 시작 노드를 큐에 넣는다.
2. 큐의 앞부분에서 노드를 제거하고 해당 노드를 방문한다.
3. 해당 노드에 연결된 아직 방문하지 않은 모든 인접 노드를 큐에 넣는다.
4. 큐가 비어있지 않은 동안 2-3단계를 반복한다.

JavaScript에서의 BFS 예제:

let visited = {};  // 방문한 노드를 기록
let graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
};

function bfs(start) {
    let queue = [start];

    while (queue.length > 0) {
        let node = queue.shift();  // 큐의 앞부분에서 노드를 제거

        if (node in visited) continue;  // 이미 방문한 노드는 건너뛴다.
        visited[node] = true;

        console.log(node);  // 현재 노드 출력
        graph[node].forEach(neighbor => {
            if (!(neighbor in visited)) {
                queue.push(neighbor);  // 아직 방문하지 않은 인접 노드를 큐에 추가
            }
        });
    }
}

bfs('A');  // A부터 시작하는 BFS

BFS의 사용 사례:
1. 최단 경로 탐색: 그래프 내의 두 노드 사이의 최단 경로를 찾을 때, 특히 가중치가 없는 그래프에서 유용합니다.
2. 레벨 순서 탐색: 트리에서 각 레벨의 노드를 순서대로 방문할 때 사용됩니다.
3. 연결 요소(Connected Components) 탐색: 그래프 내의 모든 연결 요소를 찾을 때 사용할 수 있습니다.
4. 네트워크 브로드캐스팅: 네트워크에서 모든 노드에 정보를 전달할 때 사용됩니다.

장점:
1. 두 노드 사이의 최단 경로를 찾는 데 유용하다.
2. 시작 노드에서 동일한 거리에 있는 노드를 동일한 순서로 방문합니다.

단점:
1. 모든 가능한 경로를 탐색하는 DFS에 비해 BFS는 더 많은 메모리를 사용할 수 있습니다.

BFS는 특정 노드에서 시작하여 모든 노드를 최단 경로로 방문하는 데 중점을 둡니다. DFS와 비교했을 때, BFS는 특히 최단 경로 문제에서 더 유리한 특성을 갖습니다.