너비 우선 탐색 (BFS, Breadth-First Search)

너비 우선 탐색 (BFS, Breadth-First Search) 개요

너비 우선 탐색(BFS)은 그래프나 트리를 탐색하는 대표적인 알고리즘 중 하나로, 탐색의 너비(Breadth)를 우선으로 진행하는 방식이다. BFS는 시작 노드에서 출발해 인접한 노드들을 먼저 탐색한 후, 그 다음으로 인접한 노드들의 이웃들을 탐색하는 방식으로 진행된다. 즉, 같은 레벨에 있는 노드들을 먼저 방문하고, 한 레벨의 모든 노드를 방문한 후 다음 레벨로 넘어가는 방식이다.

BFS는 큐(Queue) 자료구조를 사용해 구현되며, 최단 경로를 찾는 문제나, 그래프의 각 노드를 너비 우선으로 방문할 때 매우 유용하다.

 

BFS의 동작 원리

1. 시작 노드에서 탐색을 시작한다.
2. 해당 노드를 방문 처리하고, 그 노드를 큐에 넣는다.
3. 큐에서 노드를 꺼내어 해당 노드와 연결된 모든 인접 노드를 방문한다. 아직 방문하지 않은 노드만 큐에 추가한다.
4. 큐가 빌 때까지 이 과정을 반복한다.
5. 큐에서 꺼낸 노드들은 각 레벨별로 너비 우선으로 탐색된다.

BFS 탐색 순서 예시

다음 그래프에서 BFS를 사용해 0번 노드부터 탐색한다고 가정해 본다:

    0 -- 1
    |    |
    4 -- 2 -- 3

BFS의 탐색 순서는 다음과 같다

• 0 → 1 → 4 → 2 → 3

 

BFS 구현 방법

BFS는 큐(Queue)를 사용하여 구현된다. 큐는 먼저 들어온 요소가 먼저 나가는 FIFO(First In, First Out) 구조를 가지고 있으며, 이를 통해 노드들이 탐색될 순서를 관리한다.

큐를 이용한 BFS의 구현 흐름:

1. 시작 노드를 큐에 넣는다.
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드들을 큐에 넣는다.
3. 더 이상 큐에 남은 노드가 없을 때까지 반복한다.

BFS 구현

다음은 Python에서 BFS를 구현한 코드이다. 그래프는 인접 리스트(Adjacency List)로 표현되며, BFS를 통해 모든 노드를 탐색한다.

from collections import deque

class Graph:
    def __init__(self):
        self.adj_list = {}  # 인접 리스트로 그래프 표현

    # 간선 추가 함수
    def add_edge(self, u, v):
        if u not in self.adj_list:
            self.adj_list[u] = []
        if v not in self.adj_list:
            self.adj_list[v] = []
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)  # 무방향 그래프일 경우

    # BFS 구현
    def bfs(self, start_node):
        visited = set()  # 방문한 노드를 저장하는 집합
        queue = deque()
        queue.append(start_node)  # 큐에 시작 노드를 추가
        visited.add(start_node)  # 시작 노드를 방문 처리

        while queue:
            node = queue.popleft()  # 큐에서 노드를 꺼냄
            print(node, end=" ")

            # 인접한 노드들을 큐에 추가 (방문하지 않은 노드만)
            for cur_node in self.adj_list[node]:
                if cur_node not in visited:
                    queue.append(cur_node)  # 큐에 추가
                    visited.add(cur_node)  # 방문 처리

# 그래프 생성
graph = Graph()

# 간선 추가 (무방향 그래프)
graph.add_edge(0, 1)
graph.add_edge(0, 4)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(2, 4)

# BFS 탐색 (0번 노드에서 시작)
graph.bfs(0)
# 0 1 4 2 3

위 코드에서 BFS는 시작 노드 0에서 출발하여, 해당 노드와 연결된 모든 이웃 노드를 방문한 후, 그 다음으로 인접한 노드들을 방문하는 방식으로 동작한다. 큐는 각 레벨별로 노드를 탐색하기 위한 순서를 관리한다.

 

BFS의 특징

1. 시간 복잡도:
   • 그래프의 노드 수를 V, 간선 수를 E라고 할 때, BFS의 시간 복잡도는 O(V + E)이다.
     • 모든 노드를 한 번씩 방문하고, 모든 간선을 한 번씩 탐색하기 때문이다.
2. 공간 복잡도:
   • BFS는 큐와 방문 집합을 사용하는데, 큐의 최대 크기는 노드 수에 비례하므로 O(V)의 공간 복잡도를 가진다.
3. 용도:
   • 최단 경로 탐색: BFS는 최단 경로 탐색에 매우 효과적이다. 특히 모든 간선의 가중치가 동일한 그래프에서, 특정 노드에서 다른 노드로 가는 최단 경로를 찾는 데 유리하다.
   • 연결성 탐색: 그래프가 연결되어 있는지 또는 연결된 성분(connected components)을 탐색할 때 유용하다.
   • 레벨 탐색: BFS는 그래프의 레벨 구조를 탐색할 때 사용된다. 즉, 시작 노드로부터 같은 거리에 있는 노드를 먼저 탐색하므로, 각 레벨별로 탐색이 가능하다.
4. 장점:
   • 최단 경로 보장: 가중치가 없는 그래프에서는, 시작 노드에서 목표 노드까지의 최단 경로를 보장한다.
   • 레벨 탐색: 노드 간의 거리 또는 깊이를 구하는 문제에서 유용하다.
   • 사이클 탐지: 그래프에서 사이클이 존재하는지 탐지할 수 있다.
5. 단점:
   • 메모리 사용량: BFS는 모든 노드를 큐에 저장해야 하므로, 메모리 사용량이 클 수 있다. 특히 노드가 많거나, 그래프가 넓게 퍼진 경우 큐의 크기가 매우 커질 수 있다.
   • 재귀적 구현 어려움: BFS는 큐를 이용한 반복적인 구조이기 때문에, 재귀적으로 구현하는 것이 복잡하다. 재귀를 사용하기에는 DFS가 더 적합하다.

 

BFS의 응용

1. 최단 경로 찾기: 가중치가 없는 그래프에서 특정 노드에서 다른 노드로 가는 최단 경로를 찾는 데 유용하다.
   • 예: 미로 탐색 문제, 네트워크에서의 최단 경로 문제 등.
2. 그래프의 연결성 탐색: 연결된 그래프의 모든 노드를 탐색하거나, 연결된 성분의 개수를 구할 때 사용된다.
   • 예: 소셜 네트워크에서 한 사람이 다른 사람과 연결되어 있는지 탐색하는 문제.
3. 레벨 탐색: 트리에서 각 레벨에 있는 노드들을 탐색할 때 사용된다.
   • 예: 트리의 특정 레벨의 노드 수를 구하는 문제.
4. 사이클 탐지: 무방향 그래프에서 사이클이 있는지 여부를 탐지할 수 있다.
   • 예: 도로망이 사이클을 포함하고 있는지 확인하는 문제.

 

BFS와 DFS의 비교

 

특징	BFS (너비 우선 탐색)	DFS (깊이 우선 탐색)
탐색 방식	레벨 단위로 너비를 우선 탐색	깊이 우선으로 탐색
구현 방식	큐(Queue)를 사용	스택(Stack) 또는 재귀(Recursion)를 사용
최단 경로 보장	가중치가 없는 그래프에서 최단 경로 보장	최단 경로를 보장하지 않음
메모리 사용	큐의 크기만큼 메모리 사용 (O(V))	재귀 호출 스택이나 명시적 스택 사용
적합한 문제	최단 경로, 레벨별 탐색	경로 탐색, 순회, 사이클 탐지 등

 

• BFS는 그래프를 너비 우선으로 탐색하는 알고리즘으로, 큐(Queue)를 사용하여 구현된다.
• BFS는 가중치가 없는 그래프에서 최단 경로를 보장하며, 연결된 성분 탐색, 레벨 탐색 등 다양한 문제에서 유용하다.
• 시간 복잡도는 O(V + E)로, 노드와 간선을 각각 한 번씩 탐색한다.
• BFS는 메모리를 많이 사용할 수 있지만, 최단 경로 탐색에서 매우 효과적이다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms