[알고리즘] BFS(너비 우선 탐색) 개념 및 구현(파이썬)

목차

• BFS의 개념
• BFS의 장단점
• BFS의 시간 복잡도
• BFS의 구현

 

 

 

BFS(너비 우선 탐색)이란?

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

 

 

BFS의 동작 과정

1. 탐색 시작 정점을 큐에 삽입하고 방문 처리를 합니다. 
2. 큐에서 정점을 꺼낸 뒤에 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리를 합니다. 
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. 

 

BFS의 장단점

장점

• 시작 정점에서 목표 정점까지의 최단 길이 경로를 보장한다. 

 

단점

• 경로가 매우 길 경우, 탐색 가지가 급격히 증가함에 따라 많은 기억 공간이 필요하다. 
• 답이 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후 실패로 끝난다. 
• 무한 그래프(infinite graph)의 경우에는 답을 찾지 못하고, BFS가 끝나지도 않는다. 

 

 

 

BFS의 시간 복잡도

• N: 노드의 수, E: 간선의 수
• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)

 

 

 

BFS의 구현

# graph[i]는 i번째 노드와 인접한 노드 번호를 포함
graph = [
    [1, 2, 4],
    [0, 2],
    [0, 1, 3, 4],
    [2, 4],
    [0, 2, 3]
]

# 방문 처리를 위한 리스트
visited = [False] * 5

# queue 자료구조 사용을 위해
from collections import deque

# BFS
def bfs(start):
    # 시작 정점 큐 삽입 및 방문 처리
    queue = deque([start])
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        v = queue.popleft()
        print(v, end = ' ') # 0 1 2 4 3
        for x in graph[v]:
            if not visited[x]:
                queue.append(x)
                visited[x] = True
                
# 0을 시작 정점으로 BFS
bfs(0)

 

 

 

 

참고

• github.com/ndb796/python-for-coding-test
• https://ko.wikipedia.org/wiki/너비_우선_탐색
• C언어로 쉽게 풀어쓴 자료구조