[자료구조] BFS 이란?

너비 우선 탐색 (BFS) 이란?

 

너비 우선 탐색(BFS, Breadth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 시작 노드에서부터 인접한 모든 노드를 먼저 탐색하고, 그 다음 레벨의 노드로 넘어가며 탐색을 진행합니다. 즉, 깊이보다 너비를 우선으로 탐색하는 방식입니다.

 

BFS의 주요 특징

 

1. 큐(queue) 사용

 

BFS는 큐 자료구조를 사용하여 구현됩니다. 시작 노드를 큐에 넣고, 큐가 빌 때까지 노드를 하나씩 빼면서 탐색을 진행합니다.

 

2. 너비 우선

 

BFS는 한 레벨의 모든 노드를 먼저 탐색하며, 그 다음 레벨로 넘어갑니다. 따라서 가장 가까운 노드부터 탐색하여 최단 경로 문제에 유용하게 사용됩니다.

 

3. 모든 노드 탐색

 

BFS를 통해 모든 노드를 탐색할 수 있으며, 그래프나 트리가 연결되어 있을 때 주로 사용됩니다.

 

BFS는 주로 다음과 같은 문제를 해결하는 데 사용됩니다.

- 최단 경로 찾기
- 그래프 순회
- 노드의 연결 여부 확인

이제 파이썬 코드를 통해 BFS를 구현하고 예시를 살펴보겠습니다.

from collections import deque

# 그래프를 인접 리스트로 표현
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 방문한 노드를 추적하기 위한 리스트
visited = []

# BFS 함수 정의
def bfs(start_node):
    global visited
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

# 시작 노드를 지정하여 BFS 수행
print("BFS 탐색 결과:")
bfs('A')

 

 

이 코드에서는 A 노드를 시작으로 BFS를 수행하고, 방문한 노드는 visited 리스트에 추가하여 중복 방문을 피합니다.

 

큐를 사용하여 인접한 노드를 탐색하며, 결과적으로 BFS를 통해 그래프를 순회하며 노드를 출력하게 됩니다.

 

 

 

다른 방식의 코드

def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나 씩 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

graph_dfs = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

bfs(graph_bfs, 1, visited_bfs)