너비 우선 탐색 (BFS, Breadth-First Search)
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문합니다.
주로 큐(Queue)를 이용하여 구현하며, 최단 경로를 찾을 때 많이 사용됩니다.
const graph = {
1: [2, 3],
2: [4, 5],
3: [6, 7],
4: [],
5: [],
6: [],
7: []
};
function bfs(graph, startNode) {
const visited = new Set([startNode]);
const queue = [startNode];
const result = [];
while (queue.length > 0) {
const node = queue.shift(); // 큐에서 꺼내기
result.push(node);
console.log(`현재 방문 노드: ${node}`);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor); // 큐에 삽입
}
}
}
return result;
}
console.log("BFS 탐색 결과:", bfs(graph, 1).join(" -> "));