BFS

BFS

(노드의 확장 순서대로 숫자가 증가함)

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

• 미로의 출구까지의 최단 거리를 구하는 문제에서 많이 사용된다.

BFS의 동작 과정

1. 모든 노드에 대한 정보를 큐에 삽입한 이후 방문한 노드를 방문 처리를 한다. (Flase -> True)
2. 시작 노드의 인접 노드들을 큐에 넣는다
3. 큐에서 가장 처음에 들어간 노드를 빼내어 방문 처리를 해준다.
4. 위의 과정을 더이상 실행 할 수 없을 때까지 반복한다.

구현

대표적인 구현의 방법은 크게 2가지로 나뉘어 진다.

1. Queue(FIFO)를 이용한 구현

2. 재귀를 이용한 구현

Queue를 이용한 구현

from collections import deque

def bfs (graph, node, visited):
    queue = deque([node])
    
    visited[node] = True #현재 노드 방문 여부 변경
    
    # 큐가 Null이 될 때까지
    while queue:
        v = queue.popleft() # 노드 pop
        print(v, end = ' ')
        # 방문하지 않은 인접 노드 queue에 삽입
        
        for i in graph[v]: #이때 graph는 배열 리스트
            if not (visited[i]):
                queue.append(i)
                visited[i] = True


visited = [False] * (N + 1)

재귀를 이용한 구현

from collections import deque

def bfs_recursive(graph, queue, visited):
    if not queue:
        return
    
    next_queue = deque()
    
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                next_queue.append(i)
    
    bfs_recursive(graph, next_queue, visited)