[알고리즘] 2-2. 너비 우선 탐색(BFS)

BFS

 

BFS(Breadth First Search)는 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘이다.

BFS에서는 큐 자료구조를 이용하여 구현한다. 인접한 노드들 중 방문하지 않은 노드를 큐에 추가하면 가까운 노드부터 탐색하는 것이다.

 

동작 방식은 다음과 같다:

 

1. 탐색 시작 노드를 큐에 넣고, 방문처리한다.

2. 큐에서 노드를 꺼내 큐의 인접 노드들 중 방문하지 않은 모든 노드들을 큐에 삽입하고, 순서대로 방문처리한다.

3. 2번의 과정을 계속해서 반복한다.

 

 

노드 '1'부터 시작해서 '1'을 큐에 넣고 방문처리한다.

노드 '1'을 큐에서 꺼내고, '1'의 인접 노드들 중 방문하지 않은 노드들을 모두 큐에 넣고 방문처리한다.

노드 '2'를 큐에서 꺼내고, 2에 인접한 노드들 중 방문하지 않은 노드인 '5'를 큐에 넣고 방문처리한다.

노드 '3'을 큐에서 꺼내고, '3'에 인접한 노드들 중 방문하지 않은 '7'을 큐에 넣고 방문처리한다.

노드 '4'를 큐에서 꺼내고, '4'의 인접 노드들 중 방문하지 않은 '8'을 큐에 넣고 방문처리한다.

노드 '5'를 큐에서 꺼내고, 인접 노드들 중 방문하지 않은 '6'을 큐에 넣고 방문처리한다.

큐에 남은 노드들의 방문하지 않은 인접노드가 없으므로 큐를 전부 꺼낸다.

 

방문 순서(큐에 들어간 순서)는 다음과 같다:

1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 6

 

코드(Python)

 

from collections import deque

def bfs(graph, start, visited):
    q = deque([start])#시작 노드를 큐에 넣는다
    visited[start] = True#방문처리한다
    while q:#큐에 노드가 있는 동안:
        v = q.popleft()#제일 먼저 들어온 노드를 빼서
        print(v, end = ' ')
        for i in graph[v]:#인접 노드들 중 방문하지 않은 노드들을 큐에 넣고 방문처리한다
            if not visited[i]:
                q.append(i)
                visited[i] = True

#그래프의 정보(인접 노드들)
graph = [[],
         [2, 3, 4],
         [1, 5],
         [1, 7],
         [1, 8],
         [2, 6],
         [5],
         [3, 8],
         [4, 7]]
#방문 정보
visited = [False] * 9
#1부터 너비우선탐색
bfs(graph, 1, visited)

결과

1 2 3 4 5 7 8 6