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

🔍 너비 우선 탐색(Breadth-First Search)

너비 우선 탐색은 컴포넌트의 모든 정점을 한 번씩 순회하는 용도로 쓰인다. DFS와 대립되는 성질을 갖고 있으며, 사용되는 곳도 매우 다르다.

그러나 DFS와 겹치는 용도가 있는데, BFS 역시 컴포넌트의 개수를 세거나 각 컴포넌트의 크기를 구하는 데는 사용 가능하다.

DFS가 깊이를 중시한다면 BFS는 넓이를 중시한다.

너비 우선 탐색은 루트 노드(혹은 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.

주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.

 

📌 너비 우선 탐색의 특징

• BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색하기 때문에 직관적이지 않은 면이 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다.
  • 선입선출(FIFO) 원칙으로 탐색

 

📌 너비 우선 탐색 과정

1. a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
   • 큐에 방문된 노드를 삽입(enqueue)한다.
   • 초기 상태의 큐에는 시작 노드만이 저장
     • 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
2. 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
   • 큐에서 꺼낸 노드를 방문한다.
   • 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
     • 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
   • 큐에 방문된 노드를 삽입(enqueue)한다.
3. 큐가 소진될 때까지 계속한다.

 

 

📌 BFS의 시간 복잡도

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)
• 깊이 우선 탐색(DFS)과 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

 

📌 예시 코드

const graph = { 
	A: ["B", "C"], 
	B: ["A", "D"], 
	C: ["A", "G", "H", "I"],
	D: ["B", "E", "F"], 
	E: ["D"], 
	F: ["D"], 
	G: ["C"], 
	H: ["C"], 
	I: ["C", "J"], 
	J: ["I"] 
}; 

const bfs = (graph, startNode) => { 
	let visited = []; // 탐색을 마친 노드들 
	let needVisit = []; // 탐색해야할 노드들 
	
	needVisit.push(startNode); // 노드 탐색 시작 
	
	while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면 
		const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
		if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면 
			visited.push(node); 
			needVisit = [...needVisit, ...graph[node]]; 
		} 
	} 
	return visited; 
}; 

console.log(bfs(graph, "A")); 
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]