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

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

• 너비 우선 탐색(BFS, Breadth-First Search)
  • 시작 장점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식
  • 방문하지 않은 정점을 저장하기 위해 큐(Queue) 를 사용함.
    • 선입선출(FIFO) 자료구조
    • 큐에 있는 정점들은 큐에 들어갔던 순서대로 제거됨.
    • 이러한 큐의 속성을 이용하여 시작 정점에 가까이 있는 정점들을 먼저 처리할 수 있음.
  • 시간 복잡도 : O(V + E)
• 깊이 우선 탐색(DFS, Depth-First Search)
  • 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식
  • 더 방문할 정점이 없어지면, 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복함.
  • 이러한 그래프 탐색 방법을 백트래킹(Backtracking) 이라고 함.
  • 방문하지 않은 정점을 저장하기 위해 스택(Stack) 을 사용함.
    • 후입선출(LIFO) 자료구조
    • 현재 정점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용하기에 적합한 자료구조
  • 시간 복잡도 : O(V + E)
• BFS와 DFS의 차이점
  • BFS
    • 시작 정점에서 가까운 정점을 찾는데 적합함.
    • 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장됨.
      • 단일-시작 또는 다중-시작 최단 경로 알고리즘이 BFS 알고리즘을 조금 변경하여 사용하고 있음.
    • 현재 경계에 인접한 모든 정점을 방문함.
      • BFS에 의해 생성된 탐색 트리는 짧고 넓은편이고, 상대적으로 적은 메모리를 필요로 함.
  • DFS
    • 대체로 시작 정점에서 멀리 있는 정점을 찾을 떄 적합함.
    • 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장되지 않음.

 

동작 과정

①

• 가장 먼저 우리집 정점부터 방문함.

②

• 다음으로 R2 정점을 방문함.
  • 우리집 정점과 연결된 정점 R1과 R2 중에서 R2를 임의로 선택하였음.
• R1과 R2 중에서 어느 것을 먼저 방문해도 DFS 알고리즘으로 모든 정점을 탐색할 수 있음.

③

• 이번에는 R3 정점을 방문함.
  • R2와 연결된 정점은 R1과 R3이며, 이 중 임의로 R3를 먼저 선택하였음.

④

• 인접한 정점 중에서 아직 방문하지 않은 정점을 찾아 탐색을 진행하는 과정을 아래의 그림에 나타냈음.
• 마지막으로 R1을 방문하면, 이제 방문하지 않은 정점을 찾을 수 없게 됨.
  • 이 경우, 탐색이 종료됨.

 

코드

#include <iostream>
#include <string>
#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 {
public:
    // N개의 정점으로 구성되 그래프
    Graph(unsigned N) : V(N) {}

    // 그래프의 정점 개수 반환
    auto vertices() const { return V; }

    // 전체 에지 리스트 반환
    auto& edges() const { return edge_list; }

    // 정점 v에서 나가는 모든 에지를 반환
    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) {
        // 에지 양 끝 정점 ID가 유효한지 검사
        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.vertices(); i++) {
        os << i << ":\t";

        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;

    // 1번 정점부터 BFS 실행 & 방문 순서 출력
    cout << "[DFS 방문 순서]" << endl;
    auto bfs_visit_order = depth_first_search(G, 1);
    for (auto v : bfs_visit_order) {
        cout << v << endl;
    }

    return 0;
}

 

결과

[입력 그래프]
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