[c언어] 큐와 너비 우선 탐색

26 Dec 2023

c언어

이번에는 C언어를 사용하여 큐와 너비 우선 탐색(BFS)을 구현하는 방법에 대해 알아보겠습니다.

큐

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First-In-First-Out) 구조를 가지고 있습니다. C언어에서 큐를 구현할 때에는 배열을 활용하거나 연결 리스트를 사용할 수 있습니다.

아래는 C언어에서 배열을 사용한 큐의 구현 예시입니다.

#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front, rear;
} Queue;

void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(Queue *q) {
    return q->front == q->rear;
}

int isFull(Queue *q) {
    return q->rear == MAX_QUEUE_SIZE - 1;
}

void enqueue(Queue *q, int value) {
    if (!isFull(q)) {
        q->data[++(q->rear)] = value;
    }
}

int dequeue(Queue *q) {
    if (!isEmpty(q)) {
        return q->data[++(q->front)];
    }
    return -1; // 에러 시 -1 반환
}

너비 우선 탐색 (BFS)

너비 우선 탐색은 그래프나 트리를 탐색하는 알고리즘 중 하나로, 시작 정점으로부터 가장 가까운 정점부터 모두 방문하는 방식입니다. 큐를 사용하여 구현할 수 있으며, 모든 정점을 방문하고자 할 때 많이 사용됩니다.

아래는 C언어에서 BFS를 구현하는 예시 코드입니다.

#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0

int visited[MAX_VERTICES];
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
int n;

void bfs(int v) {
    Queue q;
    initQueue(&q);
    visit(v);
    visited[v] = TRUE;
    enqueue(&q, v);
    while (!isEmpty(&q)) {
        v = dequeue(&q);
        for (int i = 0; i < n; i++) {
            if (adjMatrix[v][i] && !visited[i]) {
                visit(i);
                visited[i] = TRUE;
                enqueue(&q, i);
            }
        }
    }
}

이렇게 하면 C언어에서 큐와 너비 우선 탐색을 구현할 수 있습니다. 다음 번 포스트에서는 실제로 이를 활용한 예시를 다뤄보겠습니다.