[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다.

 

[ Contents ]

 

 

1. BFS(Breath First Search)

너비 우선 탐색(BFS): 가까운 주변 노드부터 탐색하며 점점 넓혀가는 방식

 

 그래프에서는 원 안의 데이터를 '노드(Node)', 노드끼리 연결된 선을 '간선(Edge)'이라고 합니다. 1을 시작으로 할 때, BFS는 주변 노드부터 탐색합니다. 

 [ 1 -> 2 -> 3 -> 4 -> 5 -> 6 ]

(같은 거리 내 인접한 노드는 숫자가 작은 노드부터 탐색한다고 가정)

 

 

 

2. 큐(Queue)를 이용한 탐색 방식

2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

[Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

큐(Queue): 선입선출(First-in-First-out), 가장 먼저 들어간 자료부터 꺼내는 자료구조

 

 BFS 탐색은 큐를 이용합니다. 인접한 노드부터 먼저 큐에 삽입하고, 꺼내어서 탐색합니다.

 

 

 위에서 봤던 예제를 다시 살펴보겠습니다. 시작 노드는 1번이며, 큐에 삽입하고 방문(탐색) 합니다. 방문한 노드는 주황색 테두리로 표시하겠습니다.

 

 

 방문한 1번 노드를 큐에서 삭제(pop)하고, 인접한 2번과 3번 노드를 큐에 삽입(push)합니다.

 

 

 방문한 2번 노드를 큐에서 삭제(pop)하고, 인접한 4번, 5번, 6번 노드를 큐에 삽입(push)합니다.

 이후 큐에서 순서대로 꺼내며 주변 노드를 탐색하며, 3/4/5/6번 노드는 새로운 인접노드가 없으므로 탐색을 종료합니다.

 

 

 

3. BFS 구현

from collections import deque

# BFS 탐색 (탐색할 그래프, 노드 수, 시작 지점)
def bfs(graph, n, start):
    queue = deque([start]) #인접 노드를 저장할 Queue

    visited = [False]*(n+1) #방문 여부를 확인할 리스트
    visited[start] = True #시작 노드 방문

    #모든 노드를 탐색할 때까지 반복
    while queue:
        #방문 노드
        node = queue.popleft()
        print(node, end=' ')

        #방문한 노드의 주변 노드를 큐에 삽입
        for i in graph[node]:
            #방문하지 않는 주변 노드일 경우
            if not visited[i]:
                queue.append(i) #큐에 추가
                visited[i] = True #방문

 BFS는 큐를 이용해서 주변 노드부터 방문합니다.

 visited 리스트로 방문 여부를 표시하고, 방문하지 않은 노드를 탐색합니다.

 

 

graph = [
	[],
    [2, 3],#1번 노드와 연결된 노드
    [1, 4, 5, 6], #2번 노드와 연결된 노드
    [1], #3번 노드
    [2, 5], #4번 노드
    [2, 4], #5번 노드
    [2] #6번 노드
]

bfs(graph, 6, 1) #시작 노드 1번

 예제에서 다뤘던 그래프를 BFS 함수에 넣으면 방문 순서를 알 수 있습니다.

 

 결과는 앞서 살펴본 것과 같습니다.