너비 우선 탐색 (BFS, Breadth First Search)

---

너비 우선 탐색 (BFS, Breadth First Search)

** 아래 포스팅 내용 관련하여, 더 나은 방법이나 아이디어가 있으신 경우에는 댓글에 의견을 공유해주시면 감사하겠습니다.

** Source code는 C 언어로 작성되었습니다.

---

그래프 순회 (Traversal) 알고리즘 : 너비 우선 탐색 (BFS)

 그래프 순회 알고리즘이란, 그래프 상에 표시된 모든 지점 (node) 들을 방문해야 하는 경우 사용되는 알고리즘을 의미합니다. 요구 사항이나 그래프 형태, 각 노드의 가중치나 특성에 따라서 순회 알고리즘의 세부 구현 방식은 달라질 수 있습니다. 그러나 그래프 순회 알고리즘에서 공통적으로 가장 중요한 것은 한 번 방문한 node를 다시 방문하지 않도록 표시하는 것입니다. 이 부분이 잘못 처리될 경우 한 번 방문했던 node들을 다시 방문해야 하는 경우가 생기고, 최악의 경우 무한대로 탐색을 해 나가는 경우도 발생합니다.

 그래프 순회 알고리즘은 크게는 두가지로 나눌 수 있습니다. 너비 우선 탐색을 할 것인가, 깊이 우선 탐색을 할 것인가인데, 문제의 요구 사항에 따라서, 두 알고리즘이 모두 적합한 solution이 될 수 있는 경우가 있는가 하면, 반드시 둘 중 한가지의 알고리즘으로 해결해야 하는 경우도 있습니다. 두 방식의 차이는 단지 node를 방문하는 순서에 있습니다.

 이 포스팅에서는 두 방식 중 먼저 너비 우선 탐색 방식을 소개하려고 합니다. 너비 우선 방식은 깊이 우선 방식에 비해 주로 다음과 같은 경우에 활용됩니다.

1. Node 방문 순서가 상관이 없고,
2. Node별 가중치가 없는 경우
3. 특정 A 지점으로부터 B 지점까지의 거리, 또는 그래프를 전 탐색하는데 걸리는 최소 시간 등을 도출하고자 할 때
4. 너비 우선, 깊이 우선이라는 말 자체가 조금 생소할 수도 있는데, 아래 그림과 설명을 보시면 좀 더 이해하시기가 쉬울 것입니다.

너비 우선 탐색의 특징

 앞서 말씀드렸듯이 순회 알고리즘에서 가장 기본은 한 번 방문한 node를 다시 방문하지 않도록 표시하는 것입니다. 이를 위해서 방문 부를 표시하기 위한 방법을 마련해야 합니다.

 그리고 너비가 한 단계씩 확장될 때 마다 해당 노드의 위치 정보를 포함하기 위한 용도로 FIFO 자료 구조인 Queue가 활용됩니다. Queue의 종류는 어떤 것이든 관계가 없지만 Memory를 효율적으로 관리해야만 하는 환경이라면 Circular queue를 활용하면 되고, 그게 아니라면 보다 직관적인 linear queue를 사용하면 됩니다. 대신 buffer 크기는 전체 그래프의 node 수보다 많아야 된다는 점을 주의해야 합니다.

주의 사항 :

Queue buffer의 크기는 요구 사항에서 제시된 그래프의 최대 크기보다 항상 커야합니다.

예제

• 요구 사항 : 그래프의 1번 지점으로부터 8번 지점까지 최단 거리의 길이를 구해봅시다. 연결된 간선으로만 이동이 가능하며 간선의 길이는 1로 모두 동일하다고 가정합니다.

• 입력 데이터 그래프 : 편의상 위 예제의 입력을 다음과 같이 Hard-coding 하였습니다.

  
  

  // Test input
    u16 INPUT_BUF[MAX_NODE_NUM * MAX_NODE_NUM][2] =
    {
  
    {1, 2},
    {1, 4},
    {1, 6},
    {2, 3},
    {2, 4},
    {4, 5},
    {4, 7},
    {5, 8},
    {0, 0}
    };

• 풀이 

    - 시작점을 우선 queue에 담고 queue의 rear flag를 하나 증가시켜 줍니다.
    - 기본적으로 rear flag는 enqueue할 때마다 증가되고, front_flag는 dequeue할 때 증가됩니다.
    -  front flag가 지나간 이후에는 visit flag를 check해 줍니다.



    - 1번 노드와 거리 count 1만큼 떨어져 있는 모든 노드들을 검색하여 queue에 추가합니다.
    - input buffer에서 2번 node가 1번 node와 순서상 가장 먼저 연결되어 있으므로, 2번 node를 enqueue하고 read flag를 증가합니다.

    - 4, 6번 노드들도 똑같이 enqueue합니다.
    - 항상 visit flag는 방문시에 check되어야 합니다.

    - 1번에서 한 단계 거리에 있는 node들은 모두 방문처리가 되었기 때문에, 거리 count를 2로 증가시키고, front_flag를 이동합니다.
    - front flag는 해당 node에서 연결된 노드가 하나도 없거나, 연결된 노드 중 한 번도 방문하지 않은 노드가 더 이상 없을 때 증가됩니다. 



   
    - 5, 7번 노드가 Count 2에서 추가로 enqueue됩니다. 거리가 2만큼 떨어진 node들은 이제 모두 enqueue되었습니다.

 


    - 거리가 2만큼 떨어진 node들이 모두 검색되었으므로, count를 3으로 증가시킵니다.
    - 3번 노드는 연결된 node가 더 이상 없으므로, 5번 node로 이동하고, 5번 node에 연결된 8번 node는 아직 방문된 적이 없으므로     enqueue합니다.

    - 최종 결과는 아래와 같이 정리됩니다.

Source code

// -- BFS (Breadth First Search)


#include <stdio.h>

typedef unsigned int        (u32);
typedef unsigned short      (u16);

typedef unsigned char       (u8);

#define MAX_NODE_NUM        (100)

// Test input
u16 INPUT_BUF[MAX_NODE_NUM * MAX_NODE_NUM][2] =
{
    {1, 2},
    {1, 4},
    {1, 6},
    {2, 3},
    {2, 4},
    {4, 5},
    {4, 7},
    {5, 8},
    {0, 0}

};

// Definition for QUEUE
#define ENQUEUE(pos, val)    do { (QUEUE[pos] = val); } while(0)

#define DEQUEUE(pos)        (QUEUE[pos])

// -- Grobal variables
u8 VISIT[MAX_NODE_NUM];

u8 QUEUE[MAX_NODE_NUM];

u32 rear_flag;
u32 front_flag;

u32 min_length;

enum {
    NOT_VISITED = 0,
    VISITED = 1

};

// BFS main
void BFS( u32 front_flag )
{
    u32 i;

u32 curr_check_value = DEQUEUE(front_flag);

    for (i = 0; i < MAX_NODE_NUM * MAX_NODE_NUM; i++)
    {
        u32 current_value    = INPUT_BUF[i][0];

u32 connected_value = INPUT_BUF[i][1];

        if (current_value == 0)
        {
            break;
        }
        else if ((current_value == curr_check_value) &&
            (VISIT[connected_value] == NOT_VISITED))
        {
            VISIT[INPUT_BUF[i][1]] = VISITED;
            ENQUEUE(rear_flag++, INPUT_BUF[i][1]);
        }
    }

}

int main(void)
{

u32 boundary_for_next_step = 0;

    // Enqueue & visit the 1st node
    VISIT[front_flag] = VISITED;
    ENQUEUE(rear_flag++, 1);

boundary_for_next_step = rear_flag;

    // BFS
    do {

BFS(front_flag++);

        // Check the distance
        if (front_flag == boundary_for_next_step)
        {

boundary_for_next_step = rear_flag;

            if (rear_flag != front_flag)    min_length++;

}

}while (rear_flag > front_flag);

printf("Minimum length From 1 To 8: %d\n", min_length);

    return 0;
}

출처 / 관련 링크