[알고리즘] 깊이 우선 탐색(Depth First Search)

 

 

 

 

 

알고리즘 개요 및 소개

DFS

깊이 우선 탐색(Depth First Search, BFS)은 *맹목적 탐색방법의 하나이다. 그래프에 여러 갈래의 길이 있는데 DFS, 의 이름이 의미하듯이 한 길을 깊이 파고드는 것이다.

 

*맹목적 탐색: 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법

시간 복잡도	O(|V|+|E|)) V: 정점의 수 E: 간선의 수
장점	- 목표 노드가 깊은 단계에 있을 경우 답을 빨리 구할 수 있다. - 저장공간이 적게 든다.
단점	- 답이 없는 경로에 깊이 빠질 가능성이 있다. 미리 지정한 깊이만큼만 탐색하고 답이 없다면 다른 경로를 탐색하는 방법이 유용하다. - 얻은 답이 최단 경로라는 보장이 없다.

 

 

탐색 과정

깊이 우선 탐색의 알고리즘은 다음과 같다.

1. Stack 가장 상단 노드에 방문하지 않은 노드가 있으면 Push
2. 방문하지 않은 노드가 없으면 pop
3. 위 순서를 반복

초기 상태

1번 노드를 맨 처음 방문한다는 가정하에 시작을 하면 Stack에 1을 Push 한다.

 

2번 노드를 방문

2번 노드를 Stack에 Push 후 방문하지 않은 인접 노드들(4,5)을 Stack에 Push 한다.

4,5 노드를 Stack에 Push

 더 이상 방문할 수 있는 인접 노드가 없기 때문에 Stack에서 데이터를 pop 한다.

3노드를 방문 후 push

1번 노드에 아직 방문하지 않은 3번 노드가 있기 때문에 3번 노드를 push 한다.

 

인접 노드인 6,7 노드를 방문

아직 방문하지 않는 노드들(6,7)을 방문 후 Stack에 Push 한다. 이후 인접한 노드들 중에 방문하지 않은 노드가 없기 때문에 모든 노드가 Stack에서 pop 후 종료된다.

소스코드

#include<iostream>
#include<queue>
#include<vector>
 
constexpr int MAX = 8;
 
class Graph {
private:
    std::vector<int> node_[MAX];
    bool is_visited_[MAX];
public:
    Graph() {
        for (int i = 0; i < MAX; ++i)
            is_visited_[i] = false;
    };
    void InitNode() {
        //1번 노드에 2,3을 넣음
        node_[1].emplace_back(2);
        node_[1].emplace_back(3);
        //2번 노드에 1,4,5을 넣음
        node_[2].emplace_back(1);
        node_[2].emplace_back(4);
        node_[2].emplace_back(5);
        //3번 노드에 1,6,7을 넣음
        node_[3].emplace_back(1);
        node_[3].emplace_back(6);
        node_[3].emplace_back(7);
        //4번 노드에 2,5을 넣음
        node_[4].emplace_back(2);
        node_[4].emplace_back(5);
        //5번 노드에 2,4를 넣음
        node_[5].emplace_back(2);
        node_[5].emplace_back(4);
        //6번 노드에 3,7을 넣음
        node_[6].emplace_back(3);
        node_[6].emplace_back(7);
        //7번 노드에 3,6을 넣음
        node_[7].emplace_back(3);
        node_[7].emplace_back(6);
    }
    void BFS(int started) {
        std::queue<int> q;
        q.push(started);
        is_visited_[started] = true;
 
        while (q.empty() == false) {
        
            int curr = q.front();
            q.pop();
            std::cout << curr << " ";
            for (int i = 0; i<node_[curr].size(); ++i) {
                int node = node_[curr][i];
 
                if (is_visited_[node] == false) {
                    q.push(node_[curr][i]);
                    is_visited_[node] = true;
                }
            }
        }
 
    }
    void DFS(int started) {
        //방문한 노드는 True
        if (is_visited_[started] == false) {
            is_visited_[started] = true;
            std::cout << started << " ";
        }
        for (int i = 0; i < node_[started].size(); ++i) {
            int node = node_[started][i];
            if (is_visited_[node] == false) {
                DFS(node);
            }    
        }
        return;
    }
 
};
 
int main() {
    Graph g;
    g.InitNode();
    g.DFS(1);
}

 

 

후기

DFS 결과

너비 우선 탐색(Breadth First Search)에 이어서 두 번째 탐색 방식 DFS를 구현해보았다.  자료구조 Stack을tack] 간단한 Stack 구현을 사용하거나 재귀 함수를 사용해서 구현할 수 있다. 여기서는 후자로 구현을 하였다.

둘 중 하나의 방식에 익숙해진다면 나머지 하나의 방식은 크게 어렵지 않다.

 

 

출처 및 레퍼런스

Wiki: https://ko.wikipedia.org/wiki/깊이_우선_탐색

Book: 열혈 자료구조

그림: 본인

 

관련글

너비 우선 탐색(Breadth First Search)

그래프(Graph)

간단한 Stack 구현

 

 

20.04.21 

코드-> Color Scripter, 폰트 및 색상 변경