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

🔍 BFS란?

BFS는 Breadth-First Search의 약자로,
한국어로는 너비 우선 탐색이라고 합니다.

 

📚 뜻 풀이

• "너비 우선"이란 말 그대로,
  어떤 **정점(노드)**에서 시작해서
  **가까운 노드(이웃)**부터 먼저 방문하고,
  점점 멀리 있는 노드로 탐색을 확장해 나가는 방식입니다.

📌 BFS의 동작 방식

1. 시작 노드를 큐(queue)에 넣고
2. 큐에서 하나 꺼낸 뒤
3. 인접한(연결된) 노드들을 전부 한 번씩 방문하면서 큐에 추가
4. 큐가 빌 때까지 반복

💡 BFS의 특징

항목설명

사용 구조	큐 (Queue)
방문 순서	가까운 노드부터
최단거리 구할 수 있음	✅ 가능 (모든 간선 가중치가 동일할 때)
재귀 구조 가능?	❌ 보통 반복문과 큐 사용

 

---

📷 예시 (간단한 그래프)

     1
    / \
   2   3
  /     \
 4       5

• BFS 방문 순서: 1 → 2 → 3 → 4 → 5
  (1의 인접한 2,3 먼저, 그 다음 4,5)

---

🤔 DFS와 차이는?

구분BFS (너비 우선)DFS (깊이 우선)

구조	Queue	Stack (or 재귀)
순서	가까운 노드부터	끝까지 깊게 들어감
최단 거리	✅ 구할 수 있음	❌ 보장되지 않음

 

무방향 그래프 최단거리 찾기 코드 예제

/**
 * n: 노드 갯수, edges: 노드 간선 정보, start: 시작 노드
 */
function(n, edges, start){
	const path = Array.from({length: n+1}, () => []);
    let visited = Array(n+1).fill(false);
    let dist = Array(n+1).fill(-1);
    
    for(let i =0; i<edges.length; i++) {
    	const [a,b] = edges[i];
    	path[a].push(b);
        path[b].push(a); // 방향그래프는 해당 줄 제거
    }
    
    const queue = [start];
    visited[start] = true;
    dist[start] = 0;
    
    while(queue.length){
    	const cur = queue.shift();
        
        for (let i =0; i< path[cur].length; i++){
        	const next = path[cur][i];
            if (!visited[next]){
            	visited[next] = true;
                dist[next] = dist[cur]+1;
                queue.push(next);
            }
        }
    }
    
    return dist.slice(1);
}

 

자기 자신에게 돌아오는 간선이 있는 노드가 있다면 별도의 알고리즘 구현 필요.