17. 그래프 - 너비 우선 탐색(BFS, Breadth First Search) / 큐 자료구조 / 너비 우선 탐색 처리 순서 / 너비 우선 탐색 알고리즘 구현하기

너비 우선 탐색(BFS)

너비 우선 탐색은 너비를 우선으로 해서 탐색을 수행하는 탐색 알고리즘이다. DFS와 마찬가지로 맹목적으로 전체 노드를 탐색하고자 할 때 자주 사용되며, 큐(Queue) 자료구조에 기초한다.

 

너비 우선 탐색은 고급 그래프 탐색 알고리즘에서 자주 활용되므로, 잘 숙지해야 한다.

 

너비 우선 탐색 처리 순서

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고, 방문처리 한다.
3. 2의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

ex) 너비 우선 탐색 처리 과정

탐색 시작노드(1번)을 큐(왼쪽 테이블)에 삽입하고 방문처리 한다.

1번과 인접한 노드 2,3,8번을 큐에 모두 삽입하고 1은 빼낸다.

이제 2번(front/출구 에 있는 원소)을 기준으로, 2번과 인접한 7번을 큐에 넣고 2번을 뺀다.

 

3번(큐의 front/출구에 있는 원소)과 인접한 노드 4,5번을 모두 큐에 넣고, 3번은 빼낸다.

(위의 과정을 계속해서 반복한다 / front 원소와 인접한(아직 방문하지 않은) 노드를 모두 큐에 넣고, front 원소를 추출한다.)

 

위의 과정에서 노드들의 방문순서는 다음과 같다.

 

방문순서 : 1->2->3->8->7->4->5->6

 

 

너비 우선 탐색 알고리즘은 큐(Queue) 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현 할 땐 C++의 큐 STL을 사용하면 좋으며, 탐색을 수행함에 O(N)의 시간이 소요된다. 일반적인 경우, DFS보다 실제 수행시간이 빠른 편이다.

 

 

너비 우선 탐색 알고리즘 구현하기

1. 연결리스트로 노드, 큐 정의

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 99999999
#define MAX_SIZE 1001

typdef struct {
    int index;
    struct Node *next;
} Node;

typdef struct {
    Node *front;
    Node *rear;
    int count;
    int count;
} Queue;

Node** a;
int n, m, c[MAX_SIZE];

2. 연결 리스트 삽입 함수

void addFront(Node *root, int index){ //root 노드 다음에 새 노드를 삽입하는 함수
    Node *node = (*Node)malloc(sizeof(Node));
    node->index = index;
    node->next = root->next;
    root->next = node;   
}

3. 큐 삽입 함수

void queuePush(Queue *queue, int index){
    Node *node = (*Node)malloc(sizeof(Node));
    node->index = index;
    node->next = NULL;
    if(queue->count == 0){ //현재 큐가 비어있다면 front에 연결
        queue->front = node;
    }
    else{ //그 외엔 꼬리부분에 연결
        queue->rear->next = node;
    }
    queue->rear = node; //새 노드를 마지막 노드로 지정
    queue->count++;
}

 

4. 큐 추출 함수

int queuePop(Queue *queue){
    if(queue->count == 0){
        printf("큐 언더플로우가 발생했습니다.\n");
        return -INF;
    }
    Node *node = queue->front;
    int index = node->index;
    queue->front = node->next;
    free(node);
    queue->count--;
    return index;
}

5. 너비 우선 탐색 함수

void bfs(int start){ //특정 위치에서 탐색 시작
    Queue q;
    q.front = q.rear = NILL; //초기화
    q.count = 0;
    queuePush(&q, start);
    c[start] = 1; //시작노드 방문처리
    while (q.count != 0){//큐가 빌때까지 반복
        int x = queuePop(&q); //기준이 되는 노드 큐에서 추출
        printf("%d " , x); //방문순서가 남도록 기준 노드를 출력
        Node *cur = a[x]->next; //기존노드에 인접한 노드로 이동
        while (cur != NULL){ //인접한 노드가 없을 때까지 반복
            int next = cur->index;
            if(!c[next]){ //해당 노드에 인접한 노드가 있을경우
                queuePush(&q, next); //해당 노드 큐에 삽입
                c[next] = 1; //해당 노드 방문처리
            }
            cur = cur->next; //다음 인접한 노드로 이동
        }
    }
}

 

6. 너비 우선 탐색 알고리즘 사용하기

int main(void){
    scanf("%d %d", &n, &m); //정점갯수 n, 간선갯수 m 입력 받음
    a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE)); //각 노드당 최대 1천개씩 연결될 수 있음
    for(int i = 1; i <= n; i++){ //정점 n개 생성 및 초기화
        a[i] = (Node*)malloc(sizeof(Node));
        a[i]->next = NULL;
    }
    for(int i = 0; i < m; i++){ //연결된 정점 정보 입력받기(간선의 갯수 만큼 반복)
        int x, y;
        scanf("%d %d", &x, &y);
        addFront(a[x], y);
        addFront(a[y], x);
    }
    bfs(1);
    system("pause");
    return 0;
}

 

요약

 

너비 우선 탐색은 O(N)의 시간이 소요되는 전수 탐색 알고리즘이며, 실제적으론 dfs보다 탐색속도가 빠른편이다.

+ 큐를 이용해 구현한다는 점에서, bfs가 dfs보단 까다로울 순 있으나 시간이 더 절약 된다.