너비 우선 탐색 편집하기

너비 우선 탐색(Breadth-First Search, BFS)은 그래프 탐색 알고리즘 중 하나로, 루트 노드에서 시작하여 인접한 노드를 먼저 탐색한 후 점차 멀리 있는 노드를 탐색하는 방식이다.
[[파일:그래프 순회.png|섬네일|BFS와 DFS]]

==알고리즘==
너비 우선 탐색은 일반적으로 큐(Queue)를 사용하여 구현된다. 기본적인 과정은 다음과 같다.
#탐색을 시작할 노드를 큐에 삽입하고 방문 표시를 한다.
#큐에서 노드를 꺼내 해당 노드의 인접 노드들을 확인한다.
#방문하지 않은 인접 노드를 큐에 삽입하고 방문 표시를 한다.
#큐가 빌 때까지 위 과정을 반복한다.
==예제 코드==
다음은 Python을 사용한 너비 우선 탐색 구현 예제이다.<syntaxhighlight lang="python">
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 그래프 예제
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C'],
    'G': ['C']
}

bfs(graph, 'A')
</syntaxhighlight>
==특성==
*최단 경로 보장: 무가중 그래프에서 시작 노드로부터 특정 노드까지의 최단 경로를 찾을 수 있다.
*시간 복잡도: O(V + E) (V는 정점 개수, E는 간선 개수)
*공간 복잡도: O(V)
==활용==
*최단 경로 탐색 (예: GPS 네비게이션, 미로 찾기)
*네트워크에서 데이터 탐색
*웹 크롤링
*AI의 상태 공간 탐색 (예: 체스, 퍼즐 문제 해결)
==같이 보기==
*[[깊이 우선 탐색]]
*[[다익스트라 알고리즘]]
*[[A* 알고리즘]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms''. MIT Press.
[[분류:알고리즘]]
[[분류:그래프 이론]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*