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

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

```cpp

include

using namespace std;

template struct Edge { unsigned int src; unsigned int dst; T weight; };

template 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> 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&& e) { if(e.src>=1&&e.src<=V&&e.dst>=1&&e.dst<=V) edge_list.emplace_back(e); else cerr<<"에러: 유효 범위를 벗어난 정점!"<<endl; } template friend ostream& operator<<(ostream& os, const Graph& G); private: unsigned int V; vector> edge_list; };

template ostream& operator<< (ostream& os, const Graph& 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 auto create_reference_graph() { Graph 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 auto DFS(const Graph& G, unsigned int start) { stack stack; set visited; vector 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;

}