그래프 깊이 우선 탐색(DFS)의 개념과 C++ 구현 방법

깊이 우선 탐색(Depth First Search, DFS)은 그래프를 순회하는 대표적인 알고리즘입니다. 시작 정점이 하나 주어지면, 인접한 정점을 발견하는 즉시 그 정점으로 먼저 이동한 뒤 같은 방식으로 계속해서 탐색을 진행합니다.

DFS는 갈 수 있는 곳까지 최대한 깊이 들어간 후, 더 이상 진행할 수 없게 되면 이전 정점들로 되돌아가는 백트래킹(backtracking) 과정을 통해 아직 탐색하지 않은 새로운 경로를 찾아냅니다.

DFS를 반복문(iterative) 방식으로 구현하려면 스택(stack) 자료구조가 반드시 필요합니다. 반면 재귀(recursive) 방식으로 구현할 경우에는 별도의 외부 스택이 필요 없으며, 재귀 호출 시 시스템이 내부적으로 관리하는 콜 스택을 활용하게 됩니다.

입력: 그래프의 인접 행렬(Adjacency Matrix)

  A B C D E F
A 0 1 1 1 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0

출력: DFS 순회 결과: C F E B D A

알고리즘

dfs(vertices, start)

입력 − 그래프의 모든 정점 목록과 시작 노드

출력 − 그래프의 모든 노드를 순회

Begin
   처음에 모든 노드의 상태를 '방문하지 않음'으로 설정
   시작 노드를 스택에 push
   스택이 비어 있지 않은 동안 반복:
      스택에서 요소를 pop하여 u에 저장
      노드 u를 출력
      만약 u를 아직 방문하지 않았다면:
         u를 방문 처리
         u에 연결된 모든 노드 i에 대해:
            i번째 정점을 아직 방문하지 않았다면:
               i번째 정점을 스택에 push
               i번째 정점을 방문 처리
            종료
   종료
End

예제 코드

#include<iostream>
#include<stack>
using namespace std;
#define NODE 6
typedef struct node{
   int val;
   int state; //상태
}node;
int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0, 0},
   {1, 0, 0, 1, 1, 0},
   {1, 0, 0, 1, 0, 1},
   {1, 1, 1, 0, 1, 1},
   {0, 1, 0, 1, 0, 1},
   {0, 0, 1, 1, 1, 0}
};
void dfs(node *vertex, node start){
   node u;
   stack<node> myStack;
   for(int i = 0; i<NODE; i++){
      vertex[i].state = 0;//방문하지 않음
      }
   myStack.push(start);
      while(!myStack.empty()){
         //노드를 pop하고 출력
         u = myStack.top();
         myStack.pop();
         cout << char(u.val+'A') << " ";
         if(u.state != 1){
            //정점 상태를 방문으로 갱신
            u.state = 1;
            vertex[u.val].state = 1;
            for(int i = 0; i<NODE; i++){
            if(graph[i][u.val]){
               if(vertex[i].state == 0){
                  myStack.push(vertex[i]);
                  vertex[i].state = 1;
               }  
            }
         }
      }
   }
}
int main(){
   node vertices[NODE];
   node start;
   char s;
   for(int i = 0; i<NODE; i++){
      vertices[i].val = i;
   }
   s = 'C';//시작 정점 C
   start.val = s-'A';
   cout << "DFS Traversal: ";
   dfs(vertices, start);
   cout << endl;
}

실행 결과

DFS Traversal: C F E B D A