[자료구조] 깊이 우선 탐색(DFS)

깊이 우선 탐색(DFS=Depth First Search)

기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용합니다.  깊이 우선 탐색은 스택(Stack) 자료구조에 기초합니다. 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 

2. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 

3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복합니다. 

 

스택에 노드1을 넣고, 노드 1과 연결된 노드 2를 넣는다. 계속해서 연결되어 있으면 순서대로 노드를 넣는다. 노드 7을 넣고 더이상 연결되어 있지 않으므로 pop하여 꺼낸다. 스택에 노드 1만 남았을 때로 돌아와서 노드 1과 연결된 노드 3, 4를 차례대로 넣는다. 이후 차례대로 pop하여 원소를 꺼낸다. 

 

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1001

typeder struct{
      int index;
      struct Node *next;
} Node;

Node** a;
int n, m, c[MAX_SIZE]; //배열 c는 연결관계를 나타내는 배열

void addFront(Node *root, int index, int distance){
      Node *node = (Node*)malloc(sizeof(Node));
      node->index = index;
      node->distance = distance;
      node->next = root->next;
      root->next = node;
}

void dfs(int x){
      if(c[x]) return;  //해당 노드를 방문했으면 빠져나온다
      c[x] = 1; 		  //방문했다.
      printf("%d ", x); //방문한 노드를 출력
      Node *cur = a[x]->next;
      while(cur!=NULL){
          int next = cur->index;
          dfs(next);    //재귀적으로 방문하지 않은 노드를 탐색
          cur = cur->next;
      }
}
int main(void){
scanf("%d %d", &n, &m);
a = (Node**)malloc(sizeof(Node*) * (MAX_SIZE));
for(int i=1; i<=n; i++){
      a[i]= (Node*)malloc(sizeof(Node));
      a[i]->next = NULL;
      }
      for(int i=0; i<m; i++){
          int x, y;
          scanf("%d %d", &x, &y);
          addFront(a[x], y);
          addFront(a[y], x);
      }
      dfs(1);
      return 0;
}