너비우선탐색(Breadth-First Search)
BFS는 그래프 완전 탐색 기법 중 하나로,
그래프의 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶은 경우 너비우선탐색 알고리즘을 선택한다.
그래프 탐색이란 ?
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 기법이다.
너비우선탐색(BFS)의 특징
- 방문한 노드를 차례로 저장 후 꺼내야하므로, 선입선출 자료구조인 큐(Queue)를 사용한다.
- 그래프 탐색의 경우 노드의 방문 여부 검사가 필요하다.
방문 여부를 검사하지 않을 경우 무한루프 유의 - 시간복잡도(
V: 노드 수 /E: 에지 수 )
인접 리스트를 이용하여 구현하는 경우 :O(V+E)
인접 행렬을 이용하여 구현하는 경우 :O(N^2)
너비우선탐색(BFS)의 탐색과정
- 시작 노드를 대기열(Queue)에 넣고, 방문한 것으로 표시한다.
- 대기열에서 노드를 제거한다.
- 큐에서 빼낸 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 넣는다.
- 대기열에서 뺀 노드가 목표 노드이거나 대기열에 노드가 존재하지 않을 때까지 2-3번을 반복한다.
너비우선탐색(BFS)의 구현방법
- 반복문(큐 자료구조 사용)
@minzdev