BFS

너비 우선 탐색(BFS, Breadth-First Search)은 그래프나 트리를 탐색할 때 사용하는 알고리즘 중 하나입니다. BFS는 이름에서 알 수 있듯이 '너비를 우선으로 탐색'하는 방법으로, 시작 노드에서 가장 가까운 노드부터 차례대로 탐색합니다.

BFS의 특징:

레벨 순서 탐색: 시작 노드를 기준으로 거리에 따라 레벨을 정하고, 각 레벨을 순서대로 탐색합니다.
큐 사용: BFS는 큐(Queue)를 사용하여 노드를 관리합니다. 큐의 성질(First-In, First-Out) 때문에 가장 먼저 들어온 노드가 먼저 나가게 되어, BFS의 너비 우선 탐색 순서를 만족시키게 됩니다.

BFS의 동작 방식

1. 시작 노드를 큐에 넣습니다.
2. 큐에서 노드를 꺼냅니다. (deque)
3. 해당 노드와 인접하며 아직 방문하지 않은 노드를 모두 큐에 넣습니다.
4. 큐가 빌 때까지 2-3단계를 반복합니다.

BFS의 활용 예

1. 최단 경로 탐색: 무방향 그래프에서 두 노드 간의 최단 경로나 최단 거리를 찾는 문제에 사용됩니다.
2. 네트워크 브로드캐스팅: 네트워크에서 최단 시간 내에 메시지를 모든 노드에 전달해야 할 때 사용됩니다.
3. 소셜 네트워크 서비스: 특정 사용자와 친구 관계에 있는 모든 사용자를 찾거나, 특정 두 사용자간의 친구 관계를 파악할 때 사용됩니다.

Python으로 BFS 구현 시 주로 collections 모듈의 deque를 사용하여 큐를 구현하며, 이를 통해 효율적인 큐 연산을 지원받아 BFS를 수행합니다.

그래프 예와 파이썬 표현

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

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']}
"""

BFS알고리즘 구현

자료구조 큐를 활용하여 need_visit큐와 visited큐, 두 개의 큐를 생성

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

bfs(graph, 'A')

# ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

구현2

from collections import deque

def bfs(graph, start_node):
    visited = set()    # 이미 방문한 노드를 저장하기 위한 집합
    queue = deque([start_node])  # 시작 노드로 초기화

    while queue:
        node = queue.popleft()  # 현재 노드를 큐에서 제거
        if node not in visited:  # 현재 노드가 방문한 적이 없다면
            visited.add(node)  # 방문 기록에 추가
            queue.extend(graph[node])  # 해당 노드의 이웃을 큐에 추가

    return visited

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

print(bfs(graph, 'A'))  # 출력: {'A', 'B', 'C', 'D', 'E', 'F', 'G'}