C로 만드는 자료구조 - 넓이 우선 탐색

넓이-우선 탐색

 넓이 우선 탐색은 현재 방문한 노드 이전 노드에 인접한 노드를 우선적으로 방문하는 탐색 알고리즘이다. 

큐로 구현하는 넓이-우선 탐색

넓이 우선 탐색은 이전 노드를 기록을 가지고 있어야 하기 때문에 재귀적으로 동작하지 않는다. 우리는 넓이 우선 탐색을 구현하기 위해서 큐의 '선입선출' 특성을 이용할 것이다.

우리는 방문한 노드와 인접한 노드들을 큐에 추가할 것이고 큐는 '선입선출' 특성을 가지기 때문에 현재 노드와 인접한 노드보다 이전 노드와 인접한 노드들을 먼저 반환할 것이다. 아래는 큐를 이용한 BFS의 의사 코드이다.

BFS(node v){
     큐 Q
     v (방문 처리);
     Q.enqueue(V)
     while(! is_Empty(Q))
          u=Q.dequeue()
          for( all w (u의 인접 노드들)){
               if ( w!= 방문){
                   Q.enqueue(w)
                   w (방문처리)
               }
         }
     }
}

아래 그림을 통해 순차적으로 설명해보겠다.

노드 '0'에서 시작하며 인접하고 방문하지 않은 노드인 '1', '2'를 차례대로 큐에 추가해주고 방문 처리를 해준다. 큐를 사용하기 때문에 다음 방문 노드는 '1'이 된다.

마찬가지로 노드'1'가 인접하고 방문하지 않은 노드를 큐에 추가한다. 이때 다음 방문 노드는 깊이 우선 탐색에서는 3 또는 4가 되었겠지만 넓이 우선 탐색에서는 노드'2'가 다음 방문 노드가 된다.

노드 '2'에서는 노드'4'는 인접해 있지만 이미 방문한 노드로 처리되어 있기 때문에 노드'5'만 큐에 추가할 수 있다. 다음 방문 노드는 '3'이 된다.

노드'3'에서는 방문하지 않았고 인접한 노드인 '6'을 큐에 추가한다. 다음 방문 노드는 '4'가 된다.

노드 '4'에서는 큐에 추가할 노드가 없다. 다음 방문 노드는 '5'가 된다.

노드 '5' 또한 큐에 추가할 노드는 없다. 다음 방문 노드는 '6'이 된다.

노드'6'에서도 큐에 추가할 노드는 없다. 또한 큐에 더 이상 노드가 존재하지 않으므로 알고리즘은 종료된다. 알고리즘 종료 시 모든 노드를 탐색했음을 알 수 있고 방문 순서는 0-1-2-3-4-5-6 이 된다.

코드로 구현

깊이 우선 탐색을 구현하기 위해서 우리는 앞서 다뤘던 여러 자료구조를 사용할 것이다.

먼저 연결 리스트로 구현하는 그래프와 연결 리스트로 구현한 스택을 다시 활용할 것이다. 여기서는 오직 깊이 우선 탐색 관련 코드만 적어두었다.

1. graphtraversalBFS.h

void traversalBFS(Graph* pGraph, int startVertexID);

2. graphtraversalBFS.cpp

#include "graphlinkedlist.h"
#include "linkedgraph.h"
#include "linkedqueue.h"
#include "graphtraversal.h"

int enqueueLQForBFS(Queue *pQueue, int nodeID) {
    QueueNode node = {0,};
    node.data = nodeID;
    return enqueue(pQueue, node);
}

void traversalBFS(Graph *pGraph, int startVertexID) {
    Queue *pQueue = NULL;
    QueueNode *pQueueNode = NULL;
    ListNode *pListNode = NULL;
    int *pVisited;
    if (pGraph == NULL) return;
    if (checkVertexValid(pGraph, startVertexID) == FALSE) return;
    pVisited = (int *) malloc(sizeof(int) * pGraph->maxVertexCount);
    if (pVisited == NULL) return;
    memset(pVisited, FALSE, sizeof(int) * pGraph->maxVertexCount);
    pQueue = createQueue();
    pVisited[startVertexID] = TRUE;
    enqueueLQForBFS(pQueue, startVertexID);

    while (pQueue->currentElementCount > 0) {
        pQueueNode = dequeue(pQueue);
        printf("[%d] ", pQueueNode->data);
        pListNode = pGraph->ppEdge[pQueueNode->data]->headerNode.pLink;
        while (pListNode != NULL) {
            if (pVisited[pListNode->data.vertexID] == FALSE) {
                pVisited[pListNode->data.vertexID] = TRUE;
                enqueueLQForBFS(pQueue, pListNode->data.vertexID);
            }
            pListNode = pListNode->pLink;
        }
    }

    free(pVisited);
    deleteQueue(pQueue);
}

실행 결과