깊이 우선 탐색(Depth First Search)

개요

깊이 우선 탐색은 너비를 우선으로 했던 너비 우선 탐색과 달리 깊이를 우선적으로 수행하는 탐색 알고리즘이다. 너비 우선 탐색과 달리 스택(stack)을 사용한다는 특징이 있지만, 사용하지 않고 구현할 수도 있다.

깊이 우선 탐색

깊이 우선 탐색은 스택의 최상단에 위치한 노드와 연결된 노드 중 스택에 삽입되지 않은 노드를 스택에 삽입한다. 이후 마지막에 삽입된 노드가 스택의 최상단에 위치하기에 위 방식을 반복할수록 더욱 깊이 들어가게 된다. 따라서 이를 깊이 우선 탐색이라 하며, 마지막에 삽입된 데이터부터 처리하는 스택 구조가 적합하다고 할 수 있다.

수행 과정

1. 시작 노드를 빈 스택에 삽입한다.
2. 스택의 최상단에 위치한 시작 노드와 연결된 노드 중 스택에 존재하지 않는 노드를 순서대로 삽입한다.
3. 새로 갱신된 스택의 최상단에 위치한 노드를 기준으로 모든 노드에 대해 위 과정을 반복한다.

코드 구현

#include <iostream>
#include <stack>
#include <vector>

int main(){
    std::stack<int> s;
    int start_node{1};
    bool v[8], pass;
    std::vector<int> a[8];

    a[1].emplace_back(2);
    a[2].emplace_back(1);
    a[1].emplace_back(3);
    a[3].emplace_back(1);
    a[2].emplace_back(3);
    a[3].emplace_back(2);
    a[2].emplace_back(4);
    a[4].emplace_back(2);
    a[2].emplace_back(5);
    a[5].emplace_back(2);
    a[3].emplace_back(6);
    a[6].emplace_back(3);
    a[3].emplace_back(7);
    a[7].emplace_back(3);
    a[4].emplace_back(5);
    a[5].emplace_back(4);
    a[6].emplace_back(7);
    a[7].emplace_back(6);

    s.push(start_node);
    v[start_node] = true;
    std::cout<<s.top()<<' ';
    while (!s.empty()){
        pass = true;
        int top = s.top();
        for (int i=0;i<a[top].size();i++){
            if (!v[a[top][i]]) {
                s.push(a[top][i]);
                std::cout<<a[top][i]<<' ';
                v[a[top][i]] = true;
                pass = false;
            }
        }
        if (pass) s.pop();
    }

    return 0;
}
//1 2 3 6 7 4 5

Reference

https://m.blog.naver.com/ndb796/221230945092