깊이 우선 탐색(Depth First Search) - DFS에 대해 알아보자

블로그 https://blog.naver.com/ndb796/221230945092 와 https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/ 을 참고하였습니다.

1. DFS (Depth First Search) - 깊이 우선 탐색이란??

  - Stack을 사용하며 해당 노드에서 다음 노드로 넘어가기 전 완벽하게 탐색하는 알고리즘입니다.

  - 재귀함수를 사용하고, 넓게 탐색하기 전 깊에 탐색합니다.

2. DFS 의 과정

  ① 9개의 노드들이 존재합니다.

  ② 시작노드 1을 Stack에 삽입하며 시작합니다. 

  ③ 1의 노드 인접한 노드들을 차례로 순회하며 Stack에 넣고 방문처리합니다.

  ④ 더이상 노드 2의 인접노드는 없으므로 다시 1의 인접노드인 3의 노드를 방문합니다.

      노드 2에서 다시 부모노드로 돌아오는 과정을 백트래킹(backtracking)이라고 합니다.

  

⑤ 3의 인접노드인 노드 4,5 중 노드 4를 먼저 Stack에 넣습니다.

  ⑥ 노드 4의 인접 노드인 7,8,6의 노드들 중 노드 7을 먼저 Stack에 넣습니다.

  ⑦ 노드 7에서 더이상 방문할 노드가 없기 때문에 다시 노드4의 인접노드들 중 노드 8을 방문합니다.

 

  ⑧ 8의 인접노드인 노드 9를 방문합니다.

  ⑨ 마찬가지로 노드 9의 인접노드인 5를 방문합니다. 

  ⑩ 5의 노드에서 더이상 방문할 노드들이 없으므로 차례로 Stack에서 다 제외시킵니다.

  ⑪ 다시 노드 4의 인접한 노드 6을 Stack에 넣습니다.

  ⑫ 노드 6 방문 후 더이상 방문할 노드들이 없으므로 Stack에서 노드들이 다 빠져나오게 됩니다.

  ※ 처음 시작노드의 인접한 노드를 방문하고, 방문한 노드의 이웃 노드들을 전부 방문합니다.

     처음 시작노드의 인접한 노드의 이웃노드들을 완전 탐색한 후 다시 처음 시작노드의 또 다른 인접노드를 찾습니다.

     또 다른 인접노드가 존재한다면 다시 인접 노드의 이웃 노드들을 완전 탐색하고 존재하지 않는다면 종료합니다.

3. DFS 의 구현

 #include<iostream>
 #include<vector>
 
 using namespace std;
 
 int number=9; // 노드의 개수 
 int c[10]; // 방문처리를 위한 배열 
 vector<int> a[10];
 
 void dfs(int x) {
     if(c[x]) {  // 방문처리된 노드라면 종료합니다. 
         return;
     }
     c[x] = true; // 방문처리  
     printf("%d ", x);
     for(int i=0; i<a[x].size(); i++) {
         int y = a[x][i];
         dfs(y); // 재귀로 인접한 노드들을 방문합니다. 
     }
 } 
 
 int main(void) {
     a[1].push_back(2);
     a[2].push_back(1);
     
     a[1].push_back(3);
     a[3].push_back(1);
     
     a[3].push_back(4);
     a[4].push_back(3);
     
     a[3].push_back(5);
     a[5].push_back(3);
     
     a[4].push_back(7);
     a[7].push_back(4);
     
     a[4].push_back(8);
     a[8].push_back(4);
     
     a[4].push_back(6);
     a[6].push_back(4);
     
     a[8].push_back(9);
     a[9].push_back(8);     
     
     a[5].push_back(9);
     a[9].push_back(5);
     dfs(1);
 }

  ▶ 결과화면