너비 우선 탐색(BFS)알고리즘
August 23, 2020
탐색 알고리즘을 공부하다 보면 깊이 우선 탐색(이하 DFS) 알고리즘과 너비 우선 탐색(이하 BFS) 알고리즘을 주로 다룬다.
오늘은 너비 우선 탐색(BFS) 알고리즘에 대해 공부한 내용을 작성하고자 한다.
개념
위키백과에 따르면 BFS 알고리즘의 개념은 다음과 같다.
맹복적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문 하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
이 정의를 쉽게 풀어쓰면 다음과 같다.
시작 정점을 시작으로 가장 인접한 정점을 순서대로 방문하는 탐색하는 알고리즘
BFS 알고리즘은 가까운 정점의 값을 모두 저장하여 순서대로 방문해야 하기 때문에 스택(Stack) 구조를 사용하여 구현하는 DFS와는 다르게 큐(Qyueue) 구조를 사용하여 구현한다.
특징
- 재귀적으로 동작하지 않는다.
- 어떤 노드를 방문했는지 반드시 검사해야 한다.
- 선입선출(FIFO) 형태로 탐색한다.
시간 복잡도
BFS의 시간 복잡도는 다음과 같다. (정점의 수: N, 간선의 갯수: E)
- 리스트로 구현된 그래프 : O(N+E)
- 행렬로 구현된 그래프 : O(N^2)구현
python을 사용하여 BFS 알고리즘을 구현하면 다음과 같다.
def bfs(graph, start_node):
visit = list() # 방문하는 노드 저장
queue = list() # 큐
queue.append(start_node)
# 큐가 비어 있을 때까지 반복적으로 진행
while queue :
node = queue.pop(0)
if node not in visit:
visit.append(node)
queue.extend(graph[node])
return visit
