C로 만드는 자료구조 - 그래프 탐색과 깊이 우선탐색

그래프 탐색(Search 혹은 Traversal)

 그래프의 탐색은 간선을 이용하여 그래프 상의 모든 노드를 한 번씩 방문하는 것을 말한다. 예를 들어 한 도시를 기점으로 모든 도시를 방문하고자 한다면 우리는 어떤 순서로 방문해야 모든 도시를 방문할 수 있을까? 

이를 해결하기 위한 그패트의 탐색 방법으로 가장 대표적이고 기초적인 2가지 방법이 있다.

1) 깊이-우선 탐색(DFS: Depth-First Search)

2) 넓이-우선 탐색(BFS: Breadth-First Search)

 깊이 우선 탐색은 현재 방문한 노드와 인접한 노드를 우선이 하는 탐색 방법이고 넓이 우선 탐색은 현재 방문한 노드보다 우선적으로 이전 노드에서 방문하지 않고 인접한 노드를 우선 탐색한다.

아래 그림을 통해 간단히 설명해보자.

위 그림에서 '1' 노드에서 시작하여  현재 방문 노드가 '2'라고 해보자 여기서 깊이 우선 탐색이라면 현재 방문 노드를 우선시하기 때문에 3을 방문할 것이고 넓이 우선 탐색이라면 이전 노드를 우선시하기 때문에 '0'을 방문할 것이다.

깊이-우선 탐색

깊이 우선 탐색은 현재 방문한 노드와 인접하고 아직 탐색되지 않은 노드를 방문하는 탐색 방법이다. 이를 어떻게 구현할까? 가장 간단한 방법은 재귀 호출에 의한 방법이다. 아래는 의사코드로 나타낸 깊이 우선 탐색이다.

DFS(node v){
     v (방문 처리);
     for( all u (v의 인접 노드들))
          if ( u != 방문)
                 DFS(u)
     }
}

스택으로 구현하는 깊이-우선 탐색

위에서 다룬 재귀 호출은 매우 직관적이고 간단한 방법이지만 재귀 호출 함수들의 특성상 과부하가 걸릴 가능성도 크다.
이때 비재귀적으로 스택을 이용해 구현하는 방법도 있다.

우리는 현재 방문한 노드에서 인접한 노드를 찾는 깊이 우선 탐색 방식에서 스택의 '후입 선출' 특성을 충분히 사용할 수 있다. 우리는 방문한 노드에서 인접한 노드들을 스택에 푸시할 거고 스택의 후입 선출 특성으로 인해 가장 마지막에 추가된 노드 즉 현재 방문 중인 노드 위주로 탐색을 할 것이다. 이를 의사 코드로 나타내면 다음과 같다.

DFS(node v){
     스택 S
     v (방문 처리);
     S.push(v)
     while(! is_Empty(S))
          u=S.pop()
          for( all w (u의 인접 노드들)){
               if ( w != 방문){
                   S.push(w)
                   w (방문처리)
               }
         }
     }
}

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

가장 먼저 '0' 노드를 방문한다고 가정하자 방문 여부 확인 배열에서 '0'을 방문했다고 값을 변경해주고 (방문 시 1, 방문 안 한 노드일 시 0) 스택에는 인접한 노드인 '1', '2'를 추가해준다. 여기서 스택에 들어간 노드는 이미 방문 처리된 것과 같기 때문에 '1', '2'에 방문 여부 확인 값을 바꿔주어야 한다. 스택이기 때문에 다음 방문 노드는 '1'이 될 것이다.

'1'에 방문 후에도 마찬가지로 방문 여부 값을 바꿔주고 스택에 인접하고 아직 방문하지 않은 노드 '3', '4'를 추가하고 방문 처리를 해준다.

'3'과 방문한 적 없고 인접한 노드는 '6'이 유일하다. 다음 방문 노드는 '6'이 된다.

'6' 노드와는 방문한적 없고 인접한 노드가 없으므로 스택에 추가할 노드는 없다. 다음 방문 노드는 기존 스택에서 가장 늦게 들어간 '4'가 된다.

노드 '2'는 이미 방문한 노드로 처리되어 있기 때문에 노드 '4'에서도 스택에 추가할 노드는 존재하지 않는다.

 노드 '2'에서는 아직 방문하지 않은 노드 '5'가 존재하므로 스택에 추가해준다.

 더 이상 추가할 노드가 존재하지 않고 스택이 비어있으므로 알고리즘은 종료된다. 이때 모든 노드를 방문했음을 알 수 있고 방문 순서는 0-1-3-6-4-2-5 가 된다.

코드로 구현

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

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

1. graphtraversalDFS.h

void traversalDFS(LinkedGraph* pGraph, int startVertexID);

2. graphtraversalDFS.cpp

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

int pushLSForDFS(LinkedStack* pStack, int nodeID)
{
    StackNode node = {0,};
    node.data = nodeID;
    return pushLS(pStack, node);
}

void traversalDFS(LinkedGraph* pGraph, int startVertexID){
    int i = 0, vertextID = 0;
    LinkedStack *pStack = NULL;
    StackNode *pStackNode = NULL;
    ListNode *pListNode = NULL;
    int *pVisited = NULL;
    if (pGraph == NULL) return;
    pStack = createLinkedStack();
    if (pStack == NULL) return;
    pVisited = (int *)malloc(sizeof(int) * getMaxVertexCountLG(pGraph));
    if (pVisited == NULL) return;
    memset(pVisited, FALSE, sizeof(int) * getMaxVertexCountLG(pGraph));

    pVisited[startVertexID] = TRUE;
    pushLSForDFS(pStack, startVertexID);

    while(isLinkedStackEmpty(pStack) == FALSE){
        pStackNode = popLS(pStack);
        if (pStackNode == NULL) break;
        vertextID = pStackNode->data;
        printf("[%d\n] ", vertextID);
        pListNode = pGraph->ppAdjEdge[vertextID]->headerNode.pLink;
        while(pListNode != NULL){
            int vertexID = pListNode->data.vertexID;
            if (pVisited[vertexID] == FALSE){
                pVisited[vertexID]= TRUE;
                pushLSForDFS(pStack, vertexID);
            }
            pListNode = pListNode->pLink;
        }
    }
    printf("\n");
    free(pVisited);
    deleteLinkedStack(pStack);
}

실행 결과