BFS

정의 및  장단점

BFS는 Breadth First Serach로 너비우선탐색이다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리있는 노드를 찍고 돌아오고 멀리갔다가 돌아로는 탐색이다. BFS는 그 반대이다. 

 

 

 

출처: https://iq.opengenus.org/dfs-vs-bfs/

 

구현방법

BFS는 큐 자료구조를 이용한다. 큐를 이용하면 자연스럽게 먼저들어온것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다.

파이썬에서는 deque라이브러리를 이용한 큐 자료구조를 사용하는 것이 보편적이다. 시간복잡도는 O(N)의 시간이 소요된다. 

일반적인 경우 실제 수행시간이 DFS보다 좋은편이다. 문제에 따라 DFS의 경우 무한굴레에 빠져 시간이 엄청 길어 질수 있다. 하지만 BFS는 가까운노드에서부터 점차적으로 넓혀가기 때문에 보다 안정적이다. 모든 경우의 수를 전부 한단계(깊이)씩 탐색한다.

문제 예시

 

from collections import deque

# BFS 함수 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end=' ')
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

 

 

https://yunzae.tistory.com/56

큐(Queue,deque,list)