깊이 우선 탐색(DFS, Depth-first search)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

깊이 우선 탐색(DFS)

그래프 내 모든 정점을 탐색하는 방법의 하나이다.
시작 정점에서 멀어지는 방향으로 탐색하며, 더 방문할 정점이 없으면 다른 경로를 찾아 멀어지는 방향으로 재귀적으로 탐색한다.
O(V + E) 시간에 수행된다.
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 백트래킹(Backtracking) 기법의 하나이다.

1. 시작 정점 v를 스택에 삽입한다.
2. 스택이 비어있지 않은 동안 반복한다.
3. 스택에서 정점 1개를 꺼낸다.
4. 아직 방문하지 않았다면 방문하고, 이미 방문했다면 2로 돌아간다.
5. 꺼낸 정점을 방문했다고 표시한다.
6. 꺼낸 정점에 연결된 정점들 중 방문하지 않은 정점들을 스택에 삽입한다.
7. 2로 돌아간다.

 

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

using namespace std;

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

template <typename T>
class Graph
{
private:
    unsigned V;
    vector<Edge<T>> edge_list;

public:
    // N개의 정점으로 구성된 그래프
    Graph(unsigned V) : V(V) {}

    // 정점 개수 반환
    unsigned vertices() const { return V; }

    // 간선 리스트 반환
    vector<Edge<T>>& edges() const { return edge_list; }

    // v가 출발지인 모든 간선 반환
    vector<Edge<T>> edges(unsigned v) const
    {
        vector<Edge<T>> edges_from_v;

        copy_if(edge_list.begin(), edge_list.end(), back_inserter(edges_from_v), [v](const Edge<T>& e) { return e.src == v; });

        return edges_from_v;
    }

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

    friend ostream& operator << (ostream& os, const Graph<T>& G)
    {
        for (unsigned i = 1; i < G.vertices(); ++i)
        {
            os << i << ":\t";

            for (Edge<T>& e : G.edges(i))
                os << "{" << e.dst << ": " << e.weight << "}, ";

            os << endl;
        }

        return os;
    }
};

template <typename T>
Graph<T> create_reference_graph()
{
    // 정점이 8개인 그래프 생성
    // 0번 ID는 사용하지 않는다.
    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 (pair<unsigned, T>& j : i.second)
            G.add_Edge(Edge<T>{i.first, j.first, j.second});

    return G;
}

template <typename T>
vector<unsigned> depth_first_search(const Graph<T>& G, unsigned start)
{
    set<unsigned> visited;          // 방문한 정점
    vector<unsigned> visit_order;   // 방문 순서
    stack<unsigned> stck;

    stck.push(start);

    while (!stck.empty())
    {
        unsigned current_vertex = stck.top(); stck.pop();

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

            for (Edge<T>& e : G.edges(current_vertex))
                if (visited.find(e.dst) == visited.end())
                    stck.push(e.dst);
        }
    }

    return visit_order;
}

void main()
{
    using T = unsigned;

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

    // 1번 정점부터 DFS 수행
    vector<T> dfs_visit_order = depth_first_search<T>(G, 1);

    // 방문 순서 출력
    cout << "[DFS 방문 순서]" << endl;
    for (T v : dfs_visit_order)
        cout << v << endl;
}

 

출력

[입력 그래프]
1:      {2: 0}, {5: 0},
2:      {1: 0}, {5: 0}, {4: 0},
3:      {4: 0}, {7: 0},
4:      {2: 0}, {3: 0}, {5: 0}, {6: 0}, {8: 0},
5:      {1: 0}, {2: 0}, {4: 0}, {8: 0},
6:      {4: 0}, {7: 0}, {8: 0},
7:      {3: 0}, {6: 0},
8:      {4: 0}, {5: 0}, {6: 0},

[DFS 방문 순서]
1
5
8
6
7
3
4
2