MENU
  1. ホーム
  2. C 언어
  3. C 언어로 너비 우선 탐색(BFS) 구현하기

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

C 언어

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

목차
  1. BFS란 무엇인가
    1. BFS의 특징
    2. BFS의 활용 사례
    3. BFS와 DFS의 비교
  2. BFS의 동작 원리
    1. BFS 알고리즘의 단계
    2. 시각적 예시
    3. 결과
  3. 그래프의 표현 방법
    1. 인접 리스트
    2. 인접 행렬
    3. 표현 방식의 선택
  4. BFS 알고리즘의 구현
    1. 필요한 데이터 구조 정의
    2. BFS 알고리즘 구현
    3. 메인 함수
    4. 결과
  5. BFS 예제 코드 분석
    1. 1. 그래프 초기화
    2. 2. 간선 추가
    3. 3. BFS 알고리즘
    4. 4. 메인 함수
    5. 5. BFS 동작 순서 분석
    6. 결과
  6. BFS 응용: 최단 경로 찾기
    1. 최단 경로를 찾는 BFS 알고리즘
    2. 코드 구현
    3. 그래프 초기화 및 메인 함수
    4. 결과 분석
    5. 시간 및 공간 복잡도
  7. BFS의 시간 및 공간 복잡도
    1. 시간 복잡도
    2. 공간 복잡도
    3. 효율성 최적화
    4. 그래프 크기에 따른 성능 평가
    5. 실제 응용에서 고려 사항
  8. BFS 구현 시 주의할 점
    1. 1. 방문 배열을 초기화하지 않음
    2. 2. 큐 오버플로 또는 언더플로
    3. 3. 간선 방향 및 그래프 종류를 고려하지 않음
    4. 4. 그래프가 연결되어 있지 않은 경우 처리하지 않음
    5. 5. 중복 방문 체크 누락
    6. 6. 데이터 입력 형식 오류
    7. 7. 메모리 관리 문제
    8. 8. 출력 순서를 잘못 설정
    9. 결론
  9. 요약

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과 연결된 정점 2와 4를 큐에 추가.
  • 큐 상태: [2, 4]
  • 방문 배열: [1: 방문, 2: 방문, 3: 미방문, 4: 방문, 5: 미방문]
  1. 두 번째 반복
  • 큐에서 2 제거, 2와 연결된 정점 3과 5를 큐에 추가.
  • 큐 상태: [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] = 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;
            }
        }
    }
}


설명:

  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를 이해하고 실제 문제에 적용하는 능력을 갖출 수 있습니다.

C 언어
BFS C언어 너비 우선 탐색 알고리즘
목차
  1. BFS란 무엇인가
    1. BFS의 특징
    2. BFS의 활용 사례
    3. BFS와 DFS의 비교
  2. BFS의 동작 원리
    1. BFS 알고리즘의 단계
    2. 시각적 예시
    3. 결과
  3. 그래프의 표현 방법
    1. 인접 리스트
    2. 인접 행렬
    3. 표현 방식의 선택
  4. BFS 알고리즘의 구현
    1. 필요한 데이터 구조 정의
    2. BFS 알고리즘 구현
    3. 메인 함수
    4. 결과
  5. BFS 예제 코드 분석
    1. 1. 그래프 초기화
    2. 2. 간선 추가
    3. 3. BFS 알고리즘
    4. 4. 메인 함수
    5. 5. BFS 동작 순서 분석
    6. 결과
  6. BFS 응용: 최단 경로 찾기
    1. 최단 경로를 찾는 BFS 알고리즘
    2. 코드 구현
    3. 그래프 초기화 및 메인 함수
    4. 결과 분석
    5. 시간 및 공간 복잡도
  7. BFS의 시간 및 공간 복잡도
    1. 시간 복잡도
    2. 공간 복잡도
    3. 효율성 최적화
    4. 그래프 크기에 따른 성능 평가
    5. 실제 응용에서 고려 사항
  8. BFS 구현 시 주의할 점
    1. 1. 방문 배열을 초기화하지 않음
    2. 2. 큐 오버플로 또는 언더플로
    3. 3. 간선 방향 및 그래프 종류를 고려하지 않음
    4. 4. 그래프가 연결되어 있지 않은 경우 처리하지 않음
    5. 5. 중복 방문 체크 누락
    6. 6. 데이터 입력 형식 오류
    7. 7. 메모리 관리 문제
    8. 8. 출력 순서를 잘못 설정
    9. 결론
  9. 요약