BFS

BFS는 시작 노드로부터 시작하여 인접한 모든 노드를 먼저 탐색하는 방식입니다. 이는 큐(queue) 자료구조를 사용하여 구현됩니다.

 

1. 시작 노드를 큐에 넣고 방문 표시를 합니다.
3. 큐가 빌 때까지 다음을 반복합니다:
   - 큐에서 하나의 노드를 꺼냅니다.
   - 해당 노드의 인접한 모든 미방문 노드들을 큐에 넣고 방문 표시를 합니다.

 

실전)

from collections import deque

# 그래프 정의
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': [],
    'D': [],
    'E': []
}

# 시작 노드 설정
start_node = 'A'

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        current_node = queue.popleft()
        print(current_node)  # 현재 노드 방문

        for neighbor in graph[current_node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)


print("BFS 탐색 결과:")
bfs(graph, start_node)

 

 

- BFS vs. DFS

BFS와 DFS는 그래프 탐색 알고리즘으로, 각각의 특성에 따라 다른 상황에 사용됩니다.

1. 너비 우선 탐색 (BFS):
- 가까운 노드부터 탐색해야 할 때 사용합니다. 즉, 시작 노드에서 목표 노드까지의 최단 경로를 찾을 때 유용합니다.
- 최단 경로 문제나 최소 비용 문제에서 많이 사용됩니다.
- 레벨 단위로 탐색하기 때문에 깊이에 제한이 있는 경우에 유용합니다.

 

2. 깊이 우선 탐색 (DFS):
- 그래프에서 깊이를 우선적으로 탐색해야 할 때 사용합니다.
- 무한 그래프나 깊이가 매우 깊은 그래프를 탐색할 때 적합합니다.
- 모든 경로를 탐색하고자 할 때 사용할 수 있습니다.
- 예를 들어, 미로 찾기나 그래프에서 사이클을 찾는 문제에 유용합니다.