Graph BFS

이전 포스트에서 DFS를 다뤘으므로 이번에는 같은 방식으로 BFS를 어떻게 구현하는지에 대해 알아보도록 하자.

 

그래프

 

그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한 것을 말한다.

그래프 탐색은 하나의 정점(Vertex)으로부터 시작하여 차례대로 연결된 간선(Edge)를 통해 연결되어있는지 갈 수 있는지를 탐색하는 방법이다.

 

그래프 탐색에는 DFS와 BFS가 있는데 이번 포스트에서는 DFS 에 대해 알아보도록 하자.

BFS란?

 

Breadth-First Search (너비 우선 탐색) 은 노드를 넓게 탐색하는 것을 말한다.

 

DFS는 한쪽 길을 끝날때 까지 다 파고 그 다음길을 판다면, BFS는 넓은 길로 파는 형식을 말하는 것이다. 인접한 노드를 하나하나 밟으면서 가는 방식이 BFS의 특징이다.

 

최단거리 길찾기에서 주로 쓰이게 된다.

 

BFS는 재귀를 사용하지 않지만, 방문했는지의 여부는 체크해야 하며 먼저 들어온 노드의 인접한 노드가 있는지 훑어본 후 없다면 방문했다고 체크한 후 그 다음 노드를 체크하는 형식의 선입선출 원칙으로 탐색된다.

 

즉, Queue를 사용하는 것이 BFS의 특징이다.

 

BFS 구현

 

위와 같이 0에서 시작을 한다면 가장 인접한 1번과 3번을 예약해두고, 그 중 1번을 먼저 탐색한다면 인접한 2번을 예약 후 더 없다면 1번체크, 예약된 3번에서 인접한 4번을 예약하고 3번을 체크 이런식으로 진행된다.

 

1. Graph

그래프는 2차원 배열로 그래프를 구현해봤다.

 

class BFSGraph
{
    // version 1
    int[,] adj = new int[6, 6]
    {
        { 0, 1, 0 ,1 ,0 ,0},
        { 1, 0, 1 ,1 ,0 ,0},
        { 0, 1, 0 ,0 ,0 ,0},
        { 1, 1, 0 ,0 ,1 ,0},
        { 0, 0, 0 ,1 ,0 ,1},
        { 0, 0, 0 ,0 ,1 ,0}
    };
}

 

 

2. BFS

public void BFS(int start)
{
    bool[] found = new bool[6];

    Queue<int> q = new Queue<int>();
    q.Enqueue(start);
    found[start] = true;

    while(q.Count > 0)
    {
        int now = q.Dequeue();
        Console.WriteLine(now);

        for(int next = 0; next < 6; next++)
        {
            if (adj[now, next] == 0) // 인접하지 않을 경우 스킵
                continue;
            if (found[next]) // 이미 발견되었을 경우 스킵
                continue;

            q.Enqueue(next);
            found[next] = true;
        }
    }
}

 

BFS는 위와 같이 구현된다. 방문 체크를 할 bool값의 배열, 그리고 Queue를 선언하고 q안의 예약된 노드들이 다 나갈때 까지 반복시킨다.

 

예약된 노드는 바로 Dequeue해주면서 인접한 노드가 있는지 개수만큼 반복을 해준다.

 

예를 들어 0이 Start로 들어간다면 인접한 노드가 1과 3이기 때문에 for문에서 체크하다보면 2차원 배열에 1이라고 되어있는 1과 3이 각각 Enqueue가 되어 예약이 되고, 방문 체크를 하면서 노드를 BFS방식으로 하나하나 체크해나가게 된다.

 

 

그래서 값을 보면 012345 이렇게가 아닌 0 1 3 2 4 5 이렇게 뻗어나가는 형식인 걸 알 수 있다.

 

3. 부모 노드와 거리 출력

 

 public void BFS(int start)
 {
     bool[] found = new bool[6];
     int[] parent = new int[6];
     int[] distance = new int[6];

     Queue<int> q = new Queue<int>();
     q.Enqueue(start);
     found[start] = true;
     parent[start] = start;
     distance[start] = 0;

     while(q.Count > 0)
     {
         int now = q.Dequeue();
         Console.WriteLine(now);

         for(int next = 0; next < 6; next++)
         {
             if (adj[now, next] == 0) // 인접하지 않을 경우 스킵
                 continue;
             if (found[next]) // 이미 발견되었을 경우 스킵
                 continue;

             q.Enqueue(next);
             found[next] = true;
             parent[next] = now;
             distance[next] = distance[now] + 1;
         }
     }
 }

 

 

위와 같이 거리의 경우 현재(now)노드에서 + 1을 해준다면 해당 거리가 나오며, 부모 노드의 경우는 현재(now)노드를 출력해주면 부모인지 알 수 있다.