TIL-2024.03.10 - BFS (너비 우선 탐색)

------- BFS

설명:

• BFS는 너비 우선으로 그래프를 탐색하는 알고리즘.
• 한 번에 한 레벨씩 탐색하며, 각 레벨에서 모든 노드를 방문한 후에 다음 레벨로 이동
• BFS는 큐(queue)를 사용하여 구현

 

동작 원리:

• 시작 노드를 큐에 넣고 방문 표시.
• 큐가 빌 때까지 다음을 반복:
  > 큐에서 하나의 노드를 빼기.
  > 해당 노드와 인접한 모든 노드를 방문하고 큐에 넣기.
• 모든 노드가 방문될 때까지 반복.

 

특징:

• 최단 경로를 찾을 때 유용합니다.
• 메모리를 많이 사용할 수 있습니다.
• 큐를 사용하므로 반복적으로 구현이 쉽습니다.

 

예제:

 

function bfs(graph, start) {
    let visited = new Set();
    let queue = [start];

    while (queue.length > 0) {
        let current = queue.shift();
        if (!visited.has(current)) {
            visited.add(current);
            console.log(current);

            let neighbors = graph[current];
            for (let neighbor of neighbors) {
                queue.push(neighbor);
            }
        }
    }
}

// 예제 그래프
let graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['E', 'F'],
    'D': [],
    'E': [],
    'F': []
};

console.log("BFS 결과:");
bfs(graph, 'A');

 

 

사용 이유:

1. 최단 경로 탐색: BFS는 너비 우선으로 탐색하기 때문에 최단 경로를 찾는 데에 적합. 예를 들어, 최소 이동 경로, 최소 거리 등.
2. 단계별 탐색: BFS는 레벨별로 탐색하기 때문에 특정 단계까지의 모든 가능한 경로를 탐색할 때 유용.
3. 최단 경로 문제: 가중치가 없는 그래프에서 최단 경로 문제를 해결할 때 BFS를 사용