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

그래프 탐색이란?
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.

이때, 어떤 탐색 알고리즘을 쓰는지에 따라 방문하는 방식이 달라진다.

 

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

시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 그리고 더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방식을 백트래킹(Backtracking) 이라고 한다.

다음은 깊이 우선 탐색을 표현한 애니메이션이다.

깊이 우선 탐색

애니메이션에서 연한 녹색으로 칠해지는것이 정점을 방문하는 절차이고, 진한 녹색으로 칠해지는것이 더 방문할 정점이 있는지 탐색하는 백트래킹 과정이다.

트리구조에서 전위순환, 중위순환, 후위순환이 이 깊이 우선 탐색을 활용한 순회방법에 해당한다.

깊이 우선 탐색의 장단점은 다음과 같다.

DFS의 장점:

1. DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
2. DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
3. DFS를 사용하여 그래프에서 순환을 감지할 수 있다.

DFS의 단점:

1. 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
2. DFS는 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.

DFS는 특정 시나리오에서 매우 유용할 수 있지만 항상 최선의 선택은 아니다. 해결하려는 특정 문제에 따라 BFS(Breadth-first Search)와 같은 다른 알고리즘이 더 적합할 수 있다.

---

다음은 실제로 깊이 우선 탐색을 구현해보자. DFS를 구현하는 방식은 스택을 사용하여 구현한다. 스택은 후입선출 속성을 가지고 있기 때문에 현재 저점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용하기에 적합한 자료 구조이다.

구현에 사용할 그래프는 다음과 같다.

다음 그래프를 DFS 방식으로 순환해보자.

#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <vector>

using namespace std;

template <typename T>
struct Edge {
    unsigned src;
    unsigned dst;
    T weight;
};

template <typename T>
class Graph {
    public:
        Graph(unsigned N) : V(N) {}

        auto verties() const {
            return V;
        }

        auto& edge() const {
            return edge_list;
        }

        auto edges(unsigned v) const {
            vector<Edge<T>> edges_from_v;
            for (auto& e : edge_list) {
                if (e.src == v) edges_from_v.emplace_back(e);
            }

            return edges_from_v;
        }

        void add_edge(Edge<T>&& e) {
            if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
                edge_list.emplace_back(e);
            else
                cerr << "에러 : 유효 범위를 벗어난 정점!" << endl;
        }

        template <typename U>
        friend ostream& operator<< (ostream& os, const Graph<U>& G);

        private:
            unsigned V;
            vector<Edge<T>> edge_list;
};

template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G) {
    for (unsigned i=1; i<G.verties(); i++) {
        os << i << ": ";

        auto edges = G.edges(i);
        for (auto& e : edges)
            os << "{" << e.dst << ": " << e.weight << "}, ";

            os << endl;
    }

    return os;
}

template <typename T>
auto create_reference_graph() {
    Graph<T> G(9);

    map<unsigned, vector<pair<unsigned, T>>> edge_map;
    edge_map[1] = { {2,0}, {5,0} };
    edge_map[2] = { {1,0}, {5,0}, {4,0} };
    edge_map[3] = { {4,0}, {7,0} };
    edge_map[4] = { {2,0}, {3,0}, {5,0}, {6,0}, {8,0} };
    edge_map[5] = { {1,0}, {2,0}, {4,0}, {8,0} };
    edge_map[6] = { {4,0}, {7,0}, {8,0} };
    edge_map[7] = { {3,0}, {6,0} };
    edge_map[8] = { {4,0}, {5,0}, {6,0} };

    for (auto& i : edge_map)
        for (auto& j : i.second)
            G.add_edge(Edge<T>{ i.first, j.first, j.second });

    return G;
}

template <typename T>
auto depth_first_search(const Graph<T>& G, unsigned start) {
    stack<unsigned> stack;
    set<unsigned> visited;
    vector<unsigned> visit_order;
    stack.push(start);

    while(!stack.empty()) {
        auto current_vertex = stack.top();
        stack.pop();

        if (visited.find(current_vertex) == visited.end()) {
            visited.insert(current_vertex);
            visit_order.push_back(current_vertex);

            for (auto& e : G.edges(current_vertex)) {
                if (visited.find(e.dst) == visited.end()) {
                    stack.push(e.dst);
                }
            }
        }
    }

    return visit_order;
}

int main() {
    using T = unsigned;

    auto G = create_reference_graph<T>();
    cout << "[입력 그래프]" << endl;
    cout << G << endl;

    cout << "[DFS 방문 순서]" << endl;
    auto dfs_visit_order = depth_first_search(G, 1);
    for (auto v : dfs_visit_order)
        cout << v << endl;

    return 0;
}

다음 코드를 실행시키면, 아래와 같은 출력결과가 나온다.

책에 나와있는 코드를 그대로 실행한 결과이다. 이것만으로는 이해가 잘 되지 않아 따로 간단하게 구현한 코드를 덧붙이겠다. 아래 코드는 따로 스택을 사용하지는 않고, 방문 여부를 나타내주는 bool 배열과 재귀를 사용하여 구현했다. 아마 알아보기는 이쪽이 좀 더 수월할것이다.

#include <iostream>
#include <vector>

using namespace std;

bool visited[9];        //방문 여부를 나타내주는 bool타입 배열
vector<int> graph[9];   //그래프를 나타내는 vector 배열

void DFS(int start) {
	visited[start] = true;

	cout << start << " ";

	for (int i=0; i<graph[start].size(); i++) { //인접한 정점의 갯수만큼 탐색
		int idx = graph[start][i];

		if (!visited[idx])
            DFS(idx);
	}   //해당 정점이 아직 방문한적이 없는 정점이면 재귀적으로 DFS 실행 / 방문했던 정점이라면 무시하고 다른 정점을 찾음
}

int main(void) {
    graph[1].push_back(2);
    graph[1].push_back(5);

    graph[2].push_back(1);
    graph[2].push_back(4);
    graph[2].push_back(5);

    graph[3].push_back(4);
    graph[3].push_back(7);

    graph[4].push_back(2);
    graph[4].push_back(3);
    graph[4].push_back(5);
    graph[4].push_back(6);
    graph[4].push_back(8);

    graph[5].push_back(1);
    graph[5].push_back(2);
    graph[5].push_back(4);
    graph[5].push_back(8);

    graph[6].push_back(4);
    graph[6].push_back(7);
    graph[6].push_back(8);

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

    graph[8].push_back(4);
    graph[8].push_back(5);
    graph[8].push_back(6);
    //vector 배열로 그래프 정의

    DFS(1);

    return 0;
}

분명히 같은 그래프인데 첫번째 코드 결과와는 결과값이 다르게 나왔다. 하지만 정점을 탐색하는 방식 자체는 동일하니 상관은 없다.