[알고리즘] 너비 우선 탐색(BFS, Breadth First Search)

너비 우선 탐색(BFS, Breadth First Search)

BFS는 가까운 노드부터 우선적으로 탐색하는 방식이며 레벨(level) 순서대로 접근한다. BFS는 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용된다. 큐를 활용해서 구현한다.

• 장점
  • 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리
  • 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장
  • 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있음
  • 단순 검색 속도가 DFS보다 빠름
• 단점
  • 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공간 필요
  •  노드의 수가 늘어나면 탐색해야 하는 노드 또한 많아지기 때문에 비현실적

 

출처 : https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif와 https://velog.io/@sukong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-%EB%84%88%EB%B9%84%EC%9A%B0%EC%84%A0%ED%83%90%EC%83%89BFS-lp8zywtn

 

 

 

 

파이썬 코드

그래프 데이터 예시는 이전 게시물인 DFS의 그래프 데이터 예시를 참고하면 된다.

 

기본 1

visited 변수에 방문한 노드들을 넣는 버전이다.

from collections import deque

def bfs(graph, start):
  visited, queue = list(), deque([start])
  while queue:
      node = queue.popleft()
      if node not in visited:
          visited.append(node)
          queue += graph[node]
  return visited

 

 

 

기본 2

visited를 방문 처리 용으로 사용하고 result에 방문한 노드들을 넣는 버전이다.

from collections import deque, defaultdict

def bfs(graph, start):
  result = list()
  visited, queue = defaultdict(bool), deque([start])
  while queue:
      node = queue.popleft()
      if not visited[node]:
          visited[node] = True
          result.append(node)
          queue += graph[node]
  return result

 

 

 

기본 3

from collections import deque

def bfs(graph, start):
    visited, queue = [start], deque([start])
    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if i not in visited:
                visited.append(i)
                queue.append(i)
    return visited

 

 

 

 

 

 

 

 

https://blog.naver.com/ndb796/221230944971

15. 너비 우선 탐색(BFS)

https://velog.io/@vagabondms/DFS-vs-BFS

DFS vs BFS