[알고리즘] BFS(너비 우선 탐색) 개념

BFS를 쉽게 말하자면?

---

예시 그래프

위 그래프의 시작 노드는 1 이고, 숫자가 낮은 노드부터 탐색한다고 가정하자. 이 가정 아래, 그래프를 가장 가까운 노드부터 탐색하면

1 -> 2 -> 3 -> 5 -> 4 -> 6 라는 결과를 얻을 수 있다. 이것이 BFS이다. BFS의 가장 주요한 모토는 "그래프를 가까운 노드부터 탐색하자." 라는 것을 잊지 말자!

 

BFS 알고리즘

---

가장 까운 노드부터 탐색하는 BFS

먼저, BFS를 구현하기 위해서는 FIFO 구조인 큐(Queue) 자료구조를 사용해야 한다. 인접한 노드를 반복적으로 큐에 넣게되면, 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 정확한 동작방식은 아래와 같다.

 

1) 탐색 시작 노드를 Queue에 Enqueue 하고 방문 처리한다.

2) Front에 있는 노드를 Dequeue 하고 해당 노드의 인접 노드 중 방문하지 않은 모든 노드들을 Queue에 Enqueue 한다.

    (이때 Queue에 Enqueue 되는 노드들은 방문처리 되야 한다.)

3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

BFS 알고리즘을 파이썬으로 구현하기

---

앞서 말했듯이, Queue 자료구조가 이용되고 이 Queue는 시작 정점으로 초기화 된다.(아래 코드의 queue = deque([start]) )

BFS를 파이썬으로 구현할 때 가장 중요한 맥락은 다음과 같다.

1. Queue의 Front 노드를 dequeue( queue.popleft( ) ) 한다.

2. dequeue된 노드에 인접하면서 방문하지 않은 노드를 queue에 enqueue 하고 방문처리 한다.

3. 1번과 2번의 과정을 더 이상 반복하지 못할 때까지 반복하면 자연스럽게 가까운 것부터 탐색하는 BFS 알고리즘이 완성된다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 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
# 인접 리스트로 그래프 표현
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

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

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