깊이 우선 탐색

Depth First Search(DFS)라고 부르는 깊이 우선 탐색은 다음과 같은 절차를 수행합니다.

1. 모든 정점을 false로 설정
2. 선택한 정점에 방문하고, 정점의 값을 true로 수정
3. 두 가지 절차중 하나 실행(처음 실행한 정점에거 a절차 실행시 반복 종료) a. 인접 정점이 모두 true라면 이전 정점으로 복귀 b. 그렇지 않다면, 현재 정점을 true로 수정후 인접 정점에서 가장 작은 정점 방문
4. 모든 정점이 true 값을 가진다면 그래프가 연결된 것임

DFS는 [너비 우선 탐색]과 다르게 queue가 아닌 stack을 사용한다.

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<stack>
 
using namespace std;
 
template<typename T>
struct Edge
{
    unsigned int src;
    unsigned int dst;
    T weight;
};
 
template<typename T>
class Graph
{
public:
    Graph(unsigned int N) : V(N){}
    auto vertices() const {return V;}
    auto &edges() const {return edge_list;}
    auto edges(unsigned int 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 int V;
    vector<Edge<T>> edge_list;
};
 
template<typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
    for(unsigned int 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 int, 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 DFS(const Graph<T>& G, unsigned int start)
{
    stack<unsigned int> stack;
    set<unsigned int> visited;
    vector<unsigned int> 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 int;
 
    auto G= create_reference_graph<T>();
    cout<<"[입력 그래프]"<<endl;
    cout<<G<<endl;
 
    cout<<"[DFS 방문 순서]"<<endl;
    auto dfs_visit_order = DFS(G,1);
    for(auto v : dfs_visit_order)
        cout<<v<<endl;
 
    return 0;
}