C 언어로 너비 우선 탐색(BFS) 구현하기

너비 우선 탐색(BFS, Breadth-First Search)은 그래프 탐색 알고리즘으로, 시작 정점에서 가까운 정점부터 순차적으로 탐색을 진행합니다. 이 알고리즘은 큐 자료구조를 사용하여 구현되며, 무가중치 그래프에서 최단 경로를 찾는 데 유용합니다. 본 기사에서는 BFS의 개념, 동작 원리, C 언어를 이용한 구현 방법과 예제를 다룹니다. 이를 통해 그래프 탐색 문제를 효과적으로 해결할 수 있는 기초 지식을 제공하겠습니다.

BFS란 무엇인가


BFS(Breadth-First Search)는 그래프 탐색 알고리즘으로, 시작 정점에서 가까운 정점부터 차례로 탐색하는 방식입니다.

BFS의 특징

  • 레벨 기반 탐색: 시작 정점에서 같은 거리에 있는 정점들을 먼저 탐색합니다.
  • 큐 자료구조 사용: 탐색 과정에서 방문할 정점들을 순서대로 저장하고 처리합니다.
  • 방문 기록 필요: 정점의 중복 방문을 방지하기 위해 방문 여부를 기록합니다.

BFS의 활용 사례

  • 무가중치 그래프의 최단 경로 찾기: 각 간선의 가중치가 동일한 그래프에서 최단 경로를 탐색할 때 효과적입니다.
  • 그래프의 연결성 확인: 연결된 컴포넌트나 서브그래프를 탐색하는 데 유용합니다.
  • 네트워크 흐름 분석: 네트워크나 소셜 그래프에서 데이터의 흐름을 추적할 때 사용됩니다.

BFS와 DFS의 비교

  • BFS는 큐를 사용해 레벨 단위로 탐색하는 반면, DFS는 스택을 사용하여 깊이 우선으로 탐색합니다.
  • BFS는 최단 경로를 보장하지만, DFS는 최단 경로를 보장하지 않습니다.
  • 탐색 우선순위와 사용 사례에서 차이가 있습니다.

BFS는 그래프 탐색의 기초적인 알고리즘으로, 문제를 구조화하고 효율적으로 해결하는 데 필수적인 도구입니다.

BFS의 동작 원리

BFS는 큐 자료구조를 활용하여 그래프를 탐색합니다. 시작 정점에서 시작하여 점차 주변 정점으로 탐색을 확장하는 방식으로 작동합니다.

BFS 알고리즘의 단계

  1. 초기화
  • 시작 정점을 큐에 추가하고 방문 여부를 기록합니다.
  • 방문 여부를 확인하기 위한 배열을 생성합니다.
  1. 탐색 반복
  • 큐에서 정점을 하나 꺼내 해당 정점과 연결된 모든 정점을 확인합니다.
  • 방문하지 않은 정점은 큐에 추가하고 방문 여부를 기록합니다.
  1. 탐색 종료
  • 큐가 비어 있으면 탐색을 종료합니다.

시각적 예시


다음과 같은 그래프를 가정합니다:

Graph:  
1 - 2 - 3  
|   |  
4 - 5  
  1. 초기화
  • 시작 정점: 1
  • 큐 상태: [1]
  • 방문 배열: [1: 방문, 2: 미방문, 3: 미방문, 4: 미방문, 5: 미방문]
  1. 첫 번째 반복
  • 큐에서 1 제거, 1과 연결된 정점 24를 큐에 추가.
  • 큐 상태: [2, 4]
  • 방문 배열: [1: 방문, 2: 방문, 3: 미방문, 4: 방문, 5: 미방문]
  1. 두 번째 반복
  • 큐에서 2 제거, 2와 연결된 정점 35를 큐에 추가.
  • 큐 상태: [4, 3, 5]
  • 방문 배열: [1: 방문, 2: 방문, 3: 방문, 4: 방문, 5: 방문]
  1. 반복 종료
  • 큐에서 정점들을 차례로 제거하며 탐색 완료.

결과


탐색 순서: 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 알고리즘을 구현하는 방법을 단계별로 설명합니다. 이번 구현에서는 그래프를 인접 리스트로 표현하며, 큐 자료구조를 활용합니다.

필요한 데이터 구조 정의

  1. 그래프 구조체
    그래프는 정점 수와 인접 리스트로 표현됩니다.
   #define MAX_VERTICES 100

   typedef struct Graph {
       int numVertices;
       int adjList[MAX_VERTICES][MAX_VERTICES];
       int visited[MAX_VERTICES];
   } Graph;
  1. 큐 구현
    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 알고리즘 구현

  1. 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;
               }
           }
       }
   }
  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] = 1src에서 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;
            }
        }
    }
}


설명:

  1. 큐를 초기화하고, 시작 정점을 큐에 삽입한 뒤 방문 배열을 업데이트합니다.
  2. 큐가 비어 있지 않는 동안 반복하여 다음 작업을 수행합니다:
  • 큐에서 정점을 꺼내 방문합니다.
  • 꺼낸 정점과 연결된 모든 미방문 정점을 큐에 삽입하고 방문 배열을 갱신합니다.
  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  


탐색 과정:

  1. 시작 정점 0: 큐에 [0] 삽입 → 방문: 0.
  2. 정점 1, 4 큐에 삽입: 큐 [1, 4] → 방문: 1, 4.
  3. 정점 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에 다음을 추가로 구현해야 합니다:

  1. 거리 배열: 시작 정점에서 각 정점까지의 거리를 저장합니다.
  2. 경로 추적: 이전 정점을 기록하여 경로를 복원할 수 있습니다.

코드 구현

  1. 거리와 이전 정점 배열 추가
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의 시간 복잡도는 그래프의 표현 방식과 정점 및 간선의 개수에 따라 결정됩니다.

  1. 인접 리스트를 사용하는 경우
  • BFS는 각 정점을 한 번 방문하고, 해당 정점과 연결된 모든 간선을 탐색합니다.
  • 복잡도: O(V + E)
    • V: 정점의 개수
    • E: 간선의 개수
  1. 인접 행렬을 사용하는 경우
  • 각 정점에 대해 모든 정점을 확인하므로 탐색 시간이 늘어납니다.
  • 복잡도: O(V^2)

예시 비교:

  • 정점 5개, 간선 4개인 그래프
  • 인접 리스트: O(5 + 4) = O(9)
  • 인접 행렬: O(5^2) = O(25)

공간 복잡도


BFS의 공간 복잡도는 그래프 저장 방식과 추가 데이터 구조(큐, 방문 배열)에 따라 달라집니다.

  1. 인접 리스트의 경우
  • 그래프 저장: O(V + E) (정점 + 간선 저장)
  • 큐와 방문 배열: O(V)
  • 전체: O(V + E)
  1. 인접 행렬의 경우
  • 그래프 저장: 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를 이해하고 실제 문제에 적용하는 능력을 갖출 수 있습니다.