[문법] BFS(너비 우선 탐색) 개념 및 구현(Python)

BFS이란?

• BFS(Breadth First Search) 또는 너비 우선 탐색이라고 함
• 시작 정점으로부터 가까운 정점을 먼저 방문하는 그래프 탐색 방법
• 큐(queue)를 이용해 방문한 정점들을 차례로 저장하고 꺼냄

 

DFS와 BFS의 차이점

• DFS 는 탐색하는 원소를 최대한 깊게 따라가야 한다.
      이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
      가장 마지막에 넣은 노드를 꺼내서 탐색하면 된다. → 스택
• BFS 는 현재 인접한 노드 먼저 방문해야 한다.
      이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고,
      가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. → 큐

 

구현 (Python)

1. 루트 노드를 큐에 넣는다.

2. 현재 큐의 노드를 빼서 visited 에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복한다.

5. 큐가 비면 탐색을 종료한다.

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def bfs_queue(start): # 시작 위치를 받는다.
    visited = [start] # 해당 위치의 노드를 visited에 저장해준다. 
    q = deque([start]) # deque화 한다.

    while q: # q에 값이 없을때까지
        node = q.popleft() # 가장 앞에 값을 빼서 노드에 저장한다.
        for adj in graph[node]: # 노드의 위치에 인접한 노드를 확인한다.
            if adj not in visited: # 만약 인접한 노드 중 방문하지 않은 노드가 있다면
                q.append(adj) # q에 추가한다.
                visited.append(adj) # 노드를 visited에 넣어준다.

    return visited # visited를 반환한다.


assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]