[Algorithm] 깊이 우선 탐색(DFS, Depth First Search)

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

특정 Data를 탐색할 때 깊이가 깊은 것을 우선적으로 탐색하는 알고리즘으로 Stack 자료구조를 사용

사실 Stack을 사용하지 않아도 구현이 가능한데, 이는 컴퓨터가 구조적으로 항상 Stack의 원리를 사용하기 때문이다.

 

깊이 우선 탐색(DFS) Sequence

Step 1: 시작 Node를 Stack에 넣고 방문 처리

Step 2: Stack의 최상단 Node 확인

Step 3: 최상단 Node에 방문하지 않은 인접 Node가 있다면 그 Node를 Stack에 넣고 방문 처리

           ☞ 방문하지 않은 인접 Node가 없으면 Stack에서 최상단 Node 삭제

Step 4: Step 2로 이동

 

Code

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

#define MAX 7
int visited[7];
vector <int> a[8];

void dfs(int x){
    // 이미 방문한 적 있으면 return
    if(visited[x]) return;

    // 방문 처리
    visited[x] = true;
    cout << 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[1].push_back(3);

    a[2].push_back(1);
    a[2].push_back(3);
    a[2].push_back(4);
    a[2].push_back(5);

    a[3].push_back(1);
    a[3].push_back(2);
    a[3].push_back(6);
    a[3].push_back(7);

    a[4].push_back(2);
    a[4].push_back(5);

    a[5].push_back(2);
    a[5].push_back(4);

    a[6].push_back(3);
    a[6].push_back(7);

    a[7].push_back(3);
    a[7].push_back(6);

    dfs(1);
}

출력

1 2 3 6 7 4 5