개념
너비 우선 탐색 (Breadth-First Search)
BFS는 그래프의 너비 부분을 우선적으로 탐색하는 알고리즘입니다. 시작 노드에서부터 이웃한 노드를 탐색한 후, 해당 이웃들의 이웃 노드를 탐색하며 너비를 우선적으로 탐색합니다. 이 과정을 반복하여 모든 노드를 방문합니다. 일반적으로 큐(Queue) 자료구조를 사용하여 탐색할 노드를 저장하고 탐색 순서를 조절합니다. BFS는 최단 경로 탐색에 유용하며, 그래프의 모든 노드를 탐색하는 경우에도 사용할 수 있습니다.
작동 방식
- 시작 노드를 큐에 삽입합니다.
- 큐가 비어있을 때까지 다음을 반복합니다.
- 큐에서 하나의 노드를 꺼냅니다.
- 해당 노드를 방문 처리합니다.
- 해당 노드와 인접한 모든 미방문 노드들을 큐에 삽입합니다.
- 탐색이 종료되면 방문한 노드의 순서에 따라 결과를 반환하거나 원하는 동작을 수행합니다.
이 구현 방법을 좀 더 구체적으로 설명하면 다음과 같습니다.
- 큐는 FIFO(First-In, First-Out) 원칙에 따라 노드들을 저장하는 자료구조입니다. 방문할 노드를 큐의 뒤쪽에 삽입하고, 노드를 꺼낼 때는 큐의 앞쪽에서 꺼냅니다.
- 시작 노드를 큐에 삽입합니다.
- 큐가 비어있지 않은 동안 다음을 반복합니다
- 큐에서 노드를 하나 꺼냅니다.
- 해당 노드를 방문 처리합니다.
- 해당 노드와 인접한 미방문 노드들을 모두 큐에 삽입합니다. 이때 인접한 노드들을 방문했다는 표시를 해야합니다.
- 반복이 종료되면 모든 노드를 방문했으며, 방문한 순서대로 결과를 반환하거나 원하는 동작을 수행합니다.
특징
-
큐(Queue) 자료구조: BFS는 큐를 활용하여 구현됩니다. 시작 노드를 큐에 넣고, 인접한 노드를 큐에 순서대로 추가하면서 탐색을 진행합니다.
-
너비 우선 탐색 특성: BFS는 한 단계씩 너비를 우선하여 탐색합니다. 시작 노드에서 인접한 노드들을 모두 탐색한 후, 그 다음 단계의 인접한 노드들을 탐색합니다.
-
최단 경로 탐색: BFS는 시작 노드에서 다른 모든 노드까지의 최단 경로를 탐색할 수 있습니다. 먼저 도착 노드에 도달하면 탐색을 종료하므로, 최단 경로를 보장합니다.
-
그래프 탐색에서 사용되는 자주 쓰이는 알고리즘: BFS는 그래프 탐색에 많이 사용되며, 최단 경로, 연결 요소, 네트워크 통신 등 다양한 그래프 알고리즘에 활용됩니다.
-
레벨 순서 탐색: BFS는 레벨 순서대로 탐색하므로, 탐색 순서가 노드의 깊이에 따라 결정됩니다. 루트에서 시작해 한 레벨씩 아래로 내려가며 탐색합니다.
-
추가적인 메모리 사용: BFS는 큐를 사용하므로 추가적인 메모리가 필요합니다. 큐에 탐색할 노드들을 저장하고, 방문 여부를 확인하기 위한 배열 등의 데이터 구조를 사용합니다.
예시
-
최단 경로 찾기: 너비 우선 탐색은 그래프에서 시작 노드로부터 목표 노드까지의 최단 경로를 찾는데 사용될 수 있습니다. 모든 가중치가 동일한 그래프에서는 너비 우선 탐색을 통해 최단 경로를 찾을 수 있습니다.
-
연결 그래프 확인: 너비 우선 탐색은 그래프가 연결되어 있는지 확인하는 데에 사용될 수 있습니다. 시작 노드에서부터 도달 가능한 모든 노드들을 탐색하고, 모든 노드를 방문한 경우 그래프는 연결되어 있는 것으로 판단할 수 있습니다.
-
이진트리 순회: 너비 우선 탐색은 이진트리를 레벨 순서대로 탐색하는데에도 사용될 수 있습니다. 특히, 레벨 순서대로 노드를 방문하므로 너비 우선 탐색은 이진트리의 너비 우선 탐색 순회(BFS traversal)로 사용될 수 있습니다.
-
그래프의 최소 스패닝 트리(Minimum Spanning Tree): 너비 우선 탐색은 그래프의 최소 스패닝 트리를 찾는 Kruskal 알고리즘과 함께 사용될 수 있습니다. Kruskal 알고리즘은 간선들을 가중치 순서대로 정렬한 후, 최소 가중치를 가지는 간선들을 하나씩 선택하여 최소 스패닝 트리를 만드는데, 이때 너비 우선 탐색을 사용하여 연결된 노드를 확인하게 됩니다.
-
네트워크 통신: 너비 우선 탐색은 컴퓨터 네트워크에서 최단 경로를 찾거나 네트워크 통신을 할 때 사용될 수 있습니다. 예를 들어, 라우팅 알고리즘에서는 너비 우선 탐색을 사용하여 최적의 경로를 찾거나 데이터 패킷을 전송하는데 활용됩니다.
다음은 간단한 예시입니다.
A
/ | \
B C D
/ \ / \
E F G H
초기 상태:
시작 정점: A
방문한 정점: []
시작 정점 A 방문:
방문한 정점: [A]
A의 이웃 정점 B, C, D를 큐에 추가:
큐: [B, C, D]
방문한 정점: [A]
큐에서 정점 B 선택:
방문한 정점: [A, B]
B의 이웃 정점 E, F를 큐에 추가:
큐: [C, D, E, F]
방문한 정점: [A, B]
큐에서 정점 C 선택:
방문한 정점: [A, B, C]
C의 이웃 정점 G를 큐에 추가:
큐: [D, E, F, G]
방문한 정점: [A, B, C]
큐에서 정점 D 선택:
방문한 정점: [A, B, C, D]
D의 이웃 정점 H를 큐에 추가:
큐: [E, F, G, H]
방문한 정점: [A, B, C, D]
큐에서 정점 E 선택:
방문한 정점: [A, B, C, D, E]
큐에서 정점 F 선택:
방문한 정점: [A, B, C, D, E, F]
큐에서 정점 G 선택:
방문한 정점: [A, B, C, D, E, F, G]
큐에서 정점 H 선택:
방문한 정점: [A, B, C, D, E, F, G, H]
큐가 비어있으므로 탐색을 종료합니다.