너비 우선 탐색(BFS, Breadth-First Search)은 그래프 탐색 알고리즘으로, 시작 정점에서 가까운 정점부터 순차적으로 탐색을 진행합니다. 이 알고리즘은 큐 자료구조를 사용하여 구현되며, 무가중치 그래프에서 최단 경로를 찾는 데 유용합니다. 본 기사에서는 BFS의 개념, 동작 원리, C 언어를 이용한 구현 방법과 예제를 다룹니다. 이를 통해 그래프 탐색 문제를 효과적으로 해결할 수 있는 기초 지식을 제공하겠습니다.
BFS란 무엇인가
BFS(Breadth-First Search)는 그래프 탐색 알고리즘으로, 시작 정점에서 가까운 정점부터 차례로 탐색하는 방식입니다.
BFS의 특징
- 레벨 기반 탐색: 시작 정점에서 같은 거리에 있는 정점들을 먼저 탐색합니다.
- 큐 자료구조 사용: 탐색 과정에서 방문할 정점들을 순서대로 저장하고 처리합니다.
- 방문 기록 필요: 정점의 중복 방문을 방지하기 위해 방문 여부를 기록합니다.
BFS의 활용 사례
- 무가중치 그래프의 최단 경로 찾기: 각 간선의 가중치가 동일한 그래프에서 최단 경로를 탐색할 때 효과적입니다.
- 그래프의 연결성 확인: 연결된 컴포넌트나 서브그래프를 탐색하는 데 유용합니다.
- 네트워크 흐름 분석: 네트워크나 소셜 그래프에서 데이터의 흐름을 추적할 때 사용됩니다.
BFS와 DFS의 비교
- BFS는 큐를 사용해 레벨 단위로 탐색하는 반면, DFS는 스택을 사용하여 깊이 우선으로 탐색합니다.
- BFS는 최단 경로를 보장하지만, DFS는 최단 경로를 보장하지 않습니다.
- 탐색 우선순위와 사용 사례에서 차이가 있습니다.
BFS는 그래프 탐색의 기초적인 알고리즘으로, 문제를 구조화하고 효율적으로 해결하는 데 필수적인 도구입니다.
BFS의 동작 원리
BFS는 큐 자료구조를 활용하여 그래프를 탐색합니다. 시작 정점에서 시작하여 점차 주변 정점으로 탐색을 확장하는 방식으로 작동합니다.
BFS 알고리즘의 단계
- 초기화
- 시작 정점을 큐에 추가하고 방문 여부를 기록합니다.
- 방문 여부를 확인하기 위한 배열을 생성합니다.
- 탐색 반복
- 큐에서 정점을 하나 꺼내 해당 정점과 연결된 모든 정점을 확인합니다.
- 방문하지 않은 정점은 큐에 추가하고 방문 여부를 기록합니다.
- 탐색 종료
- 큐가 비어 있으면 탐색을 종료합니다.
시각적 예시
다음과 같은 그래프를 가정합니다:
Graph:
1 - 2 - 3
| |
4 - 5
- 초기화
- 시작 정점: 1
- 큐 상태:
[1]
- 방문 배열:
[1: 방문, 2: 미방문, 3: 미방문, 4: 미방문, 5: 미방문]
- 첫 번째 반복
- 큐에서
1
제거,1
과 연결된 정점2
와4
를 큐에 추가. - 큐 상태:
[2, 4]
- 방문 배열:
[1: 방문, 2: 방문, 3: 미방문, 4: 방문, 5: 미방문]
- 두 번째 반복
- 큐에서
2
제거,2
와 연결된 정점3
과5
를 큐에 추가. - 큐 상태:
[4, 3, 5]
- 방문 배열:
[1: 방문, 2: 방문, 3: 방문, 4: 방문, 5: 방문]
- 반복 종료
- 큐에서 정점들을 차례로 제거하며 탐색 완료.
결과
탐색 순서: 1 → 2 → 4 → 3 → 5
BFS는 이처럼 큐를 사용해 각 레벨의 모든 정점을 방문하며 탐색을 수행합니다. 이를 통해 그래프 구조를 효율적으로 탐색하고 필요한 정보를 수집할 수 있습니다.
그래프의 표현 방법
그래프 탐색을 구현하기 위해서는 그래프를 컴퓨터 메모리 내에서 표현하는 방법이 중요합니다. BFS에서 사용되는 대표적인 그래프 표현 방식은 인접 리스트와 인접 행렬입니다.
인접 리스트
인접 리스트는 각 정점이 연결된 다른 정점의 목록을 저장하는 방식입니다.
- 구조: 배열이나 해시 테이블을 사용하여 각 정점에 연결된 정점들의 리스트를 저장합니다.
- 장점: 메모리 효율적이며, 희소 그래프(Sparse Graph)에 적합합니다.
- 단점: 연결 여부를 확인할 때 시간이 더 걸립니다.
예시:
그래프:
1 - 2 - 3
| |
4 - 5
인접 리스트 표현:
1: [2, 4]
2: [1, 3, 5]
3: [2]
4: [1, 5]
5: [2, 4]
인접 행렬
인접 행렬은 정점 간의 연결 관계를 2차원 배열로 나타냅니다.
- 구조: 행과 열의 각 위치에 정점 간 연결 여부를 1(연결) 또는 0(비연결)로 저장합니다.
- 장점: 연결 여부 확인이 O(1)로 매우 빠릅니다.
- 단점: 메모리 사용량이 많으며, 밀집 그래프(Dense Graph)에 적합합니다.
예시:
그래프:
1 - 2 - 3
| |
4 - 5
인접 행렬 표현:
1 2 3 4 5
1 [0, 1, 0, 1, 0]
2 [1, 0, 1, 0, 1]
3 [0, 1, 0, 0, 0]
4 [1, 0, 0, 0, 1]
5 [0, 1, 0, 1, 0]
표현 방식의 선택
- 인접 리스트: 정점 수는 많고 간선 수는 적은 경우(희소 그래프).
- 인접 행렬: 정점과 간선의 수가 비슷하거나 간선이 많은 경우(밀집 그래프).
BFS 구현 시 그래프의 크기와 특성에 따라 적합한 표현 방식을 선택하면 메모리와 시간 효율성을 극대화할 수 있습니다.
BFS 알고리즘의 구현
C 언어로 BFS 알고리즘을 구현하는 방법을 단계별로 설명합니다. 이번 구현에서는 그래프를 인접 리스트로 표현하며, 큐 자료구조를 활용합니다.
필요한 데이터 구조 정의
- 그래프 구조체
그래프는 정점 수와 인접 리스트로 표현됩니다.
#define MAX_VERTICES 100
typedef struct Graph {
int numVertices;
int adjList[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
} Graph;
- 큐 구현
BFS는 큐를 사용해 탐색 순서를 유지합니다.
typedef struct Queue {
int items[MAX_VERTICES];
int front;
int rear;
} Queue;
void enqueue(Queue *q, int value) {
q->items[++(q->rear)] = value;
}
int dequeue(Queue *q) {
return q->items[(q->front)++];
}
int isEmpty(Queue *q) {
return q->front > q->rear;
}
BFS 알고리즘 구현
- BFS 함수 정의
BFS 탐색을 위한 함수는 큐를 초기화하고 정점 방문 상태를 업데이트합니다.
void bfs(Graph *graph, int startVertex) {
Queue q;
q.front = 0;
q.rear = -1;
enqueue(&q, startVertex);
graph->visited[startVertex] = 1;
while (!isEmpty(&q)) {
int currentVertex = dequeue(&q);
printf("Visited %d\n", currentVertex);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjList[currentVertex][i] == 1 && !graph->visited[i]) {
enqueue(&q, i);
graph->visited[i] = 1;
}
}
}
}
- 그래프 초기화 및 데이터 추가
void addEdge(Graph *graph, int src, int dest) {
graph->adjList[src][dest] = 1;
graph->adjList[dest][src] = 1; // 무방향 그래프
}
void initializeGraph(Graph *graph, int vertices) {
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjList[i][j] = 0;
}
graph->visited[i] = 0;
}
}
메인 함수
int main() {
Graph graph;
initializeGraph(&graph, 5);
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 4);
addEdge(&graph, 1, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 1, 4);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 4);
printf("BFS starting from vertex 0:\n");
bfs(&graph, 0);
return 0;
}
결과
입력된 그래프를 기준으로 BFS 탐색 결과를 출력합니다.
BFS starting from vertex 0:
Visited 0
Visited 1
Visited 4
Visited 2
Visited 3
위 코드는 BFS 알고리즘의 기본 구현 예제이며, 그래프의 구조와 요구 사항에 따라 확장할 수 있습니다.
BFS 예제 코드 분석
C 언어로 구현한 BFS 알고리즘을 코드별로 분석하여 각 부분이 어떻게 작동하는지 설명합니다. 예제 코드는 이전 섹션의 내용을 기반으로 합니다.
1. 그래프 초기화
그래프의 정점 수를 정의하고 모든 간선 정보를 초기화합니다.
void initializeGraph(Graph *graph, int vertices) {
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjList[i][j] = 0;
}
graph->visited[i] = 0;
}
}
설명:
graph->numVertices
에 그래프의 정점 수를 저장합니다.- 모든 간선을 0으로 초기화하여 연결되지 않았음을 나타냅니다.
- 방문 배열
visited
는 모두 0으로 설정해 초기 상태에서 아무 정점도 방문하지 않았음을 나타냅니다.
2. 간선 추가
정점 간의 연결을 나타내는 간선 정보를 추가합니다.
void addEdge(Graph *graph, int src, int dest) {
graph->adjList[src][dest] = 1;
graph->adjList[dest][src] = 1; // 무방향 그래프
}
설명:
graph->adjList[src][dest] = 1
은src
에서dest
로의 연결을 추가합니다.- 무방향 그래프에서는
graph->adjList[dest][src]
도 1로 설정합니다.
예:addEdge(&graph, 0, 1)
호출 시 0과 1 정점 간에 간선이 추가됩니다.
3. BFS 알고리즘
BFS의 주요 로직은 큐와 방문 배열을 활용하여 구현됩니다.
void bfs(Graph *graph, int startVertex) {
Queue q;
q.front = 0;
q.rear = -1;
enqueue(&q, startVertex);
graph->visited[startVertex] = 1;
while (!isEmpty(&q)) {
int currentVertex = dequeue(&q);
printf("Visited %d\n", currentVertex);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjList[currentVertex][i] == 1 && !graph->visited[i]) {
enqueue(&q, i);
graph->visited[i] = 1;
}
}
}
}
설명:
- 큐를 초기화하고, 시작 정점을 큐에 삽입한 뒤 방문 배열을 업데이트합니다.
- 큐가 비어 있지 않는 동안 반복하여 다음 작업을 수행합니다:
- 큐에서 정점을 꺼내 방문합니다.
- 꺼낸 정점과 연결된 모든 미방문 정점을 큐에 삽입하고 방문 배열을 갱신합니다.
- 각 정점이 한 번만 방문되므로 탐색 결과는 중복되지 않습니다.
4. 메인 함수
int main() {
Graph graph;
initializeGraph(&graph, 5);
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 4);
addEdge(&graph, 1, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 1, 4);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 4);
printf("BFS starting from vertex 0:\n");
bfs(&graph, 0);
return 0;
}
설명:
- 그래프를 초기화하고 간선 정보를 추가합니다.
bfs()
를 호출하여 시작 정점 0에서 BFS를 수행합니다.
5. BFS 동작 순서 분석
그래프:
0 - 1 - 2
| | |
4 - 3
탐색 과정:
- 시작 정점 0: 큐에
[0]
삽입 → 방문:0
. - 정점 1, 4 큐에 삽입: 큐
[1, 4]
→ 방문:1, 4
. - 정점 2, 3 큐에 삽입: 큐
[4, 2, 3]
→ 방문:2, 3
.
결과
프로그램 출력:
BFS starting from vertex 0:
Visited 0
Visited 1
Visited 4
Visited 2
Visited 3
위 코드와 분석은 BFS 알고리즘을 C 언어로 구현하고 이해하는 데 필요한 모든 요소를 포함합니다.
BFS 응용: 최단 경로 찾기
BFS는 무가중치 그래프에서 최단 경로를 찾는 데 매우 유용합니다. BFS는 레벨 단위로 탐색하므로, 시작 정점에서 목표 정점까지의 첫 방문이 항상 최단 경로를 보장합니다.
최단 경로를 찾는 BFS 알고리즘
최단 경로를 찾으려면 BFS에 다음을 추가로 구현해야 합니다:
- 거리 배열: 시작 정점에서 각 정점까지의 거리를 저장합니다.
- 경로 추적: 이전 정점을 기록하여 경로를 복원할 수 있습니다.
코드 구현
- 거리와 이전 정점 배열 추가
void bfsShortestPath(Graph *graph, int startVertex, int targetVertex) {
Queue q;
q.front = 0;
q.rear = -1;
int distance[MAX_VERTICES];
int previous[MAX_VERTICES];
for (int i = 0; i < graph->numVertices; i++) {
distance[i] = -1; // 거리 초기화
previous[i] = -1; // 경로 추적 초기화
}
enqueue(&q, startVertex);
graph->visited[startVertex] = 1;
distance[startVertex] = 0; // 시작 정점의 거리는 0
while (!isEmpty(&q)) {
int currentVertex = dequeue(&q);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjList[currentVertex][i] == 1 && !graph->visited[i]) {
enqueue(&q, i);
graph->visited[i] = 1;
distance[i] = distance[currentVertex] + 1; // 거리 갱신
previous[i] = currentVertex; // 경로 추적
if (i == targetVertex) {
break; // 목표 정점에 도달하면 탐색 종료
}
}
}
}
// 최단 경로 출력
printf("Shortest path from %d to %d: ", startVertex, targetVertex);
int path[MAX_VERTICES];
int count = 0;
for (int v = targetVertex; v != -1; v = previous[v]) {
path[count++] = v;
}
for (int i = count - 1; i >= 0; i--) {
printf("%d ", path[i]);
}
printf("\nDistance: %d\n", distance[targetVertex]);
}
그래프 초기화 및 메인 함수
int main() {
Graph graph;
initializeGraph(&graph, 6);
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 4);
addEdge(&graph, 4, 5);
printf("BFS Shortest Path from 0 to 5:\n");
bfsShortestPath(&graph, 0, 5);
return 0;
}
결과 분석
그래프:
0 - 1 - 3 - 4 - 5
| |
2-------
출력 결과:
Shortest path from 0 to 5: 0 2 3 4 5
Distance: 4
설명:
- 최단 경로는 BFS 탐색 과정에서 처음으로 도달한 경로입니다.
- 경로 복원을 통해 정점 5까지의 정확한 이동 순서를 출력합니다.
시간 및 공간 복잡도
- 시간 복잡도:
O(V + E)
(정점V
, 간선E
) - 공간 복잡도:
O(V)
(거리 배열과 이전 정점 배열)
BFS는 간단한 로직으로 무가중치 그래프에서 효율적으로 최단 경로를 찾을 수 있는 강력한 도구입니다.
BFS의 시간 및 공간 복잡도
BFS 알고리즘은 그래프 탐색에서 효율성과 성능을 결정하는 핵심 요소입니다. 이 섹션에서는 BFS의 시간 및 공간 복잡도를 분석하고, 구현과 응용에서 이를 최적화할 방법을 알아봅니다.
시간 복잡도
BFS의 시간 복잡도는 그래프의 표현 방식과 정점 및 간선의 개수에 따라 결정됩니다.
- 인접 리스트를 사용하는 경우
- BFS는 각 정점을 한 번 방문하고, 해당 정점과 연결된 모든 간선을 탐색합니다.
- 복잡도:
O(V + E)
V
: 정점의 개수E
: 간선의 개수
- 인접 행렬을 사용하는 경우
- 각 정점에 대해 모든 정점을 확인하므로 탐색 시간이 늘어납니다.
- 복잡도:
O(V^2)
예시 비교:
- 정점 5개, 간선 4개인 그래프
- 인접 리스트:
O(5 + 4) = O(9)
- 인접 행렬:
O(5^2) = O(25)
공간 복잡도
BFS의 공간 복잡도는 그래프 저장 방식과 추가 데이터 구조(큐, 방문 배열)에 따라 달라집니다.
- 인접 리스트의 경우
- 그래프 저장:
O(V + E)
(정점 + 간선 저장) - 큐와 방문 배열:
O(V)
- 전체:
O(V + E)
- 인접 행렬의 경우
- 그래프 저장:
O(V^2)
(행렬 크기) - 큐와 방문 배열:
O(V)
- 전체:
O(V^2)
예시 비교:
- 정점 5개, 간선 4개인 그래프
- 인접 리스트:
O(5 + 4) + O(5) = O(14)
- 인접 행렬:
O(5^2) + O(5) = O(30)
효율성 최적화
- 인접 리스트 활용: 희소 그래프에서는 인접 리스트가 더 메모리 효율적이며 빠릅니다.
- 방문 배열 사용: 방문 여부를 빠르게 확인하여 중복 작업을 방지합니다.
- 큐 크기 최적화: 큐의 크기를 정점 수로 제한하여 메모리 사용을 관리합니다.
그래프 크기에 따른 성능 평가
- 희소 그래프:
정점이 많고 간선이 적은 그래프는O(V + E)
복잡도를 가지는 인접 리스트가 유리합니다. - 밀집 그래프:
정점과 간선이 비슷한 그래프에서는 인접 행렬이 단순한 구현과 빠른 간선 탐색이 장점입니다.
실제 응용에서 고려 사항
- 데이터 크기: 그래프가 매우 크다면 메모리 효율성을 위해 인접 리스트를 사용합니다.
- 탐색 빈도: 정점 간 연결 여부를 자주 확인해야 한다면 인접 행렬이 더 빠릅니다.
BFS는 다양한 문제에서 효율적으로 사용되지만, 그래프의 구조와 크기에 따라 적절한 데이터 표현 방식과 최적화 전략을 선택하는 것이 중요합니다.
BFS 구현 시 주의할 점
BFS는 간단한 알고리즘처럼 보이지만, 구현 과정에서 몇 가지 주의할 사항이 있습니다. 이 섹션에서는 BFS 구현 시 자주 발생하는 실수와 이를 방지하기 위한 방법을 설명합니다.
1. 방문 배열을 초기화하지 않음
문제:
방문 배열을 초기화하지 않으면 이전 탐색의 결과가 남아 예상치 못한 동작이 발생할 수 있습니다.
해결 방법:
- BFS 시작 전에 모든 정점을
0
(미방문)으로 초기화해야 합니다.
for (int i = 0; i < graph->numVertices; i++) {
graph->visited[i] = 0;
}
2. 큐 오버플로 또는 언더플로
문제:
큐를 사용할 때, 정점이 많거나 큐 포인터를 잘못 관리하면 오버플로 또는 언더플로가 발생할 수 있습니다.
해결 방법:
- 큐 크기를 적절히 설정하고, 큐 연산(삽입/제거)에서 경계 조건을 명확히 확인합니다.
int isFull(Queue *q) {
return q->rear == MAX_VERTICES - 1;
}
int isEmpty(Queue *q) {
return q->front > q->rear;
}
3. 간선 방향 및 그래프 종류를 고려하지 않음
문제:
무방향 그래프와 방향 그래프를 구분하지 않고 구현하면, 일부 경로를 놓치거나 불필요한 경로를 탐색할 수 있습니다.
해결 방법:
- 간선 추가 시 방향 여부를 명확히 정의합니다.
void addEdge(Graph *graph, int src, int dest, int isDirected) {
graph->adjList[src][dest] = 1;
if (!isDirected) {
graph->adjList[dest][src] = 1;
}
}
4. 그래프가 연결되어 있지 않은 경우 처리하지 않음
문제:
그래프가 여러 연결 컴포넌트로 나뉘어 있으면 BFS가 일부 컴포넌트만 탐색하고 종료될 수 있습니다.
해결 방법:
- 모든 정점에 대해 BFS를 실행하여 연결되지 않은 컴포넌트도 탐색합니다.
for (int i = 0; i < graph->numVertices; i++) {
if (!graph->visited[i]) {
bfs(graph, i);
}
}
5. 중복 방문 체크 누락
문제:
방문 여부를 확인하지 않으면 같은 정점을 여러 번 큐에 삽입하여 성능이 저하됩니다.
해결 방법:
- 정점 방문 시 반드시 방문 배열을 갱신합니다.
if (!graph->visited[neighbor]) {
graph->visited[neighbor] = 1;
enqueue(&q, neighbor);
}
6. 데이터 입력 형식 오류
문제:
그래프의 정점 번호가 입력 데이터와 일치하지 않으면 런타임 오류가 발생할 수 있습니다.
해결 방법:
- 입력 데이터의 유효성을 확인하고, 정점 번호가
0
이상numVertices - 1
이하인지 검사합니다.
if (src < 0 || src >= graph->numVertices || dest < 0 || dest >= graph->numVertices) {
printf("Invalid edge: (%d, %d)\n", src, dest);
return;
}
7. 메모리 관리 문제
문제:
동적 메모리를 사용하는 경우, 메모리 할당과 해제를 적절히 관리하지 않으면 메모리 누수 또는 잘못된 참조가 발생합니다.
해결 방법:
- 동적 메모리를 할당한 후 탐색 종료 시 반드시 해제합니다.
free(queue);
8. 출력 순서를 잘못 설정
문제:
정점을 탐색한 순서대로 출력하지 않으면 결과가 혼란스러울 수 있습니다.
해결 방법:
- BFS 탐색 순서대로 출력하도록 큐에서 정점을 꺼낼 때만 출력합니다.
int currentVertex = dequeue(&q);
printf("Visited %d\n", currentVertex);
결론
BFS는 구현이 간단한 알고리즘이지만, 세부적인 실수로 인해 예상치 못한 결과를 초래할 수 있습니다. 위에서 설명한 주의사항과 해결 방법을 따르면 올바르고 효율적인 BFS 구현이 가능합니다.
요약
본 기사에서는 C 언어를 활용한 BFS 알고리즘의 개념, 구현, 응용, 그리고 효율성에 대해 다뤘습니다. BFS는 큐 자료구조를 기반으로 그래프를 레벨 단위로 탐색하며, 최단 경로 찾기와 같은 다양한 문제를 해결할 수 있는 강력한 알고리즘입니다. 또한, 구현 시 방문 배열 초기화, 큐 관리, 그래프 유형 구분 등에서 발생할 수 있는 문제를 살펴보고, 이를 방지하는 방법을 소개했습니다. 이를 통해 BFS를 이해하고 실제 문제에 적용하는 능력을 갖출 수 있습니다.