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

BFS(너비 우선 탐색)

---

 너비 우선 탐색은 루트 노드 (혹은 임의의 노드)에서 시작해서 인접한 노드들을 우선으로 방문하여 탐색하는 알고리즘이다.  가능한 한 넓게 탐색을 진행하는 방식이다. 

BFS의 동작 방식

---

1. 시작 노드 선택
   • 탐색할 노드를 선택하고 해당 노드를 큐에 추가
2. 방문 및 큐 연산
   • 큐에서 노드를 꺼내고 방문 처리
   • 현재 방문중인 노드의 인접 노드들을 확인하여 방문되지 않았다면 큐에 추가
3. 반복
   • 큐가 비어 있지 않는 동안 위 과정을 반복수행
   • 큐가 비었다면 탐색이 완료됨을 의미
4. 탐색 종료
   • 모든 노드를 방문하거나, 특정 조건을 만족하는 노드를 찾으면 탐색이 종료됨. 

BFS는 Queue 자료구조를 사용하여 구현한다. 

BFS 구현 예시

---

인접 리스트로 표현된 그래프가 있다고 하자

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

 

Python의 collection 라이브러리의 deque를 사용하여 큐 자료구조를 사용하자

from collections import deque

def bfs(graph, start):
	# 방문한 노드를 기록할 집합
	visited = set()
    # 큐를 초기화 (start 삽입)
    queue = deque([start])
    
    # 큐가 비어있지 않은 동안 반복
    while queue:
    	# 큐에서 노드를 꺼냄 (큐는 선입선출 자료구조)
    	node = queue.popleft()
        # 해당 노드가 방문된적 없다면
        if node not in visited:
        	# 해당 노드를 방문하고 방문 처리
        	print(node, end = " ")
            visited.add(node)
            
            # 현재 방문중인 노드의 인접 노드들에 대해
            for neighbor in graph[node]:
            	# 방문된적 없는 노드라면 큐에 추가
            	if neighbor not in visited:
                	queue.append(neighbor)

bfs(graph, 'A')

• 특징
  • 최단 경로를 보장한다. 
    • BFS는 큐 자료구조를 사용하여 그래프를 레벨 순서로 탐색한다. 
      • 레벨 0 : 시작 노드
      • 레벨 1 : 시작 노드의 인접 노드
      • 레벨 2 : 레벨 1 노드의 인접노드 .....
      • 순서로 탐색이 되기 때문에 노드가 탐색될 때마다 그 노드까지의 거리는 최단 거리를 보장한다.

BFS의 시간복잡도

---

BFS의 시간 복잡도는 그래프의 노드 수 (V), 간선의 수 (E)에 비례한다. 

각 노드와 간선들은 한번씩만 방문되기 때문에 최종적인 BFS의 시간복잡도는 O(V+E) 이다. 

 

 

 

2024.08.20 - [🤔알고리즘] - [알고리즘] DFS (깊이 우선 탐색)

[알고리즘] DFS (깊이 우선 탐색)