알고리즘

[알고리즘] BFS (너비 우선 탐색)

Song 컴퓨터공학 2023. 5. 28. 17:58

 너비 우선 탐색, BFS 이란?

BFS 란 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. BFS는 큐를 사용해 구현하며 DFS와 마찬가지로 인접 행렬로 표현된 그래프와 인접 리스트로 표현된 그래프의 경우 조금 달라집니다. 오늘 포스팅에서는 BFS 의 동작을 단계별로 이해해보고 인접 행렬로 표현된 그래프에 적용할 수 있는 BFS 코드를 구현해보겠습니다. BFS 도 DFS와 마찬가지로 시간 복잡도는 인접 행렬인지 인접 그래프로 표현되었는지에 따라 달라지게 되는데 인접 행렬의 경우 O(n^2), 인접 그래프의 경우 O(n+e) 가 됩니다.

 

BFS의 구현에 있어서 큐는 반드시 알아야 하기 때문에 큐의 개념이 헷갈리신다면 아래의 포스팅을 참고해주세요.

 

[C 자료구조] 큐(Queue) - 선형큐 / 원형큐 배열 구현

큐(Queue) 란? 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 구조인 반면, 큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이런 특성을 FIFO (First-In First-Out) 이라고 합니다.

songsite123.tistory.com

 

 

 BFS 진행 과정

 

BFS는 아래의 과정으로 진행됩니다.

  1. 시작정점을 방문하고 큐에 넣는다.
  2. 큐에서 가장 앞의 노드를 빼고 해당 노드의 인접 정점을 방문하지 않았다면 모두 방문하고 큐에 넣는다.
  3. 큐가 빌 때까지 2를 반복한다.

가장 먼저 시작 정점을 방문하게 되고 큐에 시작 정점을 넣습니다.

큐에서 가장 앞의 노드를 빼고 해당 노드의 인접 노드를 조사합니다. 그리고 만약 방문한 정점이라면 큐에 넣지 않고, 방문하지 않은 정점이라면 모두 큐에 넣습니다.

이 연산은 당연히 한번에 진행되는 것이 아니라 3단계에 걸쳐서 진행됩니다.

  • B노드는 방문하지 않았으므로 방문하고 큐에 넣는다.
  • C노드는 방문하지 않았으므로 방문하고 큐에 넣는다.
  • E노드는 방문하지 않았으므로 방문하고 큐에 넣는다.

큐의 가장 앞 노드인 B 노드를 빼고, 해당 노드의 인접 노드를 조사합니다.

  • A 노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.
  • C 노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

큐의 가장 앞 노드인 C 노드를 빼고, 해당 노드의 인접 노드를 조사합니다.

  • B노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.
  • A노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.
  • D노드는 방문하지 않았으므로 방문하고 큐에 넣는다.

큐의 가장 앞 노드인 E 노드를 빼고, 해당 노드의 인접 노드를 조사합니다.

  • A 노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.
  • D 노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.
  • C 노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

큐의 가장 앞 노드인 D 노드를 빼고, 해당 노드의 인접 노드를 조사합니다.

  • C 노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.
  • E 노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

마지막으로 큐가 비었으므로 BFS를 종료합니다.

 BFS의 장단점

 

BFS의 장점

  • 노드의 수가 적고 깊이가 얕은 경우 빠르게 탐색이 가능하다.
  • 단순 검색 속도가 DFS보다 빠르다.
  • 너비를 우선 탐색하므로 답이 되는 경로가 여러개여도 최단 경로를 보장한다.

BFS의 단점

  • 큐에 다음에 탐색할 정점들을 저장해야 하므로 이에 따른 저장공간이 많이 필요하다.
  • 노드의 수가 많아지면 탐색할 노드 또한 많아져 시간이 오래 걸린다.

 

 BFS 구현

 

BFS는 큐를 사용해 구현하기 때문에 C로 구현할 경우 큐 구현 코드도 필요합니다. 인접 행렬로 표현된 그래프에 대한 BFS 코드만 확인해보겠습니다.

void bfs_mat(GraphType* g, int v)
{
    int w;
    QueueType q;

    queue_init(&q);     // 큐 초기화 
    visited[v] = TRUE;          // 정점 v 방문 표시 
    printf("%d ", v);
    enqueue(&q, v);			// 시작 정점을 큐에 저장 
    while (!is_empty(&q)) {
        v = dequeue(&q);		// 큐에 정점 추출 
        for (w = 0; w < g->n; w++)	// 인접 정점 탐색 
            if (g->adj_mat[v][w] && !visited[w]) {
                visited[w] = TRUE;    // 방문 표시
                printf("%d ", w);
                enqueue(&q, w); 	// 방문한 정점을 큐에 저장
            }
    }
}

DFS와 마찬가지로 visited 배열을 사용해 방문 표시를 해줍니다. 맨 처음 시작 정점을 큐에 삽입하기 전 출력을 하고 enqueue를 통해 큐에 넣어줍니다. 그리고 while 문을 통해 큐가 비면 종료하도록 하고 하나씩 꺼내서 인접 정점을 모두 조사하고 출력합니다. 

전체 코드 및 실행 결과

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

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct { // 큐 타입
    element  queue[MAX_QUEUE_SIZE];
    int  front, rear;
} QueueType;

// 공백 상태 검출 함수
void queue_init(QueueType* q)
{
    q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType* q)
{
    return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType* q)
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType* q, element item)
{
    if (is_full(q)) {
        fprintf(stderr, "큐가 포화상태입니다\n");
        exit(1);
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType* q)
{
    if (is_empty(q)) {
        fprintf(stderr, "큐가 공백상태입니다\n");
        exit(1);
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}


#define MAX_VERTICES 50
typedef struct GraphType {
    int n;	// 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

// 그래프 초기화 
void graph_init(GraphType* g)
{
    int r, c;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++)
        for (c = 0; c < MAX_VERTICES; c++)
            g->adj_mat[r][c] = 0;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}
void bfs_mat(GraphType* g, int v)
{
    int w;
    QueueType q;

    queue_init(&q);     // 큐 초기화 
    visited[v] = TRUE;          // 정점 v 방문 표시 
    printf("%d ", v);
    enqueue(&q, v);			// 시작 정점을 큐에 저장 
    while (!is_empty(&q)) {
        v = dequeue(&q);		// 큐에 정점 추출 
        for (w = 0; w < g->n; w++)	// 인접 정점 탐색 
            if (g->adj_mat[v][w] && !visited[w]) {
                visited[w] = TRUE;    // 방문 표시
                printf("%d ", w);
                enqueue(&q, w); 	// 방문한 정점을 큐에 저장
            }
    }
}

int main(void)
{
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    graph_init(g);
    for (int i = 0; i < 6; i++)
        insert_vertex(g, i);
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 0, 4);
    insert_edge(g, 4, 5);
    insert_edge(g, 1, 5);

    printf("너비 우선 탐색\n");
    bfs_mat(g, 0);
    printf("\n");
    free(g);
    return 0;
}

 

참고 :

https://code-lab1.tistory.com/16

C언어로 쉽게 풀어쓴 자료구조 - 생능출판

 

저작자표시 비영리 동일조건

'알고리즘' 카테고리의 다른 글

[알고리즘] DFS (깊이 우선 탐색) - 스택 구현 / 재귀 구현  (0) 2023.05.28

'알고리즘'의 다른글

  • 현재글[알고리즘] BFS (너비 우선 탐색)

관련글

티스토리툴바