너비 우선 탐색(BFS)

• Breadth First Search

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

• 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용

BFS의 특징

• 재귀적으로 동작하는 DFS와 달리 BFS는 주로 큐(Queue)를 사용

• 사이클이 있는 경우, 무한 루프에 빠지지 않도록 방문 체크를 해주어야 함

• 물웅덩이에 돌멩이를 하나 던지면, 파동이 전체 방향으로 퍼져나가는 동심원의 형태로 탐색이 진행

BFS의 동작 순서

BFS의 구현

from collections import deque

q = deque() # 빈 큐 q 및 visited 배열 생성
q.append(st) # 시작 노드 'st'를 큐 q에 삽입
visited[st] = 1 # 노드 'st'를 방문한 것으로 표시(1 or True)

while q: # 큐 q가 비어 있찌 않은 동안 다음을 반복
	# 큐의 맨 앞에서 요소를 꺼내 'now'에 저장, 큐의 맨 앞의 요소를 제거
    now = q.popleft()
    print(now, end=" ") # 'now'의 값을 출력하고 뒤에 공백을 붙임
    # 노드 'now'의 인접 리스트 v에서 각 이웃 'next'에 대해
    for next in v[now]:
    if not visited[next]: # 만약 'next'가 아직 방문하지 않은 노드인 경우
    	visited[next] = 1 # 노드 'next'를 방문한 것으로 표시
        q.append(next) # 'next'를 큐 q에 넣음

import java.util.LinkedList;
import java.util.Queue;

public class BFS {
	public static void main(String[] args) {
    	int st = 1;
        Queue<Integer> q = new LinkedList<>();
        q.add(st);
        visited[st] = 1;
        while (!q.isEmpty()) {
        	int now = q.poll();
            System.out.print(now + " ");
            for (int next : v[now]) {
            	if (visited[next] == 0) {
                	visited[next] = 1;
                    q.add(next);
				}
			}
		}
	}
}

queue<int> q;
q.push(st);
visited[st] = 1;
while (!q.empty()) {
	int now = q.front();
    q.pop();
    cout << now << " ";
    for (int &next: v[now]) {
    	if (!visited[next]) {
        	visited[next] = 1;
            q.push(next);
		}
	}
}

BFS의 시간 복잡도

• 인접 리스트로 표현된 그래프: $O(V + E)$

• 인정 행렬로 표현된 그래프: $O(V^2)$

• $V$ → 정점(노드)의 수, $E$ → 간선의 수

두 방식 모두 조건 내에 모든 노드를 검색한다는 점에서 시간 복잡도는 동일하지만, 일반적으로 DFS를 재귀 함수로 구현한다는 점에서 DFS보다 BFS가 조금 더 빠르게 동작

주어진 그래프의 구조와 시작 노드에 따라서 실제 시간 복잡도가 다를 수 있으며, 어떤 알고리즘이 더 효율적인지는 그래프의 형태와 알고리즘의 목적에 따라 달라짐

일반적으로 어떤 알고리즘을 선택할지는 문제의 특성과 요구 사항에 따라 결정

DFS와 BFS의 공통점 및 차이점

공통점

• 그래프에서 시작 노드로부터 목적지 노드까지 도달하거나 특정 정보를 찾는 것이 목표

• 방문 기록을 체크함으로써, 이미 방문한 노드를 다시 방문하지 않게 하여 무한 루프 방지

차이점

• DFS는 주로 재귀로 구현하지만, BFS는 큐(queue) 자료구조를 활용하여 구현

• 동작 순서 상 DFS는 트리를 탐색할 때 자주 사용, BFS는 최단 경로 탐색에 자주 사용