MENU
  1. ホーム
  2. C 언어
  3. C 언어로 구현하는 BFS를 활용한 최단 경로 탐색

C 언어로 구현하는 BFS를 활용한 최단 경로 탐색

C 언어

BFS(Breadth-First Search)는 그래프 탐색 알고리즘으로, 노드와 간선으로 이루어진 구조에서 최단 경로를 탐색하는 데 널리 사용됩니다. 이 기사는 C 언어를 이용하여 BFS를 구현하고, 이를 활용해 최단 경로를 탐색하는 방법을 단계별로 알아보는 데 중점을 둡니다. BFS의 기본 원리, 그래프 표현 방식, 구현 예제, 그리고 실제 응용 사례까지 종합적으로 다루어 독자들이 실질적으로 활용할 수 있는 기초와 통찰을 제공합니다.

목차

BFS란 무엇인가?


BFS(Breadth-First Search)는 그래프 탐색 알고리즘 중 하나로, 노드를 계층적으로 탐색하며 목표 노드에 도달할 때까지 진행합니다. 시작 노드에서 인접한 모든 노드를 먼저 탐색한 후, 그다음 단계의 노드를 탐색하는 방식으로 작동합니다.

BFS의 기본 원리


BFS는 큐(Queue)를 활용해 노드를 탐색하며, 다음과 같은 과정으로 수행됩니다:

  1. 시작 노드를 큐에 삽입합니다.
  2. 큐에서 노드를 꺼내 방문하고, 해당 노드와 인접한 노드를 큐에 추가합니다.
  3. 큐가 빌 때까지 반복합니다.

BFS의 특징

  • 최단 경로 탐색: BFS는 간선의 가중치가 동일한 그래프에서 최단 경로를 보장합니다.
  • 넓이 우선 탐색: 탐색 범위를 점진적으로 확장하며 모든 노드를 방문합니다.
  • 비순환적 작업: 한 번 방문한 노드는 다시 탐색하지 않도록 처리합니다.

BFS는 효율성과 단순성으로 인해 그래프 탐색, 최단 경로 탐색, 네트워크 분석 등 다양한 분야에서 활용되고 있습니다.

그래프 표현 방식


그래프를 컴퓨터에서 다루기 위해서는 데이터를 저장할 적절한 방법이 필요합니다. 그래프 표현 방식은 BFS 알고리즘 구현의 핵심 요소 중 하나입니다.

인접 리스트


인접 리스트는 각 노드가 연결된 노드 목록을 저장하는 방식입니다. 이 방식은 메모리 효율적이며, 특정 노드와 인접한 노드를 찾는 데 적합합니다.

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;
  • 장점: 간선이 적은 희소 그래프에 적합.
  • 단점: 특정 노드 간의 연결 여부를 확인하려면 순회가 필요.

인접 행렬


인접 행렬은 2차원 배열을 사용해 그래프를 표현합니다. 배열의 각 요소는 두 노드 사이의 간선 여부를 나타냅니다.

int graph[MAX][MAX] = {0};
  • 장점: 두 노드 간의 연결 여부를 O(1) 시간에 확인 가능.
  • 단점: 메모리 소모가 많으며, 간선이 적은 경우 비효율적.

비교

표현 방식메모리 효율성간선 확인 속도BFS 탐색 성능
인접 리스트높음낮음효율적
인접 행렬낮음빠름비교적 비효율적

BFS에서의 선택


BFS를 구현할 때, 그래프의 밀도와 요구사항에 따라 인접 리스트나 인접 행렬 중 적합한 방식을 선택해야 합니다. 일반적으로 희소 그래프는 인접 리스트를, 밀집 그래프는 인접 행렬을 사용하는 것이 효과적입니다.

BFS의 구현 방법


C 언어에서 BFS를 구현하려면 그래프를 적절히 표현하고, 탐색 과정을 관리하기 위한 자료 구조를 사용해야 합니다. 다음은 BFS를 단계별로 구현하는 방법입니다.

1. 그래프 생성


그래프는 인접 리스트나 인접 행렬을 사용해 표현할 수 있습니다. 인접 리스트를 사용하는 예제는 다음과 같습니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

2. 간선 추가 함수


노드 간의 연결을 추가합니다.

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 무방향 그래프의 경우
    newNode = malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

3. BFS 함수


큐를 사용하여 BFS를 구현합니다.

void BFS(Graph* graph, int startVertex) {
    int* queue = malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;

    graph->visited[startVertex] = 1;
    queue[rear++] = startVertex;

    while (front < rear) {
        int currentVertex = queue[front++];
        printf("Visited %d\n", currentVertex);

        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                queue[rear++] = adjVertex;
            }
            temp = temp->next;
        }
    }
    free(queue);
}

4. 메인 함수


그래프를 생성하고 BFS를 실행합니다.

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 3, 5);

    printf("Breadth First Search starting from vertex 0:\n");
    BFS(graph, 0);

    return 0;
}

5. 실행 결과


BFS 실행 시, 탐색 결과는 다음과 같습니다:

Visited 0  
Visited 1  
Visited 2  
Visited 3  
Visited 4  
Visited 5

이 과정은 그래프 탐색의 기초로, BFS의 작동 원리를 이해하는 데 매우 유용합니다.

최단 경로 탐색 원리


BFS는 그래프에서 간선의 가중치가 동일한 경우(예: 모든 간선의 가중치가 1) 최단 경로를 탐색하는 데 적합한 알고리즘입니다. 이는 BFS가 그래프를 계층적으로 탐색하며 각 노드에 도달하는 최소 간선을 보장하기 때문입니다.

BFS와 최단 경로


BFS의 핵심 원리는 다음과 같습니다:

  1. 시작 노드에서 인접 노드를 먼저 탐색합니다.
  2. 인접 노드를 방문한 후, 그다음 계층으로 넘어가면서 탐색을 계속합니다.
  3. BFS 탐색 과정에서 처음 방문한 노드는 최단 경로로 도달한 것입니다.

최단 경로 탐색 과정


다음은 간단한 그래프에서 BFS로 최단 경로를 찾는 과정입니다:

그래프 구조:

0 -- 1 -- 3  
|    |  
2 -- 4
  1. 시작 노드 0에서 탐색을 시작합니다.
  2. 0에서 인접한 노드(1, 2)를 큐에 추가합니다.
  3. 큐에서 노드 1을 방문하고, 1의 인접 노드(3, 4)를 큐에 추가합니다.
  4. 큐에서 노드 2를 방문하고, 2의 인접 노드(4)를 큐에 추가(이미 방문한 노드는 생략).
  5. 큐에서 노드 3을 방문하고, 탐색 종료.

최단 경로 계산:

  • 노드 0에서 노드 3까지의 최단 경로는 0 -> 1 -> 3으로, BFS는 이를 보장합니다.

코드에서의 최단 경로 추적


BFS를 사용해 경로를 추적하려면, 각 노드의 부모 노드를 저장해야 합니다.

void BFSWithPath(Graph* graph, int startVertex, int targetVertex) {
    int* queue = malloc(graph->numVertices * sizeof(int));
    int* parent = malloc(graph->numVertices * sizeof(int));
    for (int i = 0; i < graph->numVertices; i++) {
        parent[i] = -1;  // 초기화
    }
    int front = 0, rear = 0;

    graph->visited[startVertex] = 1;
    queue[rear++] = startVertex;

    while (front < rear) {
        int currentVertex = queue[front++];
        if (currentVertex == targetVertex) break;

        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                parent[adjVertex] = currentVertex;
                queue[rear++] = adjVertex;
            }
            temp = temp->next;
        }
    }

    // 최단 경로 출력
    int path[graph->numVertices];
    int count = 0, v = targetVertex;
    while (v != -1) {
        path[count++] = v;
        v = parent[v];
    }
    printf("Shortest path: ");
    for (int i = count - 1; i >= 0; i--) {
        printf("%d ", path[i]);
    }
    printf("\n");

    free(queue);
    free(parent);
}

출력 예시


위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:

Shortest path: 0 1 3

왜 BFS가 최단 경로를 보장하는가?

  • BFS는 노드의 탐색 순서를 계층적으로 수행합니다.
  • 먼저 방문한 경로가 가장 짧은 경로가 되며, 이후 탐색에서 더 짧은 경로는 존재할 수 없습니다.

따라서, BFS는 간선의 가중치가 동일한 그래프에서 최단 경로 탐색을 위한 강력한 도구입니다.

BFS 코드 예제


BFS를 사용해 그래프를 탐색하고 최단 경로를 찾는 실제 코드 예제를 살펴봅니다. 이 예제는 인접 리스트를 활용한 C 언어 구현입니다.

전체 코드

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 그래프 구조체 정의
typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

// 그래프 생성 함수
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// 간선 추가 함수
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    newNode = malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// BFS 함수
void BFS(Graph* graph, int startVertex) {
    int* queue = malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;

    graph->visited[startVertex] = 1;
    queue[rear++] = startVertex;

    printf("BFS Order: ");
    while (front < rear) {
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);

        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                queue[rear++] = adjVertex;
            }
            temp = temp->next;
        }
    }
    printf("\n");
    free(queue);
}

// 메인 함수
int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 5);

    printf("Breadth First Search starting from vertex 0:\n");
    BFS(graph, 0);

    return 0;
}

코드 설명

  1. 그래프 생성 및 초기화
  • createGraph 함수는 주어진 정점 수로 그래프를 초기화합니다.
  • 모든 정점은 초기 상태에서 방문되지 않은 것으로 설정됩니다.
  1. 간선 추가
  • addEdge 함수는 두 노드 간의 연결을 양방향으로 추가합니다.
  1. BFS 탐색
  • BFS 함수는 큐를 이용해 정점 방문 순서를 관리합니다.
  • 방문한 정점은 출력되며, 인접 노드가 큐에 추가됩니다.

실행 결과


위 코드를 실행하면 다음과 같은 출력이 나타납니다:

Breadth First Search starting from vertex 0:  
BFS Order: 0 1 2 3 4 5

코드 확장


위 코드는 간단한 BFS를 구현했으며, 필요에 따라 다음과 같은 기능을 추가할 수 있습니다:

  • 최단 경로를 저장하고 출력.
  • 방향 그래프 지원.
  • 노드 간 간선 가중치를 고려한 확장.

이 코드를 기반으로 다양한 BFS 응용 문제를 해결할 수 있습니다.

BFS의 응용과 한계


BFS는 다양한 분야에서 활용되며, 특정 문제를 해결하는 데 강력한 도구를 제공합니다. 하지만 알고리즘의 특성과 한계를 이해하면 더 효과적으로 사용할 수 있습니다.

BFS의 응용 사례

1. 최단 경로 탐색


BFS는 간선 가중치가 동일한 그래프에서 최단 경로를 탐색하는 데 적합합니다. 예를 들어, 다음과 같은 상황에 활용됩니다:

  • 미로 문제: 출발지에서 목표 지점까지 최단 경로 찾기.
  • 소셜 네트워크 분석: 두 사용자 간 최소 연결 경로 계산.

2. 연결 요소 탐색


BFS를 사용하면 그래프에서 서로 연결된 구성 요소를 찾을 수 있습니다. 이는 네트워크의 분리된 영역을 분석하는 데 유용합니다.

3. 전염 시뮬레이션


BFS는 전염병의 확산 시뮬레이션에 활용될 수 있습니다. 각 노드는 개인을, 간선은 접촉 관계를 나타냅니다. BFS를 통해 전염 경로와 소요 시간을 예측할 수 있습니다.

4. 최적화 문제


BFS는 최적화 문제의 상태 공간 탐색에서도 사용됩니다. 예를 들어, 체스나 퍼즐 게임의 가능한 상태를 계층적으로 탐색할 때 유용합니다.

BFS의 한계

1. 가중치가 있는 그래프


BFS는 간선 가중치가 동일하지 않은 경우 최단 경로를 보장하지 못합니다. 이때는 다익스트라(Dijkstra) 알고리즘과 같은 대안이 필요합니다.

2. 메모리 소모


BFS는 큐를 사용하여 탐색 상태를 저장하므로, 매우 큰 그래프에서는 메모리 소모가 큽니다. 특히 노드와 간선이 많은 경우 스택 기반 DFS보다 비효율적일 수 있습니다.

3. 탐색 시간


BFS는 모든 노드를 탐색해야 하므로, 탐색 대상이 큰 경우 수행 시간이 길어질 수 있습니다. 예를 들어, 넓은 범위의 목표 지점을 탐색할 때 DFS보다 느릴 수 있습니다.

효율적인 사용을 위한 전략

  • 필요에 따라 알고리즘 선택: 그래프의 특성(간선 가중치, 밀도)에 따라 BFS와 다른 알고리즘을 병행 사용.
  • 메모리 최적화: 대규모 그래프에서는 적합한 데이터 구조와 방문 기록 방식을 설계.
  • 혼합 탐색 사용: 문제에 따라 BFS와 DFS를 조합하거나 이진 탐색 트리와 함께 사용.

BFS는 간단하면서도 강력한 알고리즘이지만, 문제의 특성과 그래프의 속성을 고려하여 적절히 사용하는 것이 중요합니다. 이를 통해 BFS의 장점을 최대화할 수 있습니다.

요약


BFS(Breadth-First Search)는 그래프 탐색과 최단 경로 계산에 효과적인 알고리즘으로, 계층적 탐색 방식을 통해 간단하면서도 강력한 문제 해결 도구를 제공합니다. 이 기사에서는 BFS의 원리, 그래프 표현 방법, C 언어 구현, 그리고 응용 사례와 한계를 다루었습니다. BFS는 미로 탐색, 네트워크 분석, 상태 공간 탐색 등 다양한 분야에서 활용되며, 알고리즘의 특성을 이해하고 적절히 활용하면 효율적인 문제 해결이 가능합니다.

C 언어
BFS C언어 알고리즘 최단 경로
목차